递归能解决什么问题，当一个问题涉及到规模，并且规模变化问题性质不改变并且有问题出口的情况下，我们自然而然的想到递归。
那又怎么实现递归，许多文章里大致总结了递归程序分为两部分，分别为递归边界部分和递归式部分，了解了这两个部分，一个递归程序基本也就完成。
这个部分，更多是循环渐进的应用实例，来帮大家解决问题。
基础
全排列问题：
给出一个n为1到9的整数，试求1~n这n个数的全排列，并按从小到大输出。
分析题意不妨设用数组p来储存这n个数的排列，要排第n个数只要把前n-1个排好，以此类推，明显该问题可以想象成递归问题。
1.那递归边界怎么确定：该问题排n个，明显到排第n+1个的时候就可以结束，递归边界如下:
if(index==n+1) //递归边界 { for(int i=1;i<n+1;i++) cout<<p[i]; cout<<endl; return ; }
2.如何确定递归式
确定递归式的时候，不妨就想象现在正在排第x位，这一位有什么要求，只要数字不是前面出现的即可，排好了就排下一个，这时候我们如果用另外一个t数组的标记有哪些数字还没有排，就可以写成:
else{ for(int i=1;i<n+1;i++) { if(!t[i]) //查找未排的 { p[index]=i;t[i]=true;//排这一位 permutation(index+1); // 递归排下一位 t[i]=false; // 回溯 }
这里需要注意的是如果用了t数组来标志的话一般有回溯要求，可以自己理解为什么要回溯。
最后总程序如下：
#include<iostream> using namespace std; const int maxn=11; int n,p[maxn],t[maxn]={false}; void permutation(int index) { if(index==n+1) //递归边界 { for(int i=1;i<n+1;i++) cout<<p[i]; cout<<endl; return ; } else{ for(int i=1;i<n+1;i++) { if(!t[i]) { p[index]=i;t[i]=true; permutation(index+1); // 递归式 t[i]=false; // 回溯 } } } } int main() { cin>>n; permutation(1); return 0; }
应用
n皇后问题:会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将n个皇后放在棋盘上（有n * n个方格），使它们谁也不能被吃掉！
实际上，n皇后可以转化为上面全排列的子问题，不如以顺序记录棋子的横坐标，对应排列数字依次就为横坐标的对于的列坐标，每一组排列确定了一组排放棋子位置。
显然递归边界依旧不变，只是在写递归式的时候，要筛选掉不符合n皇后规则的排序，所以这个问题，只是在全排列问题的递归式部分加上约束条件即可，如下：
else{ for(int i=1;i<n+1;i++) { if(!t[i]) { int a=1; for(int j=1;j<index;j++) //约束条件 { if((index-j)==abs(i-p[j])) a=0; } if(a){ p[index]=i;t[i]=true; queen(index+1); t[i]=false; } } }
下面是结果：
#include<iostream> #include<algorithm> using namespace std; const int maxn=11; int n,p[maxn],t[maxn]={false}; void queen(int index) { if(index==n+1) { for(int i=1;i<n+1;i++) cout<<p[i]; cout<<endl; return ; } else{ for(int i=1;i<n+1;i++) { if(!t[i]) { int a=1; for(int j=1;j<index;j++) //判断这个点是否可行 { if((index-j)==abs(i-p[j])) a=0; } if(a){ p[index]=i;t[i]=true; queen(index+1); t[i]=false; } } } } } int main() { n=8; queen(1); return 0; }
进阶
上面那个问题其实得到的结果是多个，那如果只要其中结果的一个又如何中途退出?
八皇后问题：
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2…b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
这和上面的n皇后问题几乎一致，只是只要其中第几个结果，这就涉及到退出问题，在我写的程序里，除了递归边界和递归式，还加了一个计数退出段。
#include<iostream> #include<string> #include<algorithm> using namespace std; int a[9],b[9]; int n; int sum=0; void generate(int index){ if(index==9) { sum++; //递归边界 if(sum==n){ for(int i=1;i<9;i++) cout<<a[i]; cout<<endl; } return ; } else if(sum==n) { //退出条件 return; } else{ for(int i=1;i<9;i++){ if(!b[i]) { int flag=1; for(int j=1;j<index;j++) //判断这个点是否可行 { if((index-j)==abs(i-a[j])) flag=0; } if(flag){ a[index]=i;b[i]=true; generate(index+1); b[i]=false; } } } } } int main(){ int num; cin>>num; for(int i=0;i<num;i++){ cin>>n; for(int j=1;j<9;j++)b[j]=false;sum=0; generate(1); } return 0; }
结果：
