第4讲 递归专题讲座

《第4讲 递归专题讲座》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4讲递归递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。4.1递归概述一个函数在它的函数体内调用它自身称为递归（recursion）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归

2、的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。使用递归要注意以下几点：（1）递归就是在过程或函数里调用自身；（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。例如有函数r如下：intr(inta){b=r(a−1);returnb;}这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种

3、条件后就不再作递归调用，然后逐层返回。构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。例4-1用递归法计算n!。n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。（1）描述递归关系递归关系是这样的一种关系。设{U1,U2,U3,…,Un,…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。33注意到，当n≥1时，n!=n*(n−1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k−1)!有关。（2）确定递归边界在步骤1的递归关

4、系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#includeintf(intx){return(f(x−1));}main(){printf(f(5));}它没有规定递归边界，运行时将无限循环，会导致错误。（3）写出递归函数并译为代码将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即n!=n*(n−1)!当n>1时n!=1当n

5、=1时再将这种关系翻译为代码，即一个函数：longf(intn){longg;if(n<0)printf("n<0,输入错误！");elseif(n==1)g=1;elseg=n*f(n−1);return(g);}（4）完善程序主要的递归函数已经完成，设计主程序调用递归函数即可。#includelongf(intn){longg;if(n<0)printf("n<0,输入错误！");elseif(n==1)g=1;elseg=n*f(n-1);return(g);}voidmain(){intn;longy;33printf("计算n!，请输入n:"

6、);scanf("%d",&n);y=f(n);printf("%d!=%ld",n,y);}程序中给出的函数f是一个递归函数。主函数调用f后即进入函数f执行，如果n<0,n==0或n=1时都将结束函数的执行，否则就递归调用f函数自身。由于每次递归调用的实参为n−1，即把n−1的值赋予形参n，最后当n−1的值为1时再作递归调用，形参n的值也为1，将使递归终止，然后可逐层退回。下面我们再举例说明该过程。设执行本程序时输入为5，即求5!。在主函数中的调用语句即为y=f(5)，进入f函数后，由于n=5，不等于0或1，故应执行f=f(n−1)*n，即f=f(5−1)*5。该

7、语句对f作递归调用即f(4)。进行4次递归调用后，f函数形参取得的值变为1，故不再继续递归调用而开始逐层返回主调函数。f(1)的函数返回值为1，f(2)的返回值为1*2=2，f(3)的返回值为2*3=6，f(4)的返回值为6*4=24，最后返回值f(5)为24*5=120。综上，得出构造一个递归方法基本步骤，即描述递归关系、确定递归边界、写出递归函数并译为代码，最后将程序完善。例4-2计算阿克曼函数阿克曼(Ackerman)函数a(n，m)递归定义如下：试输出阿克曼函数的(m≤3,n≤10)的值。解：a函数是一个随着变量m,n变化的双递归