jidao-chap6-递归算法设计

1第五章函数--递归选自：《计算机导论与程序设计基础》第6章以及第16章的16.1《C程序设计教程》5.13~5.1521.递归的概念2.递归过程3.递归程序设计提纲31.递归的概念•递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。•我们先从一个最简单的例子导入。41.递归的概念例：编写一个函数fac，计算阶乘n!按过去的迭代算法，该函数可以写成：intfac(intn){inti,p;p=1;for(i=2;i=n;i++)p=p*i;returnp;}5现在换一个角度考虑，n！不仅是1×2×3×…×n,还可以定义成：intf(intn){if(n==0)return1;elsereturnn*f(n-1);}1当n＝0n!＝n×(n－1)!当n＞01.递归的概念设f(n)=n!1当n＝0则f(n)＝n×f(n-1)当n＞0根据以上数学定义，函数f能否写成左边所示？函数能否调用自身？答案是肯定的!C系统会保证调用过程的正确性，这就是递归！6递归的定义：从程序书写来看，在定义一个函数时，若在函数的功能实现部分又出现对它本身的调用，则称该函数是递归的或递归定义的。从函数动态运行来看，当调用一个函数A时，在进入函数A且还没有退出（返回）之前，又再一次由于调用A本身而进入函数A，则称之为函数A的递归调用。intf(intn){if(n==0)return1;elsereturnn*f(n-1);}7递归可以分为直接递归和间接递归两种。直接递归：函数体里面发生对自己的调用；间接递归：函数A调用函数B，而函数B又直接或间接地调用函数A。1.递归的概念A(…){…B(…);…}B(…){…A(…);…}A(…){…A(…);…}直接递归间接递归81.递归的概念•不用担心函数A内部又调用函数A，会使得调用无休无止，肯定存在某个条件，当该条件成立的时候，函数A将不会再调用自身。例如，求n！时，该结束条件是if(n==0)intf(intn){if(n==0)return1;elsereturnn*f(n-1);}91.递归的概念2.递归过程3.递归程序设计提纲102.递归过程•求f（2）的递归调用过程？#includestdio.hintf(int);main(){inti=2;printf(“%d”,f(i));system(“pause”);}intf(intn)//递归函数：求n!{if(n==0)return1;elsereturnn*f(n-1);}112.递归过程2＝＝0f(2)真假调用f(1)计算2*f(1)f(1)f(0)1＝＝0真假调用f(0)计算1*f(0)0＝＝0真假f(0)＝1返回返回intf(intn){if(n==0)return1;elsereturnn*f(n-1);}调用调用①②④③11返回2122.递归过程•请思考：–发出f(2)调用时，将2赋值给形参n。然后发出f(1)调用，将1赋值给形参n。接着发出f(0)调用，将0赋值给形参n。后来赋给形参n的值会不会覆盖原来赋给n的值（如值1覆盖原来的值2）？为什么？－不会，每一次函数调用会在栈顶分配新的活动记录。–对递归函数的每一次调用结束返回时，为何能回到调用前的程序运行状态？如f(1)调用结束返回f(2)时，n的值为2。－函数访问的永远是栈顶的活动记录。当f(1)调用结束时，位于栈顶的f(1)的活动记录将出栈，此时位于栈顶的将是f(2)的函数活动记录。13开辟新的运行环境保存现场参数结合执行函数体恢复现场释放本函数的运行环境返回回顾函数调用过程2.递归过程返回地址机器的状态信息形参(放实参的值)局部变量简化的函数活动记录被调用函数中的数据现场信息，用于调用结束能正确返回并执行14操作系统返址i步骤（1）操作系统2返址i步骤（2）操作系统2返址i步骤（3）/*5*/2返址n操作系统2返址i步骤（4）/*5*/2返址n/*13*/1返址n操作系统2返址i步骤（5）/*5*/2返址n/*13*/1返址n/*13*/0返址n操作系统2返址i步骤（6）/*5*/2返址n/*13*/1返址n操作系统2返址i步骤（7）/*5*/2返址n操作系统2返址i步骤（8）f(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.return1;12.else13.returnn*f(n-1);14.}1.intf(int);2.main()3.{4.inti=2;5.printf(“%d”,f(i));6.system(“pause”);7.}8.intf(intn)//递归函数：求n!9.{10.if(n==0)11.return1;12.else13.returnn*f(n-1);14.}15求f(6)的递归调用过程递归深度f（n）0（主程序）f（6）1f（6）＝6×f（5）6×120＝7202f（5）＝5×f（4）5×24＝1203f（4）＝4×f（3）4×6＝244f（3）＝3×f（2）3×2＝65f（2）＝2×f（1）2×1＝26f（1）＝1×f（0）1×1＝1f（0）＝1（返回）[递推阶段][回归阶段]递推阶段回归阶段返回162.递归过程•可见，递归算法的执行过程分递推和回归两个阶段。当递推时，并没有求值的计算操作，实际的计算操作是在回归过程实现的。•递推阶段：–递推阶段是个不断简化问题的阶段：把对较复杂问题（规模为n）的求解转化为比原问题简单一些的问题（规模小于n）的求解。例如对f(6)的求解转化为f(5)的求解，对f(5)的求解转化为f(4)的求解…直到转化为对f(0)的求解。–当递推到最简单的不用再简化的问题时，递推终止。如f函数中，n==0的情况。–就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，就不再继续剥了。172.递归过程•回归阶段：–在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。如在得到f(1)的解后，又依次得到f(2)、f(3)…直到f(6)的值。–就像将剥下来的白菜叶又从里往外一叶一叶合起来，直到最外层菜叶。182.递归过程•思考：递归与迭代的比较(以求阶乘为例)。–迭代:从已知的初始条件出发，逐次去求所需要的阶乘值，这相当于从菜心“推到”（通过循环）最外层的菜叶。f(0)=1f(1)=1*f(0)=1f(2)=2*f(1)=2–递归：先从最外层的菜叶“递推”到菜心(递归函数调用)，再从菜心“回归”到最外面的菜叶（递归函数返回）。192.递归过程•递归算法的出发点不放在初始条件上，而放在求解的目标上，是从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。•就求阶乘而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的迭代关系，这时递归算法就表现出了明显的优越性。•下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。201.递归的概念2.递归过程3.递归程序设计提纲21•什么样的问题可以用递归解决？如果解决问题的方法是把该问题分解成小的子问题，并且这些小的子问题可以用同样的算法解决，这样不断分解，直到子问题比较简单、可以直接解决时分解过程即终止，那么就可以用递归。递归的思想就是将一个问题先转化为与原问题性质相同、但规模小一级的子问题，然后再重复这样的转化，直到问题的规模减小到我们很容易解决为止。3.递归程序设计22一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归逐级返回。如何设计递归算法:1）对所求解的问题、要计算的函数书写递归定义；注意一定要有终止条件和对应的操作。2）正确地设计递归函数的参数。注意：递归算法最外层肯定采用的是选择结构！为什么？3.递归程序设计23练习1.求浮点数x的n次幂(n≧0)。函数递归定义:nx1当n＝0＝x*当n＞0nx1nxfloatpower(floatx，intn){if(n==0)return1;elsereturnx*power(x,n-1);}递归程序设计举例24递归程序设计举例练习2.设计递归函数求任意正整数的位数。num=1234intlength(intnum){if(num/10==0)return1;elsereturnlength(num/10)+1;}intlength(intnum){intlen;len=0;if(num/10==0)len=1;else//从最低位开始，依次从n中砍掉各位while(num0){num=num/10;//去掉最低位len++;/*分解出一位数字，长度加1*/}returnlen;}1ifnum/10=length(num)=length(num/10)+1ifnum/10≠0025递归程序设计举例123/10＝＝0length(123)真假调用length(12)计算length(12)+1length(12)length(1)12/10＝＝0真假调用length(1)计算length(1)+11/10＝＝0真假length(1)＝1返回值1返回值2调用调用①②④③返回值326递归程序设计举例练习3.求任意正整数的逆置数。num=1234递归思路1：将除最高位之外的数先逆置。例如：reverse(1234)=1＋reverse(234）×10思路1递归定义：reverse(num)=numifnum长度为1highBit+reverse(restNum)×10ifnum长度大于1其中：highBit=num/power(10,len-1);restNum=num%power(10,len-1);len=num的长度；递归函数参数设计考虑：len作为递归函数的参数传入27递归设计思路1：num=1234reverse(1234,4)＝1+reverse(234,3)*10reverse(234,3)=2+reverse(34,2)*10reverse(34,2)=3+reverse(4,1)*10reverse(4,1)=4①②③④返回4返回3+4*10=43返回2+43*10=432⑥⑦⑤返回1+432*10=4321递归程序设计举例28递归程序设计举例intreverse(intnum,intlen){intrestNum,highBit;if(len==1)//如果num是个位数则递归结束returnnum;else{highBit=num/power(10,len-1);//得到最高位restNum=num%power(10,len-1);//得到剩余位//递归调用，并形成逆置数returnhighBit+reverse(restNum,len-1)*10;}}num=1234自定义power函数：intpower(intx,inty)29递归程序设计举例练习3.求任意正整数的逆置数。num=1234递归思路2：将除最低位之外的数先逆置。例如：reverse(1234)=4*1000+reverse(123)递归定义1：reverse(num)=numifnum长度为1lowBit*power(10,len-1)+reverse(restNum)ifnum长度大于1其中：lowBit=num%10;restNum=num/10;len=num的长度；30递归程序设计举例递归设计思路2：num=1234reverse(1234,4)＝4*1000+reverse(123,3)reverse(123,3)=3*100+reverse(12,2)reverse(12,2)=2*10+reverse(1,1)reve