“数据结构”专接本复习纲要(4)

《“数据结构”专接本复习纲要(4)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、“数据结构乃专接本复习纲要2006.1第四章递归一.递归的概念K什么是递归我们知道，在程序中某个A函数（过程）的执行中可以调用另一个B函数（过程），而在B函数的执行过程中又可以调用另一个C函数（过程）。这叫做函数（过程）的嵌套调用。如果在函数嵌套调用的过程中，一个调用者函数（主调函数）自身成了被调用函数（被调函数），则说，发生了函数递归调用的现象。简称发生了递归。简言之，递归就是允许程序调用自己本身的过程或函数。2、递归的种类递归分两种：间接递归和直接递归。所谓间接递归是指函数A调用了函数B,在函数B嵌套调用其它函数的过程中，发生了调用函数A的情况，就说，函

2、数A发生了间接递归，或说函数A是一个间接递归函数。所谓直接递归是函数A在执行过程中调用了A自身。我们现在学习的递归都是直接递归。3、构成递归需具备的条件（1）子问题须与原始问题为同样的事，且更为简单。（2）不能无限制地调用本身，需有个出口，化简为非递归处理。所谓递归的出口是指使函数不再调用自身的判别条件。也就是说，符合此条件后，函数可以不用再调用自身了，一般情况下，此时函数可以得到明确的处理结果了。4、递归程序与非递归程序的差异递归程序与非递归程序的主要差别在于返回数据和保存递归函数调用现场的内存需求量。因为递归函数在执行时一般要多次调用函数自身或其它函数，

3、所以它比非递归函数需要更多的空间来存放每次调用函数时的现场保存和函数返回值的保存。由于多次调用函数，因此，要花费较多的机器时间。所以，一般而言，一个递归函数和完成相同功能的非递归函数相比，递归函数在空间和时间的效率上都比非递归函数低。但一般递归函数比非递归函数构造简洁，代码短，可读性好。下面用一个表对比二者。递归非递归程序可读性易难代码量大小小大运行时间长短占用stack大小5、递归与循环的比较一般递归都可以化成等价的非递归的循环。循环是反复执行某些条件，直到符合所指定条件为止，但不包含调用函数自身。循环和递归的差异：⑴循环用while(for)递归用if.

4、..else来控制循环。〈2〉递归用较多的参数及较少的局部变量。二、递归执行过程的分析1、计算阶乘阶乘的计算可以用以下递归的函数定义来表示：f(n)=<若n=0若n>0据此，可以写出如下计算阶乘的递归函数longfact(intn)longfact(intn){longt;(1)if(n==0)t=l;(2)elset=n*fact(n-l);(3)returnt;}n=4n=3n=ln=04==0F3==0Ffact(4)4*fact(3J—l3*fact(^—3*22==0F1==OF2*fac匹H2*1l*fact(O；P1*10==0T1递归出口回代

5、递归调用注意，虽然递归调用每次调用的都是自身，但每次调用是实参发生了变化，这在分析递归执行过程中很重要。类似地，求l+2+3+・・・+n的递归过程如下intsum(intn){if(n==l)return1;elsereturnn+sum(n-l);}求sum(10)的值■1x=0P(x)=0、p(x+l)/xx<0据此，设计递归函数如下floatp(intx){ifdi==0)return1;elseif(n>0)returnx*p(x-l);else}returnp(x+l)/x;类似地,求xn（n为整数，xHO）的递归函数表示如下

6、2、数制转换将10进制数转换成8进制数打印输出的递归函数可以表示如下：prl0_8(x)=vr打印结束若x=0Iprl0_8(x/8)打印x%8若x>0,先打印x/8的转换结果，再打印x%8{trl0_8（x/8）;/*先调用自身去x/8的转换结果*/printf（“％d”,x%8）;/*转换完x/8后，再打印x%8*/}prl0_8(100)x=1001100>0prl0_8(12)x=12%112>0prl0_8⑴x=l11>0x=010>02prl0_8(100/8)J3打印f00%8_4返回2pi40_8(12/8尸3打印"12%8-4返回2prl0

7、_8(l/8)3打由1%84返回4返回voidprl0_8(intx)/*10进制数X转换成8进制数打印的递归函数*/{1if(x>0)/*若x>0*/2return;/*递归出口是x<=0*/}假设要转换十进制数100,递归调用示意如下:先打印1%8,再打印12%8,最后打印100%83、递归程序例（1）voidp(intw){1if(w>0)2{p(w-1)；3printf(u%d,,,w);}4return;nw=4nw=3nw=2W=114>013>012>01l>0—

8、w=010>0P(4L2p(44M3打丽4返回2p(3引一3打篇4返回2p(2■

9、忙3打轨4返回2p’3打帝4返回打印顺序12344＞