漢諾塔是遞歸教學的經典題目:有三根柱子,目標是把 n 個由大到小堆疊的圆盤從起始柱全部搬到目標柱,規則是每次只能搬一個,且任何時刻都不能把小盤放在大盤上面。
<script language="javascript">
var han = function (disc, src, aux, dst) {
if (disc > 0) {
han(disc - 1, src, dst, aux); // 先把上面 n-1 個從 src 搬到暫存柱 aux
document.writeln("move disc " + disc + " from " + src + " to " + dst + "<br/>");
han(disc - 1, aux, src, dst); // 再把那 n-1 個從 aux 搬到目標柱 dst
}
};
han(10, "src", "aux", "dst");
</script>
遞歸的優雅之處在於,它把「搬 n 個盤」拆解成兩個「搬 n-1 個盤」的子問題,中間夾一次合法的直接搬移:
第一步,把最上面的 n-1 個盤從 src 移到 aux(暫時借用 dst 當緩衝)。此時 src 底部最大的那個盤露出來了。
第二步,把最大的盤從 src 直接移到 dst。因為它是目前最大的,放到空的 dst 上必然合法。
第三步,把那 n-1 個盤從 aux 移到 dst(此時 src 已空,可當緩衝)。
注意兩次遞呼叫中參數的交換順序:han(disc-1, src, dst, aux) 是把 dst 與 aux 對調,代表「以 dst 為暫存」;而 han(disc-1, aux, src, dst) 則是以 aux 為新起點、src 為暫存。這個參數順序正是整段程式碼最容易被寫錯的地方。
終止條件是 disc > 0:當 disc 為 0 時什麼都不做,遞歸自然收斂。
搬移的總步數為 2n − 1。以 n = 10 而言是 1023 步,n = 64 則是 1844 億億步——這正是這個問題用來說明「遞歸優雅 ≠ 高效」的經典例子:程式碼只有四行,但時間複雜度是指數級的,且這是問題本身的性質,任何演算法都無法改善。