再帰 — 知星図

概要

再帰は、関数が自分自身を呼び出すことで問題を解く技法です。ポイントは「同じ形の、少しだけ小さい問題」に分割できるかどうかにあります。たとえば「フォルダの合計サイズ」は「直下のファイルサイズ + 各サブフォルダの合計サイズ」で求められ、サブフォルダの合計はまったく同じ手順で求められます。この自己相似の構造をそのままコードにしたのが再帰です。

初学者にとっては「自分を呼んだら無限ループでは？」と直感に反する概念ですが、ファイルシステムのフォルダ階層、HTML の要素の入れ子（DOM）、組織図、JSON のような入れ子構造を扱うときには、ループよりもはるかに自然に書けます。データの形とコードの形が一致するため、正しさを確かめやすいのも利点です。

再帰は単なる書き方のテクニックに留まらず、分割統治法や木の探索といった主要アルゴリズムの背骨であり、関数型プログラミングでは繰り返しを表現する基本手段でもあります。「大きな問題を小さな同型の問題に還元する」という思考法そのものを体で覚える語彙です。

なぜ生まれたか

木構造や入れ子構造をループだけで処理しようとすると、途端に面倒になります。フォルダ階層を深さ優先でたどるには「まだ処理していない場所」を自分で覚えておく必要があり、スタックというデータ構造を明示的に用意して、積んで、降ろして、を手で管理することになります。問題は「フォルダの中のフォルダも同じように処理する」というだけの単純な話なのに、コードは進行状態の帳簿付けで埋まってしまうのです。

再帰は、この帳簿付けを言語処理系に肩代わりさせます。関数呼び出しには「どこまで進んだか」をコールスタック（スタックとヒープ）に自動保存し、戻るときに復元する仕組みがもともと備わっています。関数が自分を呼べば、この仕組みがそのまま「未処理の場所の記憶」として働き、コードには問題の構造だけが残ります。

歴史的には、1958年にジョン・マッカーシーが設計した LISP が、リストという入れ子のデータを再帰関数で処理することを言語の中心に据えました。続く1960年の ALGOL 60 が、手続き型の言語として再帰呼び出しを仕様で認め、その実装のために呼び出しごとにフレームを積むスタックの方式が広まりました。当時の FORTRAN などは変数の置き場所を固定していたため、同じ関数を呼び出し中にもう一度呼ぶことができなかったのです。この二つを転機に、再帰はほぼすべての言語で当たり前の機能になりました。

詳細

基底条件と再帰ステップ

再帰関数は必ず二つの部分からできています。ひとつは「これ以上分割せずに直接答えられる最小の場合」を処理する基底条件（base case）、もうひとつは「問題を小さくして自分を呼び、結果を組み立てる」再帰ステップです。階乗なら「0 の階乗は 1」が基底条件、「n の階乗は n × (n−1) の階乗」が再帰ステップです。再帰のバグの大半は基底条件にあります。書き忘れる、条件がずれていて到達しない、あるいは再帰ステップで問題が小さくなっていない — いずれも無限再帰に直結するため、再帰を書くときは「必ず基底条件に近づいているか」を最初に確認します。

コールスタックで何が起きているか

再帰呼び出しのたびに、引数とローカル変数を収めたスタックフレームがコールスタック（スタックとヒープ）に積まれます。基底条件に到達すると、今度はフレームをひとつずつ降ろしながら戻り値を組み立てていきます。「行きに問題を分解し、帰りに答えを合成する」という往復が再帰の実行イメージです。

factorial(3) の実行 — 呼び出しでスタックが積まれ、基底条件から戻りながら答えを合成する

この仕組みの限界がスタックオーバーフローです。スタック領域は有限（数MB程度が一般的）なので、再帰が深くなりすぎるとフレームを積む場所が尽きてプログラムが落ちます。深さ数千程度で起きるため、要素数百万のリストを素朴な再帰で処理する、といった書き方は危険です。木のようにバランスすれば深さが log n に収まる構造では問題になりにくく、「再帰の深さがどこまで育つか」を見積もる癖が実務では重要になります。

分割統治 — 再帰が主役になるアルゴリズム

