遞歸方法求解該類問題，是一種簡單的思維方法，通常比使用迭代方法更簡單。但是，遞歸方法也有劣勢。此處以典型的漢諾塔問題（Tower of Hanoi）為例給予說明。

漢諾塔是根據一個傳說形成的數學問題，最早是由法國數學家愛德華·盧卡斯提出。

有三根桿子 A，B，C 。A 桿上有 N 個 $(N>1)$ 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 桿：

1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。

問：如何移動？最少要移動多少次？

下面鏈接是一個漢諾塔問題的交互操作程序，讀者可以通過操作，嘗試解決此問題。https://www.mathsisfun.com/games/towerofhanoi.html

漢諾塔問題，以及之前遇到過的階乘、斐波那契數列等，都是分治思想的典型應用。

對于漢諾塔問題，解決方法如下，如圖 5.1.1 所示。

圖 5.1.1 漢諾塔問題的求解過程

假設 A 柱上最初的盤子總數為 $n$ 。

• 當 $n=1$ 時，只要將編號為 1 的圓盤從 A 直接移至 C 上即可。
• 否則，執行如下三步：
  1. 用 C 柱做過渡，將 A 柱上的 $(n?1)$ 個盤子移到 B 柱上；
  2. 將 A 柱上最后一個盤子直接移到 C 柱上；
  3. 用 A 柱做過渡，將 B 柱上的 $(n?1)$ 個盤子移到 C 柱上。

由上述求解過程可知，漢諾塔問題符合分治算法的遞歸求解要求。

【算法步驟】

1. 如果 $n=1$ ，則直接將編號為 1 的圓盤從 A 移到 C，遞歸結束。
2. 否則：
   • 遞歸，將 A 上編號為 1 至 $n?1$ 的圓盤移到 B，C 做輔助塔；
   • 直接將編號為 n 的圓盤從 A 移到 C；
   • 遞歸，將 B 上編號為 1 至 $n?1$ 的圓盤移到 C，A 做輔助塔。

【算法描述】

//定義搬動操作函數 move(A, n, C) ，將編號為 n 的圓盤
// 從 A 移到 C。
//用全局變量 m 對搬動次數計數
int m = 0;
void move(char A, int n, char C){cout << ++m <<"," << n << "," << A << "," << C << endl;
}void Hanoi(int n, char A, char B, char C){//將 A 上的 n 個圓盤移到 C 上，B 做輔助塔if (n == 1) move(A, 1, C); //將編號為 1 的圓盤從 A 移到 Celse {Hanoi(n-1, A, C, B); //將 A 上不編號為 1 至 n-1 的圓盤移到 B ，C 做輔助塔move(A, n, C);  //編號為 n 的圓盤從 A 移到 CHanoi(n-1, B, A, C); //將 B 上編號為 1 至 n-1 的圓盤移到 C，A 做輔助塔}
}

【算法分析】

假設圓盤數量為 $n$ 時，移動圓盤的時間復雜度為 $T(n)$ ；圓盤數量為 $(n?1)$ 時時間復雜度 $T(n?1)$ 。根據算法，要將 $n?1$ 個圓盤從 A 移到 B（借助 C），然后將這些圓盤從 B 移到 C（借助 A）。再加上將編號為 n 的圓盤從 A 移到 C 所花費的常數時間（用 $c$ 表示）則得到遞推公式：
$$T(n)=2T(n?1)+c$$
根據遞推公式，有：
$$\begin{array}{rl}T(n)& =2T(n?1)+c=2[2T(n?2)+c]+c\\ & =2^{2}T(n?2)+[2+1]c=2^2[2T(n?3)+c]+[2+1]c\\ & =2^{3}T(n?3)+[2^2+2+1]c\\ & ?\\ & =2^{n?1}T(1)+[2^{n?2}+?+2^0]c\end{array}$$
顯然 $T(1)=c$

上述漢諾塔問題算法的時間復雜度是 $O(2^n)$ ，即指數階的時間復雜度。

在第 2 章（因為本文是我編寫的《數據結構》考研復習講義中的節選，所以，讀者在閱讀的時候，如果遇到類似的表述，勿要深究）已經研究過這種指數階時間復雜度，在一般情況下， 無法用于解決實際問題，不是一個有效的算法。

對于漢諾塔問題的時間復雜度分析，也可以通過計算移動盤子的次數得到，借用前面給出的交互演示程序和算法，可知：

圓盤數量 $n$	移動圓盤次數
1	$1=2^1?1$
2	$3=2^2?1$
3	$7=2^3?1$
$?$	$?$
n	$2^n?1$

因此時間復雜度為 $O(2^n)$ 。