3.3递归(栈的应用)３.３递归递归按其调用方式可分为直接递归和间接递归：1、直接递归:自己调用自己。如：voidf(n){……f(n/2);……}2、间接递归：P调用D，D调用P；如：voidP(intn)voidD(intn){……{……D(n/3);P(n/2);…………}}2、递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。3、递归的要素例1、定义是递归的：（１）阶乘函数求解阶乘n!的过程（2）Fibonacci数列0n=0Fib(n)=1n=1Fib(n-1)+Fib(n-2)n>1011235813……递归算法longunsignedFib(intn){if(n==0||n==1)returnn;//递归出口elsereturnFib(n-1)+Fib(n-2);//递归调用}注：累计递归调用次数：2*Fib(n+1)-1。例２、问题的解法是递归的：利用递归思想来求解某类问题（本身没有明显的递归结构，但操作方法可以用递归很好的描述）使其更为简单。如：汉诺塔问题、背包问题、八皇后问题等。经典问题——汉诺塔问题汉诺塔问题的递归求解方法:如果n=1，则将这一个盘子直接从塔A移到塔C上。否则，执行以下三步：⑴将塔A上的n-1个碟子借助塔C先移到塔B上；⑵把塔A上剩下的一个碟子移到塔C上；⑶将n-1个碟子从塔B借助于塔A移到塔C上。算法实现：voidHanoi(intn,charA,charB,charC){if(n==1)Move(A,C);else{Hanoi(n-1,A,C,B);Move(A,C);Hanoi(n-1,B,A,C);}}Hanio(3,A,B,C)递归函数的内部执行过程⑴运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；⑵每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；⑶每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。如：求解阶乘n!，递归工作仅需保留４个参数：函数名fact，参数n，局部变量x（存放fact(n-1)的值）和y（存放n*fact(n-1)的值）。参见P103.实例分析：（１）尾递归：递归调用语句只有一个，且处于函数的最后。（可不用栈来存取相关信息）如阶乘求解的非递归算法：longunsignedfact(intn){longunsignedintf=1;for(inti=1;i<=n;i++)f=f*i;returnf;}（２）单向递归：各递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用语句都处在算法的最后。如斐波那契数列非递归算法：longunsignedFib(intn)//用循环实现{if(n==0||n==1)returnn;longunsignedf1=0,f2=1,fn;//求n>=2的情况for(inti=2;i<=n;i++){fn=f1+f2;f1=f2;f2=fn;}returnfn;}（３）利用栈来模拟系统运行时的栈汉诺塔非递归算法（了解）：//Datatype.h#ifndefDatatype_H#defineDatatype_HclassDatatype{public:shortintno;//存放一个标识，0表示直接移动一个圆盘intndisk;//为1表示需进一步分解；charSPeg;//参数AcharAPeg;//参数BcharDPeg;//参数C};#endifvoidhanoi2(intn,chara,charb,charc){SeqStack<Datatype>S1;DatatypeH,H1;H.no=1;H.ndisk=n;H.SPeg=a;H.APeg=b;H.DPeg=c;S1.Push(H);//初始入栈while(!S1.Empty()){if(S1.GetTop().no==1&&S1.GetTop().ndisk!=1){//退栈hanoi(n,a,b,c);将hanoi(n-1,a,c,b)操作参数进栈H.ndisk=S1.GetTop().ndisk-1;H.SPeg=S1.GetTop().SPeg;H.APeg=S1.GetTop().APeg;H.DPeg=S1.GetTop().DP