递归算法 15p.ppt

递归算法
递归的定义
递归设计方法
递归与循环
递归函数示例
1
这个流程如下:
void B( )
{ …..
}
void A( )
{ …..
B( );
…..
}
void main( )
{ …..
A( );
…..
}
main函数 A函数 B函数


调用A函数调用B函数

结束
递归的定义
一个函数为完成它的复杂工作,可以调用其他函数
函数嵌套调用时,有一个重要的特征,先被调用的函数后返回。
如这里所举例子,函数B( ) 完成计算返回后,函数A( )继续计算(可能还要调用其他函数),待计算完成,才返回到主函数
这样从主函数出发,形成一个长长的调用链,就是通常所说的函数嵌套调用(nested call)
例如,从主函数出发,主函数调用函数A( ),函数A( )又调用函数B( ) 。
2
递归的定义
若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的
若一个函数直接地或间接地调用自己,则称这个函数是递归函数(recursive function)
在以下三种情况下,常常用到递归方法
定义是递归的
数据结构是递归的
问题的解法是递归的
递归的定义
3
递归函数分为直接递归与间接递归
直接递归:在函数中出现调用函数本身
间接递归:在函数中调用了其它函数,而该其它函数又调用了本函数
两种不同的递归程序图示如下:
递归的定义
直接递归
间接递归
返回
4
递归设计方法
递归设计首先要确定求解问题的递归模型,了解递归的执行过程,在此基础上进行递归程序设计
递归模型
递归模型反映一个递归问题的递归结构,例如
f(1)=1
f(n)=n*f(n-1) n>1
第一个式子给出了递归的终止条件,第二个式子给出了f(n)的值与f(n-1)的值之间的关系,我们把第一个式子称为递归出口,把第二个式子称为递归体。
一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定到何时为止,后者确定递归的方式。
实际上,递归是把一个不能或者不好直接求解的大问题转化为一个或者几个小问题来解决,如此分解,直至每个小问题都可以直接解决(此时分解到递归出口)
注意:递归分解不是随意的分解,递归分解要保证大问题与小问题相似,即求解过程与环境相似。
5
求解f(n)的分解过程如下 f(n) -> f(n-1) -> f(n-2) …… f(3) -> f(2) -> f(1)
一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是量变,即原来的大问题在慢慢变小,但尚未解决,遇到递归出口后,便发生了质变,即原递归问题转化为直接问题。上面的求值过程如下:
f(n) <- f(n-1) <- f(n-2) <- f(n-3) ……<- f(2) <- f(1)
这样f(n)就计算出来了,因此,递归的执行过程由分解和求值两部分构成。
由上面的分析可以得出一般的递归设计的步骤如下
(1) 对原问题f(s)进行分析,假设出合理的较小问题f(s’)
(2) 假设f(s’)是可解得,在此基础上确定f(s)的解,即给出f(s)与f(s’)的关系
(3) 确定一个特定情况(如f(1)或f(0))的解,由此作为递归出口
6
f(n)

f(n-1)
.
.
f(2)
f(1)
分解
递归是把一个不能或者不好直接求解的大问题转化为一个或者几个小问题来解决,如此分解,直至每个小问题都可以直接解决(此时分解到递归出口)
一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是量变,即原来的大问题在慢慢变小,但尚未解决,遇到递归出口后,便发生了质变,即原递归问题转化为直接问题。上面的求值过程
求值
返回
7
递归与循环
递归与循环的相似点
递归程序和循环有一些相似之处,递归程序在调用自己的时候会不断的调用自己,所以肯定有一个判断控制语句,这一个点与循环控制语句相同,因为循环也是有一个判断语句,否者两者都会出现问题,递归会出现无限递归而循环也会出现无限循环。因此递归程序具有循环的功能,所以用循环写的代码可以用递归写的代码代替。
递归与循环的相异点
递归代码有一个优点,就是代码比较短,所以在有的时候需要短代码的时候就可以用递归来代替循环。
递归比循环多一个东西,这个东西就是栈,递归在调用的时候使用了栈,所以递归可以通过栈执行一些循环执行起来比较麻烦的操作,比如:要倒着打印一个单向链表的数据。
8
假如字符数组a中存储有一字符串“12345”,
现在需要输出: 5 4 3 2 1
因为递归可以通过系统自动调用堆栈,所以可以这样写:
void prin(char a[ ])
{ if(a[0]!='\0')