学步园

     最近在实际问题中遇到了好几个需要使用递归函数才能解决的问题。在这里做个总结。所谓递归函数：就是直接或者间接的调用自身的函数。一种通俗的说法便是：递归就是用自己的简单情况定义自己。

    先举一个关于递归应用的简单例子：

   楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,问共有多少种不同的走法.

   该问题的解法可以典型的用到递推公式：

由于n=1时f(1)=1,f(n)数列是一个fibonacci数列，故用一般的递归程序就可得出结果来了。

    对于较复杂的递归程序，《c和指针》上说“一旦理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利的完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近于限制条件，递归函数总是能够正确的完成任务”。比较赞同这一点，个人觉得使用递归的熟练程度体现了一个人的自信程度。而阅读递归程序时相信递归会顺利的完成任务而不要过于纠缠其细节也是人自信的体现。

    最典型的使用递归方法的是全排列的实现。

    下面这个全排列分析及实现均来自：http://blog.chinaunix.net/u2/81947/showart_1330222.html

全排列分析  

通常我们希望检查n个不同元素的所有排列方式来确定一个最佳的排序。比如a,b,c的排列方式有abc,acb,bac,bca,cab,cba六种。
    由于采用非递归的c++函数来输出排列方式很困难，所以采用递归是一种比较不错的方法。
    其核心是：将每个元素放到n个元素组成的队列最前方，然后对剩余元素进行全排列，依次递归下去

    比如：a b c
    首先将a放到最前方（跟第一个元素交换），然后排列b c，然后将a放回本来位置 

结果 a b c； a c b
    其次将b放到最前方（跟第一个元素交换），然后排列a c，然后将b放回本来位置
结果 b a c； b c a
   。。。
 
    如果是4个元素，就将元素依次放到第一个元素的位置，后面的排序类似前面的3元素排序。

算法实现

/*<br /> * 本程序对一个数组进行全排列，并输出<br /> * 文件名perm.cpp<br /> */<br /> #include <iostream><br /> using namespace std;</p> <p>/*<br /> * 函数模板，递归调用对一个数组进行全排列<br /> */<br /> template <class T><br /> void Perm(T list[],int k,int m)<br /> {<br /> int i;<br /> if(k == m)//输出一个全排列<br /> {<br /> for(i=0;i <= m;i++)<br /> cout<<list[i];<br /> cout<<endl;<br /> }<br /> else //list[k:m]有多个排列方式<br /> //递归的产生这些排列方式<br /> for(i = k;i <= m;i++)<br /> {<br /> Swap(list[k],list[i]);//交换位置，逐步前提<br /> Perm(list,k+1,m);<br /> Swap(list[k],list[i]);//将位置还回去，对下一次排列负责<br /> }<br /> }</p> <p>template<class T><br /> inline void Swap(T& a,T& b)<br /> {//exchange a and b<br /> T temp = a;a = b;b = temp;<br /> }</p> <p>//一个测试程序<br /> int main()<br /> {<br /> char list[]="abc";<br /> Perm(list,0,4);<br /> return 0;<br /> }</p> <p>

递归解决问题和非递归解决问题的一个对比

对任意一个数，求它的除1外的奇数约数。比如，135，它的全部奇数约数（1除外）为：3，5，9，15，27，45，135。
我编了一个程序，思路是这样的：
1.首先求出它的全部奇数素数因子，比如135的全部奇数素数因子为3，3，3，5
2.用这些因子两两，三三，四四……相乘得出奇数约数
第一步的思路比较清楚，第二步算的时候写循环比较繁复，并且输出为：
3 3 3 5 9 9 15 9 15 15 27 45 135有重复数

我的非递归版本：

#include<vector><br /> #include<iostream><br /> using namespace std;<br /> vector<long>Factorization (long M)<br /> {<br /> vector<long> ret;<br /> long k, mul;<br /> vector<long>::size_type i, j, t, n, step;<br /> //这部分求奇数素数因子，存在vector里面<br /> for (k = 2; k <= M; k++)<br /> {<br /> if (M % k == 0)<br /> {<br /> M = M / k;<br /> if (k % 2 != 0)<br /> ret.push_back (k);<br /> k = 2;<br /> }<br /> }<br /> n = ret.size();<br /> //如果有奇数因子，两两，三三，四四……相乘得出奇数约数<br /> if (n != 0)<br /> {<br /> for (step = 1; step <= n - 1; step++)//这往下，复杂罗嗦，现在叫我想当时是怎么想出来的都有点难<br /> {<br /> for (i = 0; i < n - step; i ++)<br /> {<br /> for (j = i + step; j <= n - 1; j = j + step)<br /> {<br /> mul = ret[i];<br /> for (t = j - step + 1; t <= j; t++)<br /> mul *= ret[t];<br /> ret.push_back (mul);<br /> }<br /> }<br /> }<br /> }<br /> for (i = 0; i < ret.size(); i ++)<br /> cout << ret[i] << " ";<br /> return ret;<br /> }</p> <p>int main()<br /> {<br /> Factorization(135);</p> <p> return 0;<br /> }<br />

