二、递归
概念：什么是递归？
是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 递归算法要求
递归算法所体现的“重复”一般有三个要求：
（1）每次调用在规模上都有所缩小(通常是减半)；
（2）相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
（3）在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而必须有一个明确的递归结束条件，称为递归出口。
递归技术分为两种类型：
(1)基于归纳的递归； (2)基于分治的递归。 递归的应用场合：
（1）数据的是按递推方式定义的（Fibonacci函数等） （2）问题求解过程适于递归（数的排列问题等）
（3）数据或问题对象的结构形式是按递归定义的（树图的遍历，搜索回溯）
递归应用举例：求n!；求斐波那契序列；汉诺塔问题；……
递归的缺点：
递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
（一）数据的定义是按递推定义的 例1：求n!，关键：f(n)=n*f(n-1) int f(int n)
9
{ }
例2：求斐波那契序列第n项值，关键：F(n)=F(n-1)+F(n-2) int Fibonacci(int n) { }
小结：此类问题的解题思路是运用了数学归纳法（什么是数学归纳法？）的基本思想，先求出问题规模n在边界值（通常是最小值）时候的解，再依据f(n)与前项（即f(n-1)）的递推关系，给出f(n)的运算式。
例3：计算m个A，n个B可以组合成多少个不同排列的问题。
int f(int m, int n) {
if(m==0 || n==0) return 1;
return _（m+n）*(m+n-1)/(m*n)f(m-1,n-1); 或if (n==0 || n==1) return n;
return Fibonacci(n-1)+ Fibonacci(n-2); if (n==0 || n==1) return 1; return n*f(n-1);
_f(m-1,n)+f(m,n-1); }
（二）问题的求解过程适于递归
递归的思想关键在于将大任务划分成小任务，要求这些小任务与大任务有相似性。 下面用几个简单的问题来理解递归思想： 例1：输出0~9这10个数
循环法： for ( x = 0; x<=9; x++ )
{ } {
printf( “%d\\n”, x );
递归法： void fp( int begin, int end)
printf (“%d\\n”, begin); //先打印再递归 if ( begin < end )
fp(begin+1, end);
等价于： void fp ( int begin, int end)
if (begin > end) return; //递归的出口
10
}
fp ( begin, end-1); printf (“%d\\n”, end);
//先递归再打印
例2：累加求和1+2+3+……+100
循环法：for ( x=1, sum=0; x<=100; x++ ) 递归法：int fsum ( int begin, int end)
{ }
if (begin == end)
return begin; //递归的出口
return begin + fp ( begin+1, end);
sum = sum+x;
从上述两例可以看出，递归思想的精髓在于将大任务划分为与它相似的小任务，这要如何体现？就体现在函数的“参数”变化上！
例3：汉诺塔问题
递归的思路：是将n个盘的问题转化为n-1个盘的问题，再将n-1个盘的问题转化为n-2个盘??,最后转化为处理1个盘的问题。 void hanoi(int n,char A,char B,char C) {
if (n==1) }
move (A,C); else {
hanoi(n-1,A,C,B); //将n-1个盘经过C柱中转搬到B柱 move (A,C); //将第n个盘从A柱搬到C柱
hanoi(n-1,B,A,C); //将n-1个盘经过A柱中转搬到C柱 }
例4：生成1～n的全排列（分为数字可重复和不可重复）
方法一思路：建立一个由1～n组成的数组，利用任务划分，将n个数的排列问题转化为n-1个数的排列问题。具体做法：将数组中的每个数都分别与第1个数交换，然后再将剩余的数进行全排列。
void Swap(int& a, int& b) // 交换a和b {
int temp = a; a = b; b = temp;
11
}
void Perm(int list[], int k, int m) //生成list [k：m ]的所有排列方式 {
int i;
if (k == m)
{ //输出一个排列方式
for (i = 0; i <= m; i++)
printf(“%d”,list[i]); printf(“\\n”); }
else // list[k：m ]有多个排列方式
// 递归地产生这些排列方式 for (i=k; i <= m; i++) {
Swap (list[k], list[i]); //将当前序列中的每个数与第一个数交换 Perm (list, k+1, m); //进入递归对后序的数列进行全排列 Swap (list [k], list [i]); //恢复交换前的状态 }
}
int main() {
int s[]={1,2,3}; Perm(s, 0, 2); return 0; }
方法二思路：将n位数的排列划分成对每一个1位数的排列问题，对每个位置利用循环来尝试填数；填入一个数后，再利用递归去填入后续位置的数，?直至填完n个位置。
void print_permutation(int n, int *A, int pos) {
int i,j; if (pos==n)
for (i=0; i for (i=1; i<=n; i++) //尝试从1～n 个数中找出填入A[pos]的数i { int ok=1; for(j=0; j if (A[j]==i) ok=0; 12 else