递归.docx
- 文档编号:9133144
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:25
- 大小:121.26KB
递归.docx
《递归.docx》由会员分享,可在线阅读,更多相关《递归.docx(25页珍藏版)》请在冰点文库上搜索。
递归
1 递归及其实现
递归是程序设计中最常用的方法之一,许多程序设计语言都提供递归调用的功能。
有些
问题用递归方法求解往往使程序非常简单清晰。
栈在实现递归调用中起了关键作用。
一个直接调用自己或通过一系到的调用语句间接地调用自己的函数,称做递归函数。
直
接调用自己的函数称做直接递归函数。
间接调用自己的函数称做间接递归函数。
有很多数学函数是递归定义的。
例如阶乘函数的递归定义是
1 若n=0
Fact(n)=
n×Fact(n-1) 若n>0
又例如,Fibonacci(斐波那契)数列可递归定义为
0 若n=0
Fib(n)= 1 若n=1
Fib(n-1)+Fib(n-2)若n>1
据此可以写出实现求n的阶乘和求Fibonacci数列中第n项的递归算法,如算法21和
算法22所示。
longintfact(intn){ //求非负整数n的阶乘
if(!
n)return1; //0!
=1
elsereturnn*fact(n-1); //n!
=n*(n-1)!
}//fact
算法21 求阶乘的递归算法
longintfib(intn){ //求斐波那契数列中的第n个数
if(n<2)returnn; //f(0)=0,f
(1)=1
elsereturnfib(n-1)+fib(n-2); //若n>1,f(n)=f(n-1)+f(n-2)
}//fib
算法22 求斐波那契数的递归算法
一般地说,每一个递归函数的定义都包含两个部分。
(1)递归基础
对无需递归的规模最小的问题直接进行处理。
(2)递归步骤
将一般情况的问题简化成一个或多个规模较小的同性质的问题,递归地调用同样的方法
求解这些问题,使这些问题最终简化成基础问题。
算法21的递归基础是n=0时,直接返回1(0!
=1)。
一般情况下,将fact(n)简化成规
模较小的问题fact(n-1),求出fact(n-1)后再与n相乘即求得了fact(n)。
算法22的递归基础是n<2时,直接返回n(因为fib(0)=0,fib
(1)=1)。
一般情况下,将fib(n)
简化成两个规模较小的问题fib(n-1)和fib(n-2),求出fib(n-1)和fib(n-2)之后再求它们的和即可
求出fib(n)。
递归函数结构清晰,程序易读,而且它们的正确性易于证明,所以递归函数是程序设计
的有力工具。
为理解递归函数是如何实现的,先考察任意两个函数之间相互调用的情形。
用高级语言编制的程序中,调用函数和被调用函数之间的链接和信息交换需通过栈来进行。
通常,当一个函数在运行期间调用另一个函数时,在运行被调用函数之前,系统需先完
成三件事:
(1)将所有的实在参数、返回地址等信息传递给被调用函数保存;
(2)为被调用
函数的局部变量分配存储区;(3)将控制转移到被调用函数的入口。
而从被调用函数返回调
用函数之前,系统也要先完成三件事:
(1)保存被调用函数的计算结果;
(2)释放被调用函
数的数据区;(3)按被调用函数保存的返回地址将控制转移到调用函数。
当有多个函数构成
嵌套调用时,按照“后调用先返回”的原则。
上述函数间的信息传递和控制转移是通过“栈”
来实现的(这个栈一般称为系统工作栈),即系统将整个程序运行时所需的数据空间安排在
一个栈中,每当调用一个函数时,就为它在栈顶分配一片存储区,每当从一个函数退出时,
就释放它的存储区。
所以,当前正在运行的函数的数据区必在栈顶。
一个递归函数的运行过程类似于多个函数的嵌套调用,只是调用函数和被调用函数是同
一个函数。
因此,和每次调用相关的一个重要概念是递归函数运行的“层次”。
假设调用该
递归函数的主函数处在第0层,则从主函数调用递归函数为进入“第1层”,从第i层递归调
用本函数为进入“下一层”,即第i+1层。
在退出第i层递归时,应返回到“上一层”,即第
i-1层。
为保证递归函数的正确执行,系统也应象在处理一般函数调用时那样,在系统工作
栈中为递归函数开辟数据存储区。
每一层递归所需信息构成了一个“工作记录”,其中包括
所有的实在参数、所有的局部变量以及返回到上一层的返回地址。
每进入一层递归,就产生
一个新的工作记录压入栈顶。
每退出一层递归,就从栈项弹出一个工作记录。
所以,当前执
行层的工作记录必定是工作栈栈顶的工作记录,称这个工作记录为“活动记录”,并称指示
活动记录的栈顶指针为“当前环境指针”(curptr)。
图4从编译器的角度说明了阶乘函数的
递归实现。
2 汉诺塔问题
除了某些数学函数可用递归方式定义外,一些本身具有递归特性的数据结构,如二叉树
(见第五章)等也可递归地描述。
另有一类问题,虽然问题本身没有明显的递归结构,但用
递归求解比较方便,例如汉诺塔问题。
例4 (n阶Hanoi塔问题)设有A、B、C三个塔柱。
在A柱上插有由小到大编号为1
到n的n个直径各不相同的圆盘,如图5(a)所示。
现要求按以下规则将A柱上的n个圆
盘移到C柱上:
1)每次只能移动一个圆盘;2)大盘不能压小盘;3)圆盘可以插在A、B、
C中的任一塔柱上。
可以用递归的方法求解此问题。
递归基础:
当n=0时,不需要作任何操作。
递归步骤:
当n>0时,将此问题分解成三个规模较小的问题:
(1)首先将A柱上面的n-1个圆盘移到B柱;
(2)再将A柱上最大的第n号盘移到C柱;
(3)最后将B柱上n-1个圆盘移到C柱的第n号盘之上。
如图5(b)(c)(d)所示。
据此可写出求解n(n≥0)阶Hanoi塔问题的递归算法(算法23)。
为方便叙述该算法的执
行过程,人为地在每条语句前添加了编号。
图6展示了调用函数hanoi(2,a,b,c)的执行过程。
voidhanoi(intn,charx,chary,charz){//入口条件:
n>=0
1.if(n>0){ //若n=0,则不需做任何动作,仅当n>0时
2. hanoi(n-1,x,z,y); //先将n-1个盘从x柱经z柱搬到y柱
cout<<"MoveDisk"< 4. hanoi(n-1,y,x,z); //再将y柱上的n-1个盘经x柱搬到z柱 5.}//if 6.}//hanoi 算法23 求解汉诺塔问题的递归算法 3 背包问题 设有一个背包可以放入总重量为S的物品,现有n件物品,重量分别为w1,w2,…,wn。 问能否从这n件物品中选择若干件放入背包,使得放入的物品总重量恰好为S。 如果存在一 组符合上述要求的物品,则称此背包问题有解(用TRUE表示问题有解),否则称此问题无解 (用FALSE表示无解)。 假如我们定义一个维数组W存储各物品的重量,用布尔函数knap(S,n)求解背包问题。 其参数S表示背包还留有的容量,n为可供选择的物品个数。 显然,如果S=0,背包问题总 有解,即knap(0,n)为TRUE,因为不选择任何物品放入背包即可。 当S<0时,背包问题总无 解,即knap(S,n)为FALSE,因为不论选择何物品放入背包,其总重量不会是负值。 当S>0但n<1 时,背包问题也无解,因为不放任何物品到背包里,其重量之和不会是正值。 假如S>0且n ≥1,我们要求解背包问题有两种途径: 一种是选择第n件物品放入背包,于是背包剩余的 容量为S-W[n](W[n]中存储wn,即第n件物品的重量),可选择的物品是前n-1件。 如果 knapn(s-w[n],n-1)有解,则knap(S,n)也有解,否则knap(S,n)无解,说明选择第n件物 品是错的。 另一种是不选第n件物品,此时背包问题简化为knap(S,n-1),如果它有解,则 knap(S,n)也有解,如果它无解,则knap(S,n)也无解,从而背包问题可以递归地定义如下: TRUE 若S=0 knap(S,n)= FALSE 若S<0或S>0且n<1 knap(S-W[n],n-1)或knap(S,n-1) 若S>0且n≥1 上述递归定义是确定的,因为每次递归,n总减少1,S也可能减小W[n],所以递归若干次 之后,递归基础的条件(S≤0或n<1)必定成立,所以递归过程在有限步之后总能结束。 例5 用递归方法求解背包问题。 根据knap(S,n)的定义,容易写出背包问题的递归算法,如算法24所示。 constintMAXN=11; //假设最多只有十件物品 intw[MAXN]={0,3,5,6,3,7,1,2,4,9,8};//假设物品的重量已存在w[1]...w[10]中 intknap(ints,intn){ //s为背包的容量,n为可供选择物品的最大编号 if(s==0)returnTRUE; //若背包已装满,则有解 if((s<0)||(s>0)&&(n<1))returnFALSE;//若背包容量为负数或已无物品可选,则必无解 if(knap(s-w[n],n-1)){ //先试探将第n个物品装入背包中,若因此有解,则原题有解 cout< elsereturnknap(s,n-1);//不然,则舍弃第n个物品 }//knap 算法24 求背包问题的递归算法 我们知道,递归函数是用栈来实现的。 因此如果使用的程序设计语言不支持递归调用, 则可以利用栈来模拟递归函数的执行过程。 把一个递归过程转换成一个等价的非递归过程, 现已找到了不止一种方法。 这里不打算对这些方法作全面而深入的探讨,有兴趣的读者可以 阅读参考资料[3]。 应该指出,如果一个问题可用递归算法求解,则必定有非递归的算法, 因为至少可以将递归算法转换成等价的使用栈的非递归算法。 然而,可能也有其它的非递归 算法。 例如,背包问题也可以用非递归方法求解。 用一个栈stk来模拟背包,用T记录放入 背包中的物品的总重量。 从第N个物品开始,逐次检查第N个,第N-1个,…,第1个物品, 如果背包中尚有空间可放第i个物品,则将它放入背包(即将它的编号压入栈stk,并令T 增加W[i])。 如果放不下或虽有空间但已无可供选择的物品,则从栈中弹出一物品的编号(即 将该物品从背包中取走),并从T中减去它的重量,然后从它的下一个(编号小1)的物品 开始,重新检查能否将它放入背包,这个过程一直进行到T中物品总重量等于S或是栈stk 的空且要检查的物品编号已小于1。 结束时如T等于S则求得一解,在栈stk中的物品(编号) 即为所选物品。 算法25描述了用非递归方法求解背包问题的算法。 intknap(intt,intn){ //t为背包的容量,n为可供选择物品的最大编号 Stacks;ETpe;inti,found=0;//若找到一解,found被置为1,初始时found的值为0 if(t==0)returnTRUE; //背包已满,问题有解 StackInit(s,MAXSIZE); //假设MAXZISE大于n while(! found&&((n>0)||! StackEmpty(s))){//若尚未找到解且有物品可选或栈非空 if(n<=0){ //若已无物品可选,则表明先前的选择有误 Pop(s,n); //将最近选择的物品(将其编号置入n)从背包中取出 t+=w[n]; //背包的容量t因此增加w[n] --n; //既然不能选用物品n,就试选物品n-1 } if(n>0){ //如果还有物品可选 if(t>=w[n]){ //而且背包还能放得下 t-=w[n]; //就将物品n放入背包,t因此减少w[n] if(! StackFull(s)){ //若栈未满 Push(s,n); //将n入栈,即将物品n放入背包 --n; //因此可选物品的编号小1 if(t==0)found=1; //若背包已满,则求得一解 } elseexit(ERROR); //若栈已满,则出错 } else--n; //若背包放不下物品n,则尝试选择物品n-1 }//if(n>0) }//while if(found) //如果找到一解,就将所选物品的重量输出 for(i=s.top;i>0;--i){ Pop(s,e);cout< returnfound; //返回求解结果 }//knap 算法25 求背包问题的非递归算法 图7展示了执行kknap(13,6)时栈stk的状态变化过程。 W={3,5,6,3,7,1} 4 递归的效率 一般地说,虽然递归定义的函数可读性好,也易于证明其正确性,但执行效率不高。 例 如,求Fibonacci数fib(5)的递归算法(算法22)的执行过程可用如图8所示的递归树(树 的定义见第五章)来描述。 从图中可以看出,树中有许多重复的部分。 例如,为了求fib(5), 需要二次调用fib(3),三次调用fib (2),五次调用fib (1)。 如果求fib(7),则重复的部分更多。 由此 可见,fib(n)函数的效率很低。 效率低的原因是在计算过程中没有保留已得到的中间结果。 例如,在求fib(4)时,已计算出fib(3)和fib (2),但退出fib(4)时仅返回fib(4)的值,所以在调用 fib(3)时仍要重新计算。 为保留中间计算结果,可以在定义fib函数时增加一些参数,例如, 可将fib函数重新定义为newfib(n),它调用了一个辅助的递归函数Fib(first,second,n),算 法26和算法27实现了这种新的求解方法。 longintnewfib(intn){ //把实质性的工作交给Fib去做 returnFib(0,1,n); }//newfib 算法26 改进的求斐波那契数的算法 longintFib(longintfirst,longintsecond,intn){//利用参数提高递归效率 if(n==0)returnfirst; //要求的斐波那契数同first的距离为0 returnFib(second,first+second,n-1);//要求的斐波那契数同second的距离为n-1 }//Fib 算法27求斐波那契数的尾递归算法 求Fib(0,1,5)的递归树如图3,9所示。 显然只需递归调用Fib六次即可求出f5,效率比fib 要高。 函数Fib(first,second,n)的工作过程可解释为: first和second是最近已计算出的两个 Fibonacci数,而n表示first和要求的数之间的距离。 初始时first等于f0(f0=0),second等于 f1(f1=1),如图10(a)所示。 图10(b)展示了求解Fib(o,1,5)时各递归层中first,second和n的含义。 递归函数Fib有一个特点,即被调用的Fib函数的返回值,恰恰是调用它的上一层Fib 函数的返回值,于是最低层的函数返回值直接就是最高层函数的返回值。 换句话说,当函数 返回上一层时根本就不再使用上一层的局部变量,因此没有必要用栈来保留上一层的局部变 量,即可以不使用递归的方法实现同样的计算。 例如算法28就是对应于算法27的非递归算 法。 longintFibo(intn){ //求斐波那契数的非递归算法 longintfirst=0,second=1,temp;inti;//初始时,first=f0,second=f1 for(i=n;i>0;--i){ //first中存储的数逐渐向第n个斐波那契数靠近 temp=first;first=second;second+=temp;}//first移向下一个斐波那契数 returnfirst; //for语句结束时,first已是第n个斐波那契数 }//Fibo 算法28 求斐波那契数的非递归算法 显然,也可以用图10来解释Fibo的执行过程。 由于Fibo消除了递归,省掉了n次函 数调用的开销,所以它的效率更高。 尾递归函数是一种特殊的递归函数。 如果一个递归函数的返回值是直接计算而得或恰是 一个递归调用自身而得到的返回值,那么这个递归函数就称为尾递归函数。 换句话说,如果 递归函数中有一个递归调用(自身)的语句是这个函数的最后一个可执行语句,那么这个函 数就被称做尾递归函数。 应该注意,最后一个可执行语句并不一定是程序中的最后一条语句。 例如,Fib的返回值或者是first(若n=0),或者是递归调用Fib的返回值,所以它是尾递归 函数。 从算法27中也可以看出。 Fib函数中的递归调用语句是最后一个可执行语句。 尾递归函数是一类重要的函数,一方面它的效率一般较高,例如算法27的效率比算法 22的效率高。 另一方面,很容易消除尾递归函数中的递归,使之成为非递归函数,从而不 需要用栈来保留每个递归副本的局部变量,例如算法28比算法27效率更高。 例6 用尾递归实现阶乘函数,并消除递归。 算法29和算法30是用尾递归实现阶乘函数的算法。 算法31是求n的阶乘的非递归算 法。 longintnewfact(intn){//入口条件: n>=0,把实质性工作交给Fact去做 returnFact(1,n);// }//newfact 算法29 另一种求阶乘算法 longintFact(longintresult,intn){//入口条件: n≥0,第1次调用时,result应为1 if(n<=1)returnresult; returnFact(result*n,n-1); }//Fact 算法30 求阶乘的尾递归算法 longintFactor(intn){ //求n! (n≥0)的非递归算法 longintresult=1;inti; for(i=n;i>1;--i)result*=i; returnresult; }//Factor 算法31 求阶乘的非递归算法 应该指出,并不是所有的递归函数都可用尾递归求解,也没有一般法则设计尾递归。 尾 递归函数有时也未必比递归函数效率更高(例如,算法29并不比算法21效率高,因为它多 用了一个形式参数且递归次数并未减少),但容易根据尾递归函数消除递归,从而提高效率 和减少使用的存储空间。 5.5 递归与迭代 有一类问题,既可以用递归的方法求解,也可以用迭代的方法求解。 所谓迭代(iteration) 意即重复。 例如,求n个数a1,a2,…,an的和用递归的方法求解,其思路是: 若n=0,则和 为0,否则可将这n个数看成由两部分组成: 前n-1个数和最后一个数an。 用递归的方法求 出前n-1个数的和,再加上an,即可求出这n个数的和,见图11(a)。 用迭代的方法求解,其 思路是: 若n=0,则和为0,否则可将这n个数看成一串数: 最后一个数an和它之前的n-1个 数。 在累加和中依次加入an,an-1…,a1即可求出n个数的和,见图11(b). 算法32是求n个数的和的递归算法。 算法33是相应的迭代版本。 假设n个数已存储在 数组a的分量a[1],…,a[n]中。 floatsum(intn){//求n(n≥0)个数的和的递归算法,假设这些数存放在数组a中 if(n==0)return0; returnsum(n-1)+a[n]; }//sum 算法32 求和的归算法 floatSum(intn){//求个n(n>=0)个数的和的非递归算法,假设这些数存放在数组a中 floats=0;inti; for(i=n;i>0;--i)s+=a[i]; returns;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归