递归算法详解

[3]。应该指出，如果一个问题可用递归算法求解，则必定有非递归的算法， 因为至少可以将递归算法转换成等价的使用栈的非递归算法。然而，可能也有其它的非递归 算法。例如，背包问题也可以用非递归方法求解。用一个栈stk来模拟背包，用T记录放入 背包中的物品的总重量。从第N个物品开始，逐次检查第N个,第N-1个，…，第1个物品， 如果背包中尚有空间可放第i个物品，则将它放入背包（即将它的编号压入栈stk，并令T 增加W[i]）。如果放不下或虽有空间但已无可供选择的物品，则从栈中弹出一物品的编号（即 将该物品从背包中取走），并从T中减去它的重量，然后从它的下一个（编号小1）的物品 开始，重新检查能否将它放入背包，这个过程一直进行到T中物品总重量等于S或是栈stk 的空且要检查的物品编号已小于1。结束时如T等于S则求得一解，在栈stk中的物品(编号) 即为所选物品。 算法25描述了用非递归方法求解背包问题的算法。 int knap(int t,int n){                   // t为背包的容量,n为可供选择物品的最大编号   Stack s; ETp e; int i,found=0;//若找到一解,found被置为1,初始时found的值为0   if (t==0) return TRUE;                      // 背包已满,问题有解   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;                //若背包已满,则求得一解            }            else exit(ERROR);                     //若栈已满,则出错         }         else --n;                                    //若背包放不下物品n,则尝试选择物品n-1      }//if(n>0)   }//while   if (found)                                        //如果找到一解,就将所选物品的重量输出      for (i=s.top; i>0; --i){         Pop(s,e); cout<0;--i){                   //first中存储的数逐渐向第n个斐波那契数靠近      temp=first; first=second; second+=temp;}//first移向下一个斐波那契数   return first;                         //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的阶乘的非递归算 法。 long int newfact(int n){//入口条件:n>=0,把实质性工作交给Fact去做   return Fact(1,n);// }//newfact 算法29   另一种求阶乘算法 long int Fact(long int result,int n){//入口条件:n≥0,第1次调用时,result应为1   if(n<=1) return result;   return Fact(result*n,n-1); }//Fact 算法30   求阶乘的尾递归算法 long int Factor(int n){   //求n!(n≥0)的非递归算法   long int result=1; int i;   for(i=n;i>1;--i) result*=i;   return result; }//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]中。 float sum(int n){//求n(n≥0)个数的和的递归算法,假设这些数存放在数组a中   if(n==0) return 0;   return sum(n-1)+a[n]; }//sum 算法32   求和的归算法 float Sum(int n){//求个n(n>=0)个数的和的非递归算法,假设这些数存放在数组a中   float s=0; int i;   for(i=n;i>0;--i) s+=a[i];   return s; }//Sum 算法33   求和的非递归算法      从可读性上看，这两个算法都易于理解，但算法32不仅要调用sum函数n+1次，而且 在系统工作栈中要保留n+1个实在参数（从n到0）。相反，算法33只调用函数Sum一次， 且在系统工作栈中只保留实在参数n和局部变量s和i。因此迭代方法的效率比递归方法的 效率高。但不是所有递归算法都有相应的迭代算法，例如hanoi( )函数。尽管没有一般的递 归与迭代之间的对应（转换）法则，但有些较复杂的递归函数，仍可用迭代方法求解。      例7   用递归和非递归方法求二项式系数C(n,k)= C   (n≥k)。 根据数学知识,C(n,k)=n!/(k!×(n-k)!)。但用这个公式求C(n,k)是不适宜的，因为 C(20,1)=20，但20！是一个很大的数，可能不能用整型变量存储，所以要用C(n,k)的递归 定义：          1       若k=0 C(n,k) =      1       若k=n                C(n-1,k)+C(n-1,k-1)       若n>k>0 据此可写出求C(n,k)的递归算法,如算法34所示。 int com(int n,int k){                     //用递归方法求C(n,k) (n≥k≥0)   if(k==0) return 1;                      // C(n,0)=1   if(k==n) return 1;                      // C(n,n)=1   return com(n-1,k)+com(n-1,k-1);   // C(n,k)=C(n-1,k)+C(n-1,k-1) }//com 算法34   求组合数的递归算法 这个算法虽然避免了用公式计算时可能引起的溢出，但效率很低。例如，求com(5，1) 时，就调用了函数com(n,k) 九次，见图3。12。 为设计一个非递归的求C(n,k)的算法,先研究一下著名的杨辉三角形，如图13(a)所示, 其中第n行第k个数恰为C(n,k)。注意到C(n,k)=C(n,n-k),于是不妨假定k≤n/2。假设每行最 右边的1之后都是0，那么可以从第1行开始，逐行求出杨辉三角形的下一行。对第i行第 k（0≤k≤i）个元素，利用公式C(i-1,k)+C(i-1,k-1),即可依次求出a , a ,…，a , a (上标 [m]表示第m行)，如图13(b)所示。因为要求的是C(n,k)(k≤n/2)，所以对每一行只需求出最 右的k+1 个数即可。又因为不需要保存每一行的值，故可以只设一个有n+1 个元素的数组 a。由此可得用双重迭代求C(n,k)的非递归算法,如算法35所示。调用Com(5,3)时，算法执 行过程如图 13(c)所示。 int Com(int n,int k){                        // 用迭代方法求C(n,k) (n≥k≥0)   int i,j,*a=new int[n+1];                // 产生一个有n+1个元素的数组a   for(i=1;in/2) k=n-k;                            // C(n,k)=C(n,n-k)   for(i=1;i<=n;++i)                           // 逐行求C(i,k)      for(j=0;j<=k;++j)                        // 每行只要求最右边的k+1个C(i,j)         if((i-j)>=1)                            // 若i