再帰

64枚の円盤のハノイの塔を動かすには 18,446,744,073,709,551,615 回の移動が必要ですが、再帰関数ならその解き方を4行で書けます。

自分自身を呼び出す関数

中に自分の小さな写しをふくむ問題があります。5の階乗は 5! と書き、5 × 4 × 3 × 2 × 1 = 120 です。もう一度見てみましょう。これは 5 × (4 × 3 × 2 × 1)、つまり 5 × 4! です。一般に n! = n × (n − 1)! なので、階乗を計算するには、小さいほうの階乗を計算してかければよいのです。問題を小さくした版に対して自分自身を呼び出して解く関数を、再帰的な関数と言います。

function factorial(n) {
  if (n <= 1) return 1;          // 基底部: ここで止まる
  return n * factorial(n - 1);   // 再帰部: 小さくした問題
}
console.log(factorial(5)); // 120

再帰関数には必ず2つの部分が必要です。基底部（ベースケース）は、もう一度呼び出さなくても直接答えられるほど小さな入力です。ここでは「1の階乗は1」です。再帰部は問題を小さくして、もう一度関数を呼び出します。呼び出しのたびに基底部に近づかなければなりません。そうでないと、たとえばまちがえて factorial(n + 1) と書くと、呼び出しは終わりません。

呼び出しスタック

コンピューターは、終わっていない呼び出しをどうやって覚えておくのでしょうか。factorial(5) が実行されると 5 * factorial(4) にたどりつき、その答えを待たなければなりません。コンピューターは待っている呼び出しをスタックに積みます。スタックとは、最後に置いたものが最初に取り出される山のことです。factorial(4) は factorial(3) を待ち、これが factorial(1) まで続きます。これはすぐに1を返します。するとスタックがほどけていきます。factorial(2) が2を、factorial(3) が6を、factorial(4) が24を返し、factorial(5) が120を返します。

スタックの大きさには限りがあります。基底部にたどりつかない再帰は、場所がなくなるまで呼び出しを積み続け、JavaScriptはエラーで止まります。ChromeとNode.jsでは「RangeError: Maximum call stack size exceeded」というメッセージが出ます。同じ限界があるので、何十万段にもなるとても深い再帰は、ループで書くほうがよいのです。

ハノイの塔

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発表したパズルです。3本の棒があり、1本目の棒に大きさの違う円盤が、いちばん大きいものを下にして積まれています。目標は、山全体を3本目の棒へ移すことです。一度に動かせる円盤は1枚だけで、動かせるのは棒のいちばん上の円盤だけ、大きい円盤を小さい円盤の上に置いてはいけません。

円盤を1枚ずつどこへ動かすかを順に考えていくと、すぐに混乱します。再帰的に考えれば短くすみます。n枚の円盤をAからCへ動かすには、まず上のn − 1枚をAからBへどけます。次に最大の円盤をAからCへ動かします。そしてn − 1枚をBからCのその上へ動かします。n − 1枚を動かすのは1つ小さい同じパズルで、1枚を動かすのが基底部です。3枚なら7回の移動になります。ラボでは、移動のたびに待っている呼び出しのスタックが表示されます。

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7回の移動

n枚の円盤には何回の移動が必要でしょうか。n枚を動かすには、n − 1枚の移動2回に1回を足した手間がかかります。M(n) = 2M(n − 1) + 1、M(1) = 1 です。これで1、3、7、15、31となるので M(n) = 2ⁿ − 1 で、これより少ない手数の解き方はありません。10枚なら1,023回です。64枚なら 2⁶⁴ − 1 = 18,446,744,073,709,551,615 回で、1秒に1回動かしても約5,850億（585 billion）年かかります。これが前のユニットの O(2ⁿ) の増え方です。

再帰、ループ、くり返される仕事

再帰で書けるものは、ループと自分で用意したスタックでも書けます。階乗のような簡単な例は、ループのほうがわかりやすいこともよくあります。再帰がかがやくのは、問題そのものが木の形をしているときです。マージソートでリストを分けるとき、フォルダーの中のフォルダーを調べるとき、そして最後のユニットのテーマである迷路の探索などです。1つの落とし穴は、くり返される仕事です。フィボナッチ数 0, 1, 1, 2, 3, 5, 8, … は fib(n) = fib(n − 1) + fib(n − 2) にしたがいます。これをそのまま再帰で書くと、fib(10) = 55 は177回、fib(20) は21,891回、fib(30) は2,692,537回の呼び出しをします。同じ小さい値が何度も計算されるからです。一度見つけた答えを覚えておくか、ループで下から積み上げれば、このむだがなくなります。