汉诺塔和N皇后问题
汉诺塔和N皇后问题算是计算机中经典的递归算法问题了。几乎讲到递归的时候都会想到这两个问题，那么我们就来看一下这两个经典的递归问题：
首先来看一下汉诺塔问题，汉诺塔源于一个古老的印度传说： 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 当然我们不是来听故事的，我们将这个描述构造成计算机问题： 有三根柱子，这里编号为 A 、 B 、 C，一开始在A柱子上有从下往上按照从大到小顺序摆放的64个圆盘，给的任务是将这些圆盘以同样的大小顺序摆放到C柱子上，可以借助任何柱子作为中转，但是限制条件是： 1.在小圆盘上不能放大圆盘。 2.在三根柱子之间一回只能移动一个圆盘。 3.只能移动在最顶端的圆盘。
怎么解决呢？我们先假定A柱子上面的圆盘个数为2个，这里为了方便表述将圆盘编号为a、b（a圆盘在上面，b圆盘在下面），那么就先将a从A柱子移动到B柱子上面，再将b从A柱子移动到C柱子上面，再将a从B柱子移动到C柱子上面，这样就完成了，总共移动了3次圆盘。 接下来假定圆盘数为3个（编号为a、b、c），我们继续，移动步骤如下：
a（A）—> C // A柱子上的圆盘a从A柱子移动到C柱子，下同 b（A）—> B a（C）—> B c（A）—> C
上面是第一轮，接下来是第二轮：
a（B）—> A b（B）—> C a（A）—> C
我们观察：当A柱子或者B柱子只剩下一个圆盘的时候，就直接将这个圆盘移动到C柱子，上面步骤的第一轮就是先将A柱子上面的n-1（假设A柱子一共有n个圆盘）个圆盘借助其它柱子按照同样的大小顺序移动到B柱子（第一轮）这样B柱子上面就有n-1个圆盘，然后将A柱子上面的最后一个最大的圆盘直接移动到C柱子上面，接下来是将B柱子上面的n-1个圆盘借助其它柱子按照同样的大小顺序移动到C柱子上面（第二轮）。之后重复这两轮操作，直到圆盘全部转移到C柱子上。
下面直接给出源程序：
#include <iostream>
using namespace std;
int n; // 总的圆盘数
int sum; // 移动的总次数
void hanoi(int n, char A, char B, char C) // 将A柱子上面的圆盘移动到C柱子
{
if(n == 1) //如果A柱子上面只有一个柱子，那么直接移动
{
cout << "第 " << ++sum << " 步：" << A << "---->" << C << endl;
return ;
}
hanoi(n - 1, A, C, B); // 第一轮: A柱子上面的n-1个圆盘转移到B柱子上面
cout << "第 " << ++sum << " 步：" << A << "---->" << C << endl; // 进行移动调整
hanoi(n - 1, B, A, C); // 第二轮：B柱子上面的n-1个圆盘移动到C柱子上面
}
int main()
{
cin >> n;
hanoi(n, 'A', 'B', 'C');
cout << "移动次数：" << sum << endl;
return 0;
}运行结果：
建议不要轻易地输入过大的数字，这是输入 20 的运行结果：
我们继续看下一个问题：N皇后问题，先看一下经典的8皇后问题：
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
这道题我们可以利用循环去做，不过那样的话就要写一个8重循环嵌套，并且还要对各种情况进行判断，显然不是一个好方法，这个时候就轮到递归来起作用了：
首先如果要8个皇后不能互相吃掉，这8个皇后一定要在不同的8行，并且当我们在摆放第x个皇后的时候，第x个皇后一定不能和前面的x-1个皇后互吃，那么，我们把第x个皇后摆放在第x行，并且再对；列进行判断。ok，这就是这道题递归的基本思路，下面是关键代码：
void solve(int x) // 对第x个皇后进行摆放
{
int j;
for(int i = 0; i < 8; i++) // 第x个皇后最多可能有8个列可供选择
{
for(j = 0; j < x; j++) // 对第x个皇后和之前已经摆放好的的皇后进行检测是否会互吃
{
if(会发生互吃)
{
break; // 如果会互吃，那么不能摆在第i列，尝试下一列
}
}
if(j == x) // 如果j和x相等证明第x个皇后和前面的皇后不会互吃
{
save[x] = i; // 不会互吃的话的话就先选择这一列
solve(x+1); // 继续对第x+1个皇后进行摆放
}
}
}上面就是基本的递归思路（注意这里的皇后是从第0个开始，行和列也是从0开始），但是我们再看看，这个递归函数还没有出口，什么时候是递归函数的出口呢，当然是将所有皇后都摆放完成的时候，并且我们要添加判断互吃的代码：
void solve(int x) // 对第x个皇后进行摆放
{
int j;
if(x == 8) // 当0~7这8个皇后全部摆放完成之后，结束递归并且输出
{
sum++; // 可能的情况的总数加一
for(int i = 0; i < 8; i++)
{
cout << save[i] + 1<< " "; // 输出的时候行和列是从1开始
}
cout << endl;
return ;
}
for(int i = 0; i < 8; i++) // 第x个皇后最多可能有8个列可供选择
{
for(j = 0; j < x; j++) // 对第x个皇后之前的皇后进行检测是否会互吃
{
if(save[j] == i || abs(save[j] - i) == abs(j - x)) // 同在一列或者在一条对角线上会互吃
{
break; // 如果会互吃，那么不能摆在第i列，尝试下一列
}
}
if(j == x) // 如果j和x相等证明第x个皇后和前面的皇后不会互吃
{
save[x] = i; // 不会互吃的话的话就先选择这一列
solve(x+1); // 继续对第x+1个皇后进行摆放
}
}
}整个问题的核心代码就是这些了，下面给出完整代码：
#include <iostream>
#include <cmath>
const int N = 100; // 最多100个皇后
using namespace std;
int n = 8; // 皇后总数
int sum; // 可能的皇后摆放情况总数
int save[N]; // 储存所有皇后摆放的列的信息数组
void solve(int x) // 对第x个皇后进行摆放
{
int j;
if(x == n) // 当0~7这8个皇后全部摆放完成之后，结束递归并且输出
{
sum++; // 可能的情况的总数加一
for(int i = 0; i < n; i++)
{
cout << save[i] + 1<< " "; // 输出的时候行和列是从1开始
}
cout << endl;
return ;
}
for(int i = 0; i < n; i++) // 第x个皇后最多可能有8个列可供选择
{
for(j = 0; j < x; j++) // 对第x个皇后之前的皇后进行检测是否会互吃
{
if(save[j] == i || abs(save[j] - i) == abs(j - x)) // 同在一列或者在一条对角线上回互吃
{
break; // 如果会互吃，那么不能摆在第i列，尝试下一列
}
}
if(j == x) // 如果j和x相等证明第x个皇后和前面的皇后不会互吃
{
save[x] = i; // 不会互吃的话的话就先选择这一列
solve(x+1); // 继续对第x+1个皇后进行摆放
}
}
}
int main()
{
solve(0); // 从第0个皇后开始摆放
cout << "所有可能的情况: " << sum << endl;
}这就是8皇后问题的解法，那么N皇后和8皇后其实是一个原理，针对这题运用的递归其实是深度优先搜索（Depth-First-Search）的思想，有兴趣的小伙伴可以看一下这篇博客：http://blog.csdn.net/hacker_zhidian/article/details/54773762 或者参考其他资料。
如果博客中有什么不正确的地方，还请多多指点。 谢谢观看。。。