数据结构――递归

第5章递归递归与递归程序设计递归程序到非递归程序的转换递归程序设计的应用实例递归程序执行过程的分析5.1递归与递归程序设计在一个函数的定义中出现了对自己本身的调用，称之为直接递归；或者一个函数p的定义中包含了对函数q的调用，而q的实现过程又调用了p，即函数调用形成了一个环状调用链,这种方式称之为间接递归。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。例1试编一个递归函数，求正整数n的阶乘值n！。用fact(n)表示n的阶乘值，据阶乘的数学定义可知：1n=0fact(n)=n*fact(n-1)n0该问题的算法为：intFact(intn){intm;if(n==0)return(1);else{m=n*Fact(n-1);return(m);}}例2试编一个递归函数，求第n项Fibonacci级数的值。假设使用Fibona(n)表示第n项Fibonacci级数的值，根据Fibonacci级数的计算公式：1n=1Fibona(n)=1n=2Fibona(n-1)+Fibona(n-2)n2该问题的算法为：intFibona(intn){intm;if(n==1)return(1);elseif(n==2)return(1);else{m=Fibona(n-1)+Fibona(n-2);return(m);}}递归程序设计具有以下两个特点：（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口；（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。5．2递归程序执行过程的分析在递归程序的运行过程中，系统内部设立了一个栈，用于存放每次函数调用与返回所需的各种数据，主要包括：函数调用执行完成时的返回地址、函数的返回值、每次函数调用的实在参数和局部变量。在递归程序的执行过程中，每当执行函数调用时，必须完成以下任务：（1）计算当前被调用函数每个实在参数的值；（2）为当前被调用的函数分配一片存储空间，用于存放其所需的各种数据，并将这片存储空间的首地址压入栈中；（3）将当前被调用函数的实在参数、将来当前函数执行完毕后的返回地址等数据存入上述所分配的存储空间中；（4）控制转到被调用函数的函数体，从其第一个可执行的语句开始执行。当从被调用的函数返回时，必须完成以下任务：（1）如果被调用的函数有返回值，则记下该返回值，同时通过栈顶元素到该被调用函数对应的存储空间中取出其返回地址；（2）把分配给被调用函数的那片存储空间回收，栈顶元素出栈；（3）按照被调用函数的返回地址返回到调用点，若有返回值，还必须将返回值传递给调用者，并继续程序的执行。例3试编写一个递归函数，在第一行打印输出1个1，在第二行打印输出2个2，……在第n行打印输出n个n。例如，当n=5时，调用该函数的输出结果为：122333444455555该问题的算法为:print(intn){inti;if(n!=0){print(n-1);for(i=1;i=n;i++)printf(%d,n);printf(\n);}}Print(5)print(4)for(i=1;i=5;i++)printf(“%d”,5)printf(“\n”);print(3)for(i=1;i=4;i++)printf(“%d”,4)printf(“\n”);print(2)for(i=1;i=3;i++)printf(“%d”,3)Printf(“\n”);print(1)for(i=1;i=2;i++)printf(“%d”,2)Printf(“\n”);print(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)Fibona(5)S0(1)m=Fibona(4)+Fibona(3);return(m);m=Fibona(3)+Fibona(2);return(m);(2)m=Fibona(2)+Fibona(1);return(m);(3)m=Fibona(2)+Fibona(1);return(m);1return(1)(4)return(1)(5)return(1)(6)(7)(8)(9)return(1)return(1)(10)Fibona(5)的执行过程S1S2S311123(11)(12)(13)(14)1(15)(17)(18)52例4:5.3递归程序到非递归程序的转换采用递归方式实现问题的算法程序具有结构清晰、可读性好、易于理解等优点，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，因此在希望节省存储空间和追求执行效率的情况下，人们更希望使用非递归方式实现问题的算法程序；另外，有些高级程序设计语言没有提供递归的机制和手段，对于某些具有递归性质的问题（简称递归问题）无法使用递归方式加以解决，必须使用非递归方式实现。因此，本小节主要研究递归程序到非递归程序的转换方法。一般而言，求解递归问题有两种方式：（1）在求解过程中直接求值，无需回溯。称这类递归问题为简单递归问题；（2）另一类递归问题在求解过程中不能直接求值，必须进行试探和回溯，称这类递归问题为复杂递归问题。两类递归问题在转换成非递归方式实现时所采用的方法是不同的。通常简单递归问题可以采用递推方法直接求解；而复杂递归问题由于要进行回溯，在实现过程中必须借助栈来管理和记忆回溯点。5.3.1简单递归程序到非递归程序的转换采用递归技术求解问题的算法程序是自顶向下产生计算序列，其缺点之一是导致程序执行过程中许多重复的函数调用。递推技术同样以分划技术为基础，它也要求将需求解的问题分划成若干与原问题结构相同、但规模较小的子问题；与递归技术不同的是，递推方法是采用自底向上的方式产生计算序列，其首先计算规模最小的子问题的解，然后在此基础上依次计算规模较大的子问题的解，直到最后产生原问题的解。由于求解过程中每一步新产生的结果总是直接以前面已有的计算结果为基础，避免了许多重复的计算，因而递推方法产生的算法程序比递归算法具有更高的效率。简单递归问题非递归实现的基本思想：将原问题分解成若干结构与原问题相同，但规模较小的子问题，并建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录递推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。例5采用非递归方式实现求正整数n的阶乘值。仍使用Fact(n)表示n的阶乘值。要求解Fact(n)的值，可以考虑i从0开始，依次取1,2,……，一直到n，分别求Fact(i)的值，且保证求解Fact(i)时总是以前面已有的求解结果为基础；当i=n时，Fact(i)的值即为所求的Fact(n)的值。根据阶乘的递归定义，不失一般性，显然有以下递推关系成立：1i=0Fact(i)=i*Fact(i-1)i0上述递推关系表明Fact(i)是建立于Fact(i-1)的基础上的，在求解Fact(i)时子问题只有一个Fact(i-1)，且整个Fact(n)的求解过程无需回溯，因此该问题属于简单递归问题，可以使用递推技术加以实现，实现过程中只需定义一个变量fac始终记录子问题Fact(i-1)的值。初始时，i=1,fac=Fact(i-1)=Fact(0)=1；在此基础上根据以上递推关系不断向前递推，使i的值加大，直至i=n为止。阶乘问题的非递归算法的实现如下：intFact(intn){inti,fac;fac=1;/*将变量fac初始化为Fact(0)的值*/for(i=1;i=n;++i)fac=i*fac;/*根据递推关系进行递推*/return(fac);}例6试编写两个函数，分别使用递归方式和非递归方式求第n阶勒让德多项式的值。已知勒让德多项式的递归定义如下：1n=0pn(x)=xn=1((2n-1)xpn-1(x)(n-1)pn-2(x))/nn1递归实现算法：floatp(intn,floatx){floatp1,p2;if(n==0)return(1.0);elseif(n==1)return(x);else{p1=(2*n-1)*x*p(n-1,x);p2=(n-1)*p(n-2,x);return((p1-p2)/n);}}下面考虑该问题的非递归实现：根据勒让德多项式的定义，当n1时，第n阶多项式的值是建立在第n-1阶多项式的值和第n-2阶多项式的值的基础上。考虑一般情况，当i1时，第i阶多项式的值应该建立在第i-1阶多项式的值和第i-2阶多项式的值的基础上。如果仍然采用p(n,x)表示第n阶勒让德多项式的值，则在i1的情况下有如下递推关系成立：p(i,x)=((2i-1)xp(i-1,x)(i-1)p(i-2,x))/i显然，可以利用以上递推关系，从i=2开始，逐步增大i的值，依次求解第i阶勒让德多项式的值；当i=n时，便求到了p(n,x)的值。在整个求解过程中不需要进行试探和回溯，因而该问题属于简单递归问题，完全可以使用递推技术加以实现。在具体实现时可以定义两个变量pre1和pre2，分别记录上述递推关系中两个子问题的解，即pre1=p(i-2,x)，pre2=p(i-1,x)，且pre1和pre2的值始终随着i的值的改变而发生变化：每当新求出第i阶多项式的值后，i的值要增加1，而在此之前应该修改pre1和pre2的值，用pre1记录pre2当前的值，而用pre2记录新求出的多项式的值，直至i=n。floatp(intn,floatx){floatpre1,pre2,a,b,valuep;inti;if(n==0)return(1.0);elseif(n==1)return(x);else{pre1=1.0;pre2=x;for(i=2;i=n;++i){a=2*i-1;b=i-1;valuep=(a*pre2*x-b*pre1)/i;pre1=pre2;pre2=valuep;}return(valuep);}}5.3.2复杂递归程序到非递归程序的转换复杂递归问题在求解的过程中无法保证求解动作一直向前，往往需要设置一些回溯点，当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所设置的回溯点。例7按中点优先的顺序遍历线性表问题：已知线性表list以顺序存储方式存储，要求按以下顺序输出list中所有结点的值：首先输出线性表list中点位置上的元素值，然后输出中点左部所有元素的值，再输出中点右部所有元素的值；而无论输出中点左部所有元素的值还是输出中点右部所有元素的值，也均应遵循以上规律。例如，已知数组list中元素的值为：183249266103012845则list中元素按中点优先顺序遍历的输出结果为：641832926121030845试采用递归和非递归算法实现该遍历问题。递归实现算法如下：#defineMAXSIZE20typedefintlistarr[MAXSIZE];voidlistorder(listarrlist,intleft,intright){/*将数组段list[left..right]的元素按中点优先顺序输出*/intmid;if(left=right){mid=(left+right)/2;printf(%4d,list[mid]);listorder(list,left,mid-1);listorder(list,mid+1,right);}}Leftmid-1midmid+1right下面考虑该问题的非递归实现：在线性表的遍历过程中，输出中点