递归算法设计ppt课件.ppt

《递归算法设计ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章函数--递归选自：《计算机导论与程序设计基础》第6章以及第16章的16.1《C程序设计教程》5.13~5.151递归的概念递归过程递归程序设计提纲21.递归的概念递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。我们先从一个最简单的例子导入。31.递归的概念例：编写一个函数fac，计算阶乘n!按过去的迭代算法，该函数可以写成：intfac(intn){inti,p;p=1;for(i=2;i

2、<=n;i++)p=p*i;returnp;}4现在换一个角度考虑，n！不仅是1×2×3×…×n,还可以定义成：intf(intn){if(n==0)return1;elsereturnn*f(n-1);}1当n＝0n!＝n×(n－1)!当n＞0根据以上数学定义，函数f能否写成左边所示？函数能否调用自身？答案是肯定的。C系统会保证调用过程的正确性，这就是递归！1.递归的概念设f(n)=n!1当n＝0则f(n)＝n×f(n-1)当n＞05递归的定义：从程序书写来看，在定义一个函数时，若在函数的功能实现部分又出现

3、对它本身的调用，则称该函数是递归的或递归定义的。从函数动态运行来看，当调用一个函数A时，在进入函数A且还没有退出（返回）之前，又再一次由于调用A本身而进入函数A，则称之为函数A的递归调用。intf(intn){if(n==0)return1;elsereturnn*f(n-1);}6递归可以分为直接递归和间接递归两种。直接递归：函数体里面发生对自己的调用；间接递归：函数A调用函数B，而函数B又直接或间接地调用函数A。1.递归的概念A(…){…B(…);…}B(…){…A(…);…}A(…){…A(…);…}7

4、1.递归的概念不用担心函数A内部又调用函数A，会使得调用无休无止，肯定存在某个条件，当该条件成立的时候，函数A将不会再调用自身。例如，求n！时，该结束条件是if(n==0)intf(intn){if(n==0)return1;elsereturnn*f(n-1);}8递归的概念递归过程递归程序设计提纲92.递归过程求f（2）的递归调用过程？#includeintf(int);main(){inti=2;printf(“%d”,f(i));system(“pause”);}intf(intn)

5、//递归函数：求n!{if(n==0)return1;elsereturnn*f(n-1);}102.递归过程intf(intn)//递归函数：求n!{if(n==0)return1;elsereturnn*f(n-1);}调用调用①②④③11返回2112.递归过程请思考：发出f(2)调用时，将2赋值给形参n。然后发出f(1)调用，将1赋值给形参n。接着发出f(0)调用，将0赋值给形参n。后来赋给形参n的值会不会覆盖原来赋给n的值（如值1覆盖原来的值2）？为什么？－不会，每一次函数调用会在栈顶分配新的活动记录

6、。对递归函数的每一次调用结束返回时，为何能回到调用前的程序运行状态？如f(1)调用结束返回f(2)时，n的值为2。－函数访问的永远是栈顶的活动记录。当f(1)调用结束时，位于栈顶的f(1)的活动记录将出栈，此时位于栈顶的将是f(2)的函数活动记录。12回顾函数调用过程2.递归过程被调用函数中的数据现场信息，用于调用结束能正确返回13f(0)返回值1f(1)返回值1f(2)返回值2调用f(2)调用f(1)调用f(0)5.printf(“%d”,f(i));8.intf(intn)9.{10.if(n==0)11

7、.return1;12.else13.returnn*f(n-1);14.}intf(int);main(){inti=2;printf(“%d”,f(i));system(“pause”);}intf(intn)//递归函数：求n!{if(n==0)return1;elsereturnn*f(n-1);}14求f(6)的递归调用过程递推阶段回归阶段返回152.递归过程可见，递归算法的执行过程分递推和回归两个阶段。当递推时，并没有求值的计算操作，实际的计算操作是在回归过程实现的。递推阶段：递推阶段是个不断简化

8、问题的阶段：把对较复杂问题（规模为n）的求解转化为比原问题简单一些的问题（规模小于n）的求解。例如对f(6)的求解转化为f(5)的求解，对f(5)的求解转化为f(4)的求解…直到转化为对f(0)的求解。当递推到最简单的不用再简化的问题时，递推终止。如f函数中，n==0的情况。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，就不再继续剥了。162.递归过程回归阶段：在回归阶段，当获得最简单情况的解