递归就是函数间接的调用自己， 它的实现基于函数参数传递的栈机制， 每次递归递归调用都会多一个栈帧——和简单的函数调用并没有什么不同 (都是使用了调用栈)。调用自己和调用其它函数并没有本质的区别， 都是建立新栈帧， 传递参数并修改当前代码行。在函数体执行完毕后删除栈帧， 处理返回值并修改当前代码行。
递归在数据结构中占有很重要的，特别是， 树和图的建立， 和遍历。 使用递归能使代码更清晰， 更简洁， 但是调试时会很麻烦， 所以， 对于递归要熟练应用且小心应用。
下面是几个简单的应用举例：
<1>
Fibonacci数列 1 n = 0， 1
F(n) =
F(n-1) + F(n-2) n>=2
1 #include<iostream> 2 using namespace std; 3 4 int fibonacci(int n) 5 { 6 if(n<=1) return 1; 7 return fibonacci(n-1) + fibonacci(n-2); 8 } 9 10 int main() 11 { 12 int n; 13 while(scanf("%d", &n)!=EOF) 14 { 15 n = fibonacci(n); 16 printf("%d ", n); 17 } 18 return 0; 19 }
//较优化的Fibonacci数列。 #include<cstdio> using namespace std; int a[100]; int Fib(int n) { if (n <= 1) return a[1]=1; else { a[n] = Fib(n - 1) + Fib(n - 2); return a[n]; } } int main() { int n; while(scanf("%d", &n)!=EOF) { n = Fib(n); printf("%d ", n); } return 0; }
此题 有更快的解法， 用矩阵快速幂求解 构造2*2 的矩阵{ 1， 1， 1， 0}； 这个代码后面在矩阵的应用中会给出。
其实斐波那契数列是一个十分有趣的数列， a[n+2] - a[n+1] - a[n] = 0 。 如果我们令 q^(n+2) - q^(n+1) - q^n = 0。
可以解出 q 的两个值， 然后 利用这两个值，和前两项列出一个二元一次方程，解出系数。这样就求出了 斐波那契数列的通项！
斐波那契数列还具有周期性， 具有一些循环性的性质。
<2>. 汉诺塔问题， 有三个钢针， A， B， C， A 上有n个圆盘， 大的在下面， 小的在上面， 你可以借借助B针， 把A针上的圆盘移到C盘上，（任何时候较大盘都不能放在较小盘上）， 对于一个不太大的n（据说n等于64时， 每秒移动一次， 宇宙会在完成的那一瞬间毁灭， 嘿嘿！！）， 请给出移动次数最少的解决方案！
1 #include<stdio.h> 2 3 void Move(int n, char A, char B) 4 { 5 printf("Move disk %d from %c to %c ", n, A, B); 6 } 7 8 void hanoi(int n, char A, char B, char C) 9 { 10 if(n==1) Move(1, A, C); 11 else 12 { 13 hanoi(n-1, A, C, B); 14 Move(n, A, C); 15 hanoi(n-1, B, A, C); 16 } 17 } 18 19 int main() 20 { 21 int n; 22 while(scanf("%d", &n)!=EOF, n) 23 { 24 hanoi(n, 'A', 'B', 'C'); 25 } 26 return 0; 27 }
程序解释： 当n==1时， 很显然， 直接把它从A针上移动到C针上就好了。即： if（n==1） Move（1， A， C）；
当 n > 1时， 我们可以这样考虑， 我们可以把A针上面的 n-1个盘借助C针， 移动到B针上，然后把A针上的盘移动到C盘上。
然后再把B盘上的n-1个盘， 借助于A盘， 移动到C盘。
很显然， 移动n个盘的问题就转化成了移动n-1个盘的问题。依次类推， 此问题最终变成求解移动一个盘的问题。
<3>并非一切递归函数都能用非递归方式定义， 也就是说， 有些函数只能用递归的形式进行定义或描述。 例如 双递归函数——Ackerman函数。当一个函数以及它的一个变量是由函数自身定义时， 称这个函数是双递归函数。 Acerman函数 A(n， m)有两个独立的整变量m>=0和n>=0, 其定义如下：
A（1， 0） = 2
A(0， m) = 1 m>=0
A(n, 0) = n + 2 n>=2
A(n, m) = A(A(n-1, m), m-1) n, m >=1 。 这个函数增长快的惊人。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 5 typedef long long LL; 6 LL ans = 0; 7 8 LL A(LL n, LL m) 9 { 10 if(n==1&&m==0) return 2; 11 if(n==0&&m>=0) return 1; 12 if(n>=2&&m==0) return n+2; 13 return A(A(n-1, m), m-1); 14 } 15 16 int main() 17 { 18 LL a, b; 19 while(scanf("%lld%lld", &a, &b)!=EOF) 20 { 21 ans = 0; 22 ans=A(a, b); 23 printf("%lld ", ans); 24 } 25 return 0; 26 } 27
<4> 全排列问题。1~n 的全排列。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n = 0; 6 int list[100]; 7 void perm(int list[], int k, int m) 8 { 9 int i;//显示输出 10 if(k>m) 11 { 12 for(i=0; i<=m; i++) 13 printf("%d", list[i]); 14 printf(" "); 15 n++; 16 } 17 else 18 { 19 for(i=k; i<=m; i++) 20 { 21 swap(list[k], list[i]); //交换第k个数和第i个数，并把后面的数全排列 22 perm(list, k+1, m);//全排列 k+1到m 23 swap(list[k], list[i]);//第一步的逆操作，使数列保持不变，以避免重复。 24 } 25 } 26 } 27 28 int main() 29 { 30 int T; 31 while(scanf("%d", &T)!=EOF) 32 { 33 for(int i=0; i<T; i++) 34 list[i] = i+1; 35 perm(list, 2, T-1); 36 printf("total:%d ", n); 37 } 38 return 0; 39 }
此问题有多种解法， 大都应用了递归方法。<algorithm>里面也包含了生成全排列的算法
next_permutation(begin, end)；
<5>整数划分问题
如 4 可以划分为
4
3 + 1
2+ 2 ， 2+1+1
1+1 + 1+1
在整数n的所有不同 的划分中， 将最大加数n1 不大于 m 的划分记作 q（n， m）。可以建立q(n， m) 的如下递归关系。
(1) q（n， 1） = 1 ， n>=1
加数只能全部是 1
（2）q（n， m）=q（n， n）， m>=n
m>=n, n 不可能有比n自身还大的加数。
（3） q（n， n）= 1 + q（n， n - 1）
整数n的划分 分成 1 + （n-1） 和 q（n， n-1）两种情况
(4) q（n， m） = q (n，m-1) + q（n-m， m）, n>m>1
分为最大加数 n1 <=m-1时的情况， 和 n1==m时的情况。 而n1==m的情况 刚好是q（n-m，m）。（如果不太明白请结合实例理解）。
q（n, m） = 1 , n=1, m=1
q(n, m) = q(n, n) n<m
q(n, m) = 1 + q(n, n-1) n=m
q(n, m) = q(n, m-1) + q(n-m, m)
1 #include<iostream> 2 using namespace std; 3 4 int q(int n, int m) 5 { 6 if((n<1)||(m<1)) return 0; 7 if((n==1)||(m==1)) return 1; 8 if(n<m) return q(n, n); 9 if(n==m) return q(n, m-1) + 1; 10 return q(n, m-1) + q(n-m, m); 11 } 12 13 int main() 14 { 15 int a, ans = 0; 16 while(scanf("%d", &a)!=EOF) 17 { 18 ans=q(a, a); 19 printf("%d ", ans); 20 } 21 return 0; 22 }
此问题也有另外一种特别巧妙的解决办法： 生成函数。
《5》递归求最大公因数和最小公倍数
1 #include<iostream> 2 using namespace std; 3 4 //递归， 求最大公因数 5 int gcd(int a, int b) 6 { 7 return b ? gcd(b, a%b) : a; 8 } 9 10 int main() 11 { 12 int n, m; 13 while(scanf("%d%d", &n, &m)!=EOF) 14 { 15 printf("%d ", gcd(n, m)); 16 } 17 return 0; 18 }
1 #include<iostream> 2 using namespace std; 3 4 //递归， 求最小公倍数 5 int gcd(int a, int b) 6 { 7 return b ? gcd(b, a%b) : a; 8 } 9 10 int main() 11 { 12 int n, m; 13 while(scanf("%d%d", &n, &m)!=EOF) 14 { 15 printf("%d ", n/gcd(n, m)*m); 16 } 17 return 0; 18 }
《6》半数集问题
(1) n set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6，16，26，126，36，136}。
半数集set(6)中有6个元素。
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
设set(n)中的元素个数为 F（n） ，则显然有：
F（n） = 1 + F（1） + F（2） + …… + F(n/2)
|
第一次半数集 |
112 |
212 |
312 |
412 |
512 |
612 |
|
忽略原始数字12 |
1 |
2 |
3 |
4 |
5 |
6 |
|
12 |
13 |
14 24，124 |
15 25，125 |
16 26，126 36，136 |
以 n 为12 为例！
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int a[1005]; 6 7 int comp(int n)//记忆化搜索 8 { 9 int ans = 1; 10 if(a[n]>0) return a[n]; 11 for(int i=1; i<=n/2; i++) 12 ans += comp(i); 13 a[n] = ans; 14 return ans; 15 } 16 17 int main() 18 { 19 memset(a, 0, sizeof(a)); 20 int n; 21 cin>>n; 22 cout<<comp(n)<<endl; 23 return 0; 24 }
《7》http://acm.hdu.edu.cn/showproblem.php?pid=1297（递归+高精度加法）
#include<iostream> #include<cstdio> using namespace std; int main() { int a[1001][101] = {0}; a[0][1] = 1; a[1][1] = 1; a[2][1] = 2; a[3][1] = 4; for(int i=4; i<1001; i++) for(int j=1; j<101; j++) { a[i][j] += a[i-1][j] + a[i-2][j] + a[i-4][j]; a[i][j+1] += a[i][j]/1000000; a[i][j] %= 1000000; } int n; while(scanf("%d", &n)!=EOF) { int k = 100; while(!a[n][k]) k--; printf("%d", a[n][k]); for(int i=k-1; i>0; i--) printf("%06d", a[n][i]); printf(" "); } return 0; }
递归方程： ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,（见代码和分析过程）
分析过程：
设：F(n)表示n个人的合法队列，则：
按照最后一个人的性别分析，他要么是男，要么是女，所以可以分两大类讨论：
1、如果n个人的合法队列的最后一个人是男，则对前面n-1个人的队列没有任何限制，他只要站在最后即可，所以，这种情况一共有F(n-1);
2、如果n个人的合法队列的最后一个人是女，则要求队列的第n-1个人务必也是女生，这就是说，限定了最后两个人必须都是女生，这又可以分两种情况：
2.1、如果队列的前n-2个人是合法的队列，则显然后面再加两个女生，也一定是合法的，这种情况有F(n-2);
2.2、但是，难点在于，即使前面n-2个人不是合法的队列，加上两个女生也有可能是合法的，当然，这种长度为n-2的不合法队列，不合法的地方必须是尾巴，就是说，这里说的长 度是n-2的不合法串的形式必须是“F(n-4)+男+女”，这种情况一共有F(n-4).
怒切此题：
当草滩小恪求出这个递推方程后， 很是得意，，， 于是他便屁颠屁颠的去切这道题去啦。 然而， wang一直陪伴着他。 仔细想一下，Fibonacci数列就已增长的很快， 而且这个数列增长的比Fibonacci数列更快。 所以第1000项会非常的大。所以不用高精度是不行的。
《8》Big String
把A接在B的后面构成新的字符串C。
例如，A＝“^__^”，B＝“T.T”，则C＝BA＝“T.T^__^”。
令A＝B，B＝C，如上例所示，则A＝“T.T”，B＝“T.T^__^”。