河內塔(Tower of Hanoi)是解釋遞迴最經典的例子。規則很簡單:有三根柱子,目標是把整疊圓盤從起始柱搬到目標柱,每次只能搬一個,而且小盤永遠不能疊在大盤上面。
它的優美之處在於:看似複雜的搬運,用遞迴只要三行就能寫完。
<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); // ② 把暫存在 aux 的 n-1 個盤搬到 dst
}
};
han(10, "src", "aux", "dst");
</script>
要搬 n 個盤,直覺上沒人知道第一步該做什麼。但換個角度想:如果你能搬 n-1 個盤,那 n 個盤就解決了。
具體步驟只有三步:
關鍵在於第 ① 步和第 ③ 步的參數順序:han(disc-1, src, dst, aux) 中,第三個參數(auxiliary)填的是 dst,第四個(目標)填的是 aux——也就是把目標與暫存對調。這個交換正是整個演算法能運作的核心。
當 disc 遞減到 0,代表「沒有盤要搬」,什麼都不做直接返回。這就是遞迴的 base case。少了它,函式會無限呼叫自己直到堆疊溢出。
加上步驟計數與錯誤檢查,會更接近實用:
function hanoi(n, from, to, via) {
var moves = [];
(function move(disc, src, aux, dst) {
if (disc <= 0) return;
move(disc - 1, src, dst, aux);
moves.push({ disc: disc, from: src, to: dst });
move(disc - 1, aux, src, dst);
})(n, from, to, via);
return moves;
}
var steps = hanoi(3, 'A', 'C', 'B');
steps.forEach(function (s, i) {
console.log((i + 1) + '. 將直徑 ' + s.disc + ' 的盤從 ' + s.from + ' 移到 ' + s.to);
});
console.log('共 ' + steps.length + ' 步'); // 共 7 步
這個版本把結果收集成陣列而非直接輸出,方便後續做動畫或其他處理——把每一步依序套用到視覺化的柱子上,就是一個河內塔動畫了。