递归算法.ppt

递归算法递归的定义递归设计方法递归与循环递归函数示例1这个流程如下:voidB(){…..}voidA(){…..B();…..}voidmain(){…..A();…..}main函数A函数B函数调用A函数调用B函数结束递归的定义一个函数为完成它的复杂工作,可以调用其他函数函数嵌套调用时,有一个重要的特征,先被调用的函数后返回。如这里所举例子,函数B()完成计算返回后,函数A()继续计算(可能还要调用其他函数),待计算完成,才返回到主函数这样从主函数出发,形成一个长长的调用链,就是通常所说的函数嵌套调用(nestedcall)例如,从主函数出发,主函数调用函数A(),函数A()又调用函数B()。2递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的若一个函数直接地或间接地调用自己,则称这个函数是递归函数(recursivefunction)在以下三种情况下,常常用到递归方法定义是递归的数据结构是递归的问题的解法是递归的递归的定义3递归函数分为直接递归与间接递归直接递归:在函数中出现调用函数本身间接递归:在函数中调用了其它函数,而该其它函数又调用了本函数两种不同的递归程序图示如下:递归的定义直接递归间接递归返回4递归设计方法递归设计首先要确定求解问题的递归模型,了解递归的执行过程,在此基础上进行递归程序设计递归模型递归模型反映一个递归问题的递归结构,例如f(1)=1f(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))的解,由此作为递归出口6f(n)f(n-1)..f(2)f(1)分解递归是把一个不能或者不好直接求解的大问题转化为一个或者几个小问题来解决,如此分解,直至每个小问题都可以直接解决(此时分解到递归出口)一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是量变,即原来的大问题在慢慢变小,但尚未解决,遇到递归出口后,便发生了质变,即原递归问题转化为直接问题。上面的求值过程求值返回7递归与循环递归与循环的相似点递归程序和循环有一些相似之处,递归程序在调用自己的时候会不断的调用自己,所以肯定有一个判断控制语句,这一个点与循环控制语句相同,因为循环也是有一个判断语句,否者两者都会出现问题,递归会出现无限递归而循环也会出现无限循环。因此递归程序具有循环的功能,所以用循环写的代码可以用递归写的代码代替。递归与循环的相异点递归代码有一个优点,就是代码比较短,所以在有的时候需要短代码的时候就可以用递归来代替循环。递归比循环多一个东西,这个东西就是栈,递归在调用的时候使用了栈,所以递归可以通过栈执行一些循环执行起来比较麻烦的操作,比如:要倒着打印一个单向链表的数据。8假如字符数组a中存储有一字符串“12345”,现在需要输出:54321因为递归可以通过系统自动调用堆栈,所以可以这样写:voidprin(chara[]){if(a[0]!='\0')prin(a+1);printf(“%4c”,a[0]);}voidmain(){chara[15]="12345";prin(a);}这种操作是循环无法这么简单完成的。返回9递归函数示例阶乘汉诺塔10