【再帰】

ここまでの道具は「データの持ち方」の話でした。この章は少し毛色が変わって、「処理の組み立て方」の話です。再帰とは、関数が、自分自身を呼ぶこと。初見では頭がねじれる感覚があるはずですが、仕組みは意外なほど単純で、しかもその仕組みはすでに学んだスタックの上に乗っています。

再帰とは

理屈より先に、動くものを見ます。カウントダウンする関数です。

出力は 3、2、1、発射!となります。流れを追うと、

countdown(3)が3を表示してcountdown(2)を呼ぶ→

countdown(2)が2を表示してcountdown(1)を呼ぶ→

countdown(1)が1を表示してcountdown(0)を呼ぶ→

countdown(0)は「発射!」を出してreturn(もう自分を呼ばない)。

関数が自分を呼ぶたびに、問題(n)がひとつ小さくなり、最後に止まる。これが再帰の全体像です。

再帰の2つの部品

すべての再帰は、この2つでできています。

①ベースケース(止まる条件): if (n === 0) return; の部分。「これ以上小さくしなくていい、ここで終わり」という出口です。必ず関数の先頭に書きます。

②再帰ステップ(小さくして自分を呼ぶ): countdown(n - 1) の部分。必ず、問題を小さくしてから呼びます(nのままで呼んだら永遠に終わりません)。

逆に言うと、再帰のバグは必ずこのどちらかです。出口がない、または小さくなっていない。では、出口がないと何が起きるのか。見ておきましょう。

▶ 実行してみよう(わざと壊す)

エラーが出ます。「Maximum call stack size exceeded」(コールスタックの上限を超えました)。スタックの章で、「関数を呼ぶたびに『戻り先の記録』がスタックに積まれる」と話しました。自分を呼ぶたびに記録が1枚積まれ、誰もreturnしないので誰も降りてこない。積み上がり続けた呼び出しの塔が、上限に達して崩れた。それがこのエラーの正体です。再帰はスタックの上で動いています。だからこのエラーを「スタックオーバーフロー」と呼びます。

戻り値を組み立てる再帰

countdownは表示するだけでした。再帰の本領は、戻り値を積み上げて答えを組み立てる形です。定番の例、階乗(nの階乗 = 1×2×…×n)で見ます。

factorial(4) の中身を展開すると、

4 × factorial(3) →

4 × (3 × factorial(2)) →

4 × (3 × (2 × factorial(1))) →

4 × 3 × 2 × 1 = 24。