漢諾塔和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 或者參考其他資料。
如果博客中有什么不正確的地方，還請多多指點。 謝謝觀看。。。
新聞熱點
疑難解答
