文档介绍：第二章 递归算法
1
主要内容
1、递归的概念
2、递归算法的设计方法
3、递归算法的执行过程
4、递归算法的效率分析
2
递归概念的引入
一个小故事：
山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座 return(head->data+Sum(head->next));
}
12
什么时候使用递归
一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法
前提：数据是有序排列的；
基本思路：
将目标值与数组的中间元素进行比较；
若相等，查找成功。否则根据比较的结果将查找范围缩小一半，然后重复此过程。
3. 问题的求解方法是递归的
13
请问：
是否在
此列表当中？
14
请问：
是否在
此列表当中？
数组正
中间的
元素。
15
请问：
是否在
此列表当中？
不予考虑
16
请问：
是否在
此列表当中？
正中间
的元素
17
请问：
是否在
此列表当中？
正中间
的元素
不予考虑
？
18
void main()
{
int b[] = {05, 13, 19, 21, 37, 56, 64, 75,
80, 88, 92};
int x = 21;
printf("x位于数组的第%d个元素\n",
bsearch(b, x, 0, 10));
}
如何用递归来实现？
19
函数原型： int bsearch(int b[], int x, int L, int R);
递归的形式？
递归的边界？
问题分析
20
int bsearch(int b[], int x, int L, int R)
{
int mid;
if(L > R) return(-1);
mid = (L + R)/2;
if(x == b[mid])
return mid;
else if(x < b[mid])
return bsearch(b, x, L, mid-1);
else
return bsearch(b, x, mid+1, R);
}
21
什么时候使用递归
折半查找无非就是三种情况，其中两种情况的问题解法如果以算法来表示，都存在算法调用自身的情况。
递归算法的特点就是：将问题分解成为形式上更加简单的子问题来进行求解。递归算法不但是一种有效的分析问题方法，也是一种有效的算法设计方法，是解决很多复杂问题的重要方法。
折半查找中的递归现象总结
22
典型的三种情况使用递归
1、问题的定义是递归的
2、数据结构是递归的
3、问题求解的过程是递归的
23
递归的分类
直接递归：函数直接调用本身。
A( )
{……
CALL A( )
......
}
间接递归：一函数在调用其他函数时，又产生了对自身的调用。
A( ) B( )
{…… {……
CALL B（） CALL A（）
…… } …… }
24
递归模型
递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：
fun(1)=1 (1)
fun(n)=n*fun(n-1) n>1 (2)
其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为递归边界,把第二个式子称为递归体。
25
一般地,一