再帰
Recursion ・ さいき
関数が自分自身を呼び出し、問題を同じ形の小さな問題に分割しながら解く技法。木構造の処理と相性がよい。
概要
再帰は、関数が自分自身を呼び出すことで問題を解く技法です。ポイントは「同じ形の、少しだけ小さい問題」に分割できるかどうかにあります。たとえば「フォルダの合計サイズ」は「直下のファイルサイズ + 各サブフォルダの合計サイズ」で求められ、サブフォルダの合計はまったく同じ手順で求められます。この自己相似の構造をそのままコードにしたのが再帰です。
初学者にとっては「自分を呼んだら無限ループでは？」と直感に反する概念ですが、ファイルシステム・HTML の DOM・組織図・JSON のような入れ子構造を扱うときには、ループよりもはるかに自然に書けます。データの形とコードの形が一致するため、正しさを確かめやすいのも利点です。
再帰は単なる書き方のテクニックに留まらず、分割統治法や木の探索といった主要アルゴリズムの背骨であり、関数型プログラミングでは繰り返しを表現する基本手段でもあります。「大きな問題を小さな同型の問題に還元する」という思考法そのものを体で覚える語彙です。
なぜ生まれたか
木構造や入れ子構造をループだけで処理しようとすると、途端に面倒になります。フォルダ階層を深さ優先でたどるには「まだ処理していない場所」を自分で覚えておく必要があり、スタックというデータ構造を明示的に用意して、積んで、降ろして、を手で管理することになります。問題は「フォルダの中のフォルダも同じように処理する」というだけの単純な話なのに、コードは進行状態の帳簿付けで埋まってしまうのです。
再帰は、この帳簿付けを言語処理系に肩代わりさせます。関数呼び出しには「どこまで進んだか」をコールスタックに自動保存し、戻るときに復元する仕組みがもともと備わっています。関数が自分を呼べば、この仕組みがそのまま「未処理の場所の記憶」として働き、コードには問題の構造だけが残ります。1960年の ALGOL 60 が再帰呼び出しを言語仕様として認めたことが転機となり、以降ほぼすべての言語で当たり前の機能になりました。
詳細
基底条件と再帰ステップ
再帰関数は必ず二つの部分からできています。ひとつは「これ以上分割せずに直接答えられる最小の場合」を処理する基底条件（base case）、もうひとつは「問題を小さくして自分を呼び、結果を組み立てる」再帰ステップです。階乗なら「0 の階乗は 1」が基底条件、「n の階乗は n × (n−1) の階乗」が再帰ステップです。再帰のバグの大半は基底条件にあります。書き忘れる、条件がずれていて到達しない、あるいは再帰ステップで問題が小さくなっていない — いずれも無限再帰に直結するため、再帰を書くときは「必ず基底条件に近づいているか」を最初に確認します。
コールスタックで何が起きているか
再帰呼び出しのたびに、引数とローカル変数を収めたスタックフレームがコールスタックに積まれます。基底条件に到達すると、今度はフレームをひとつずつ降ろしながら戻り値を組み立てていきます。「行きに問題を分解し、帰りに答えを合成する」という往復が再帰の実行イメージです。
この仕組みの限界がスタックオーバーフローです。スタック領域は有限（数MB程度が一般的）なので、再帰が深くなりすぎるとフレームを積む場所が尽きてプログラムが落ちます。深さ数千程度で起きるため、要素数百万のリストを素朴な再帰で処理する、といった書き方は危険です。木のようにバランスすれば深さが log n に収まる構造では問題になりにくく、「再帰の深さがどこまで育つか」を見積もる癖が実務では重要になります。
分割統治 — 再帰が主役になるアルゴリズム
再帰の真価が出るのが分割統治法（divide and conquer）です。問題を半分ずつに分けてそれぞれを再帰で解き、結果を統合する — クイックソートやマージソートがその代表で、素朴な方法の O(n²) を O(n log n) に改善します（計算量の劇的な差です）。二分探索木の探索・挿入も「左右どちらかの部分木に対する同じ問題」への再帰ですし、構文解析・レンダリングエンジンの DOM 走査・電卓の式評価など、木を扱う処理はほぼすべて再帰で書かれています。
一方、分割した問題が重複する場合は工夫が要ります。フィボナッチ数列を素朴に再帰すると同じ計算を指数回繰り返してしまいますが、一度計算した結果を辞書に保存して再利用する「メモ化」を挟むだけで線形時間になります。キャッシュの発想を再帰に持ち込んだこの技法は、動的計画法への入り口でもあります。
メモ化の効果は、実際に呼び出し木が育つ様子を見ると一目で分かります。
「実行」で呼び出し木を描画します
n を選んで「実行」を押すと、fib(n) の呼び出し木が呼び出し順に育っていきます。まずはメモ化 OFF で、同じ計算が何度も現れる様子を見てください。
末尾再帰と、ループとの行き来
再帰呼び出しが関数の「最後の動作」で、戻り値をそのまま返すだけの形を末尾再帰と呼びます。この形なら呼び出し元のフレームを保持する必要がないため、処理系がフレームを再利用してループと同等のコードに変換できます（末尾呼び出し最適化）。Scheme や Scala など関数型プログラミング系の言語はこれを保証・支援しますが、Python や Java、多くの JavaScript 処理系は行わないため、「末尾再帰に書き換えたから深くても安全」とは限らない点に注意が必要です。
原理的には、すべての再帰は明示的なスタックを使ったループに書き換えられ、逆もまた可能です。実務での使い分けは明快で、データが再帰的な構造（木・入れ子）なら再帰、単純な繰り返しならループが読みやすくなります。再帰を学ぶ意義は「常に再帰で書くため」ではなく、問題を自己相似に分解する視点と、コールスタックという実行モデルの理解を手に入れることにあります。この視点はクロージャや高階関数と並んで、コードの表現力を一段引き上げてくれます。