河內塔是經典遞迴問題:將 N 個圓盤從柱子 A 移至柱子 C,借用柱子 B,規則:一次只能移一個圓盤,大盤不能放在小盤上方。
<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
}
};
// 測試:10 個圓盤
han(10, "src", "aux", "dst");
</script>
han(3, A, B, C) ├─ han(2, A, C, B) │ ├─ han(1, A, B, C) → move disc 1 from A to C │ ├─ move disc 2 from A to B │ └─ han(1, C, A, B) → move disc 1 from C to B ├─ move disc 3 from A to C └─ han(2, B, A, C) ├─ han(1, B, C, A) → move disc 1 from B to A ├─ move disc 2 from B to C └─ han(1, A, B, C) → move disc 1 from A to C
2^n - 1(n 為圓盤數)此範例展示遞迴解決分治問題的典型模式:將大問題分解為相同結構的子問題,配合終止條件(disc === 0)完成求解。