csdn成员mstlq的递归版本（其中注释是我现在加进去的）：

原程序在：http://topic.csdn.net/u/20100131/23/1bb2d017-4d0a-4634-a28b-00ad3dad81f2.html

#include <iostream><br /> #include <string><br /> #include<memory.h><br /> using namespace std;<br /> unsigned int priDivs[32];//存放奇数素数因子，不计重复<br /> unsigned int divCnts[32];//记录相应素数因子的个数<br /> unsigned int divC;//记录素数因子的重数，不计重复</p> <p>void init()<br /> {<br /> memset(priDivs,0,32*sizeof(unsigned int));<br /> memset(divCnts,0,32*sizeof(unsigned int));<br /> divC=0;<br /> };<br /> void getPriDivs(unsigned int n)<br /> {<br /> --divC;<br /> while(n%2==0) n/=2;<br /> for(unsigned int i=3; i<=n; i+=2) {<br /> if(n%i==0) ++divC;<br /> while(n%i==0) {<br /> priDivs[divC]=i;<br /> ++divCnts[divC];<br /> n/=i;<br /> }<br /> }<br /> ++divC;<br /> return ;<br /> };</p> <p>void showOddDivs(unsigned int pro,unsigned int dep)<br /> {<br /> if(dep==divC)//如果递归深度达到奇数素数的个数，如果预乘子为1，则输出提示；否则输出结果<br /> (pro==1)? (cout<<"所有奇约数是：/n") : (cout<<pro<<'/t');<br /> else<br /> for(unsigned int i=0;i<=divCnts[dep];++i,pro*=priDivs[dep])<br /> showOddDivs(pro,dep+1);//依次求除第一个奇数素数外后面部分的奇数的乘积；<br /> //第一个奇数素数的一重积与后面部分的积；..第一个因素的divCnts[dep]重积与后面部分的奇数的乘积<br /> return;<br /> }<br /> void Factorization(unsigned int n)<br /> {<br /> init();<br /> getPriDivs(n);<br /> showOddDivs(1,0);<br /> return ;<br /> }<br /> int main()<br /> {<br /> Factorization(1000000000);<br /> return 0;<br /> }<br />

对比这两个程序可知：第二个比第一个精短很多，效率上也更快；逻辑上也更容易理解。

   可见，要是善于使用递归，威力无穷。但也不是绝对的，递归的程序实现起来不如递归的思想那般简洁。思想上，递归简洁易懂；实现上，对计算机的时空开销，递归有时大得惊人：如果上面那个求n阶台阶的行走方法数采用递归，在计算f(10)时，f(3)的值被计算21次，在计算f(30)时，f(3)的值要被计算317877次（这个分析可由fibonacci数列推出），并且递归函数执行过程中所声明的变量是创建于运行时堆栈，并且直到该函数结束前变量一直存在，在时间和空间上，这个额外的开销相当恐怖。

/*<br /> **用递归方法计算n阶台阶行走方法数<br /> */<br /> long f(int n)<br /> {<br /> if(n == 1)<br /> return 1;<br /> if(n == 2)<br /> return 2;<br /> return f(n-1)+f(n-2);<br /> }

      一般像上面这种递归调用是递归函数所执行的最后一项任务时，我们称这种递归为尾部递归(tail recursion),可以把尾部递归函数很容易的改写成一个简单的循环，完成相同的任务，以避免运用递归可能带来的的大的时空开销。

/*<br /> **用迭代方法计算n阶台阶行走方法数<br /> */</p> <p>long f(int n)<br /> {<br /> long fn = 1;<br /> long f1 = 2;<br /> long f2;</p> <p> while(n > 2)<br /> {<br /> n--;<br /> f2 = f1;<br /> f1 = fn;<br /> fn = f2 + f1;<br /> }</p> <p> return fn;</p> <p>}