再帰の真価が出るのが、アルゴリズムの設計法の一つである分割統治法（divide and conquer）です。問題を半分ずつに分けてそれぞれを再帰で解き、結果を統合します。マージソートがその代表で、素朴な整列の O(n²) を常に O(n log n) に改善します（計算量とO記法で見ると劇的な差です）。クイックソートも同じ形ですが、O(n log n) になるのは平均の話で、基準値の選び方が悪く分割が偏り続けると最悪 O(n²) に落ちます。二分探索木の探索・挿入も「左右どちらかの部分木に対する同じ問題」への再帰ですし、構文解析、ブラウザレンダリングでの DOM の走査、電卓の式評価など、木を扱う処理はほぼすべて再帰で書かれています。

一方、分割した問題が重複する場合は工夫が要ります。フィボナッチ数列を素朴に再帰すると同じ計算を指数回繰り返してしまいますが、一度計算した結果を辞書に保存して再利用する「メモ化」を挟むだけで線形時間になります。キャッシュの発想を再帰に持ち込んだこの技法は、動的計画法への入り口でもあります。

下の部品で、fib(n) を1回ずつ自分の手で呼び出してみてください。光る節点を押すと呼び出され、右のコールスタックに1段積まれます。根からいまの呼び出しまでの金色の経路が、そのままスタックの中身です。最後まで進めたら、メモ化をオンにして、計算済みの枝が丸ごと消える様子と呼び出し回数を比べてください。

⚡ 体験: 呼び出しを1つずつ — 積まれるスタックと、育つ呼び出しの木

メモ化

呼び出し回数0 / 15いまの深さ0最大の深さ0

実行しているコード

function fib(n) {
if (n < 2) return n // 基底条件
const v = fib(n - 1) + fib(n - 2) // 再帰ステップ
return v
}

金の破線で光る fib(5) を押して呼び出してください。そのあとも、光る節点（次に呼ばれる子）か、結果のそろったいちばん上の段を押して進めます。

末尾再帰と、ループとの行き来

再帰呼び出しが関数の「最後の動作」で、戻り値をそのまま返すだけの形を末尾再帰と呼びます。この形なら呼び出し元のフレームを保持する必要がないため、処理系がフレームを再利用してループと同等のコードに変換できます（末尾呼び出し最適化）。Scheme は言語仕様でこれを保証し、Scala も自己末尾再帰をループに変換するなど、関数型プログラミング系の言語は支援が手厚い一方、Python や Java は行いません。JavaScript は ES2015 の仕様に末尾呼び出しの最適化を書き込みましたが、実装したのは Safari の JavaScriptCore だけで、V8（Chrome・Node.js）や Firefox は採用していません。「末尾再帰に書き換えたから深くても安全」とは限らない点に注意が必要です。

原理的には、すべての再帰は明示的なスタックを使ったループに書き換えられ、逆もまた可能です。実務での使い分けは明快で、データが再帰的な構造（木・入れ子）なら再帰、単純な繰り返しならループが読みやすくなります。再帰を学ぶ意義は「常に再帰で書くため」ではなく、問題を自己相似に分解する視点と、コールスタックという実行モデルの理解を手に入れることにあります。この視点はクロージャや高階関数と並んで、コードの表現力を一段引き上げてくれます。

試問

fib(n) は「n が 2 未満ならそのまま返し、そうでなければ fib(n−1) + fib(n−2) を返す」関数です。画面の木は fib(6) の呼び出しで、金の破線で光る節点（次に呼ばれる関数）を押すと呼び出し、結果のそろった節点を押すと値を返します。「1手進める」でも進められます。一度計算した答えを覚えて使い回す「メモ化」は、オン・オフを切り替えられます（切り替えると最初からやり直し）。

✦ 命題挑戦中

fib(6) を最後まで計算し、しかも関数の呼び出しを 12 回以下に抑えよ

fib(6) を最後まで計算する（= 8）
呼び出しを 12回以下に抑える（いま 0回）

⚡ 体験: 呼び出しを1つずつ — 積まれるスタックと、育つ呼び出しの木

メモ化

呼び出し回数0 / 25いまの深さ0最大の深さ0

実行しているコード

function fib(n) {
if (n < 2) return n // 基底条件
const v = fib(n - 1) + fib(n - 2) // 再帰ステップ
return v
}

金の破線で光る fib(6) を押して呼び出してください。そのあとも、光る節点（次に呼ばれる子）か、結果のそろったいちばん上の段を押して進めます。