数据结构第06章递归及汉诺塔.docx

《数据结构第06章递归及汉诺塔.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归算法主要知识点「递归的概念递归算法的执行过程递归算法的设计方法递归过程和运行时栈递归算法的效率分析递归算法到非递归算法的转换（设计举例c=fl(a);z=f2(y);intf2(intt){inta,c;intfl(intx{inty,z;1函数的递归调用定义：函数直接或间接的调用自身叫函数的递归调用intf(intx){inty,z;z=f(y);return(2*z);)Af()return(2^z);return(3+c);)fl()(2()调*调口f()fl()f2()说明1.从图上可以看到，这两种递归调用都是无终止的自身调用2.显然，程序中不应出现这种无终止的递归调用，

2、而只应出现有限次数的、有终止的递归调用3.这可以用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。例有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道,要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄

3、大2。即age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=10可以用式子表述如下：age(n)=10(n=[)age(n)=age(n—1)+2(n>D可以看到，当n>1时，求第n个人的年龄的公式是学则我。尸此可以用一个函数表示上述关系。图表不求第5个人年龄的过程。=10=121.从图可知，求解可分成两个阶段:第一阶段是“回溯,即将第n个人的年龄表示为第（n-1）个人年龄的函数，而第（n-1）个人的年龄仍然不知道，还要“回溯”到第（n—2）个人的年龄……直到第1个人年龄。此时age（1）已知，不必再向

4、前推了。》第二阶段，采用递推方法，从第1个人的已知年龄推算出第2个人的年龄（12岁），从第2个人的年龄推算出第3个人的年龄（14岁）一直推算出第5个人的年龄（18岁）为止。>一个递归的问题可以分为“回溯”和“递推”两个阶段。要经历许多步才能求出最后的值。»若要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。例如，age(1)=10,就是使递归结束的条件可以用一个函数来描述上述递归过程:/*求年龄的递归函数*//*c用作存放函数的返回值的变量*/age(intn){intc；ifCn==1)c=10；elsec=age(n—1)+2；return(c)；}main(){i

5、ntx=age(5);cout«x«endl;运行结果如下：18main函数中只有一个语句。整个问题的求解全靠一个age(5)函数调用来解决。函数调用过程如图所示。mainage函数n=3age(5)=18age⑷=16age(3)=14age⑵=12age(1)=10age函数age函数age函数age函数age函数mainn=5n=4n=3n=2n=lage⑸=18age⑷=16age(3)=14age(2)=12age(1)=10由图可得：age函数共被调用5次，即age(5)、age(4)>age(3)>age(2)、age(1)其中age(5)是main函数调用的，其余4次

6、是在age函数中调用的，即递归调用4次。>需强调说明的是：在某一次调用age函数时并不是立即得到age(n)的值，而是一次又一次地进行递归调用，到age(1)时才有确定的值，然后再递推出age(2)、age(3)、age(4)、ageC5)例用递归方法求n!。用递归方法，即>51=4!X5,>4!=3!X4>3!=2!X3>2!=1!X2>1!=1>可用下面的递归公式表示:n!=1(n=0,1)nl=n-(n—1)!(n>1)例求n的阶乘(几=0,1)(〃>1)intfact(intn){intf;if(n<0)cout«66dataerror!0;elseif(n==0lln==l

7、)f=l；elsef=fact(n-l)*n;return(f);}main(){intn,y;cin»n;y=fact(n);cout«y«endl;)啜解阶乘n!的过程计算fact(4)17返回24递归调用计算4*fact(3)计算3*fact⑵返回6返回2计算2*fact(l)归求值返回117计算fact(l)17例3Fibonacci数列f0n=0Fib(n)J1n=1Tib(n-1)+Fib(n-2)n>1011235813・・・・・・1717递