LASSIC Media らしくメディア

再帰処理でつまずきやすいポイント

プログラミングを学び始めた担当者や、実装レビューを任されたエンジニアが最初に戸惑う概念の一つに「再帰処理(recursion)」があります。関数が自分自身を呼び出すという説明を読んでも、頭の中でイメージが結びつかず、「結局いつ処理が終わるのか」「なぜループで書かないのか」という疑問が残るケースは少なくありません。

特に組織図やディレクトリ構成のように階層が深くなるデータを扱うシステムでは、再帰処理を避けて通れない場面が出てきます。設計レビューやコードレビューの場で「この再帰は止まるのか」「何段まで深くなり得るのか」を問われたとき、仕組みを説明できるかどうかで議論の質は変わってくるものです。

本記事では、再帰処理の基本的な仕組みから実務で使われる場面、そして導入時に押さえておきたい注意点までを整理します。焦点を当てるのは数式の証明ではなく、業務システムを開発・運用する立場から見た実務上のポイントです。

再帰処理そのものは特別な技巧ではなく、多くのプログラミング言語で標準的にサポートされている仕組みです。とはいえ、仕組みを理解しないまま既存コードへ手を加えると、基底条件の条件式を一文字書き換えただけで無限に呼び出しが続く不具合を生んだり、想定より深い入力データに遭遇した途端に処理が異常終了したりする事態につながりかねません。承認フローの階層をたどる処理や、カテゴリツリーを再帰的に展開する画面表示ロジックなど、業務システムの内部には気づかないうちに再帰処理が組み込まれていることも珍しくないでしょう。

自らコードを書くエンジニアだけでなく、開発ベンダーへの発注や仕様のすり合わせを担当する管理職層にとっても、再帰処理の考え方を理解しておく意味があるでしょう。見積もりの妥当性を検討する場面や、障害報告書に「再帰呼び出しの深さが想定を超えたことが原因」と記載された際に、その内容を正確に読み解けるかどうかは、技術的な意思決定の質に関わってきます。

再帰処理の仕組み

関数が自分自身を呼び出すという構造

再帰処理とは、ある関数が処理の途中で自分自身を呼び出す構造を指します。通常の関数呼び出しでは、関数Aが関数Bを呼び、関数Bが処理を終えたら関数Aに戻ってくるという流れになりますが、再帰処理では関数Aが関数Aを呼び出します。呼び出された側の関数Aは、呼び出した側とは独立した引数や変数を持っており、同じ処理のコピーが何重にも入れ子になって実行されるイメージです。

この「自分自身を呼ぶ」という性質を利用すると、次のような特徴を持つ問題を素直に表現できます。

• 問題全体が、同じ構造を持つより小さな問題に分解できる
• 小さな問題を解いた結果を組み合わせると、元の問題の答えになる
• データ自体が階層構造や入れ子構造を持っている

逆に言えば、こうした性質を持たない処理を無理に再帰で書いても、コードは複雑になるだけで見返りは乏しいでしょう。マトリョーシカ人形のように、同じ形をした一回り小さい入れ物が中に入っていて、それをさらに開けるとまた一回り小さい同じ形の入れ物が出てくる、というイメージを思い浮かべると理解しやすいかもしれません。

実際のプログラムでは、関数Aの中で呼び出された関数A(便宜上「子」と呼びます)は、呼び出し元の「親」とは別の実行文脈を持ちます。親が使っている変数と子が使っている変数は名前が同じでも別物として扱われるため、深く入れ子になっても互いの値を上書きし合うことはないのです。この独立性があるからこそ、同じ処理のコピーを何段にも重ねて扱える仕組みが成り立っています。

基底条件(ベースケース)と再帰ステップ

再帰処理を正しく機能させるための要となるのが、基底条件(ベースケース)と再帰ステップという二つの部品です。

• 基底条件(ベースケース)：それ以上分解できない、これ以上ないほど単純な形の問題に対する答えを直接返す部分。ここで自分自身の呼び出しを止めます。
• 再帰ステップ：問題を一回り小さくしたうえで、自分自身を呼び出す部分。呼び出すたびに、問題は基底条件へと一歩ずつ近づいていく形です。

基底条件を書き忘れる、あるいは再帰ステップが基底条件に向かって縮小していかない場合、関数は自分自身を呼び続け、処理が終わらない状態に陥ります。「どの入力で止まるか」「呼び出しごとに問題が小さくなっているか」の二点を確認する習慣は、レビューの場で役立つでしょう。

典型的な不具合の一因として、条件式の等号・不等号を取り違えるケースが挙げられます。例えば「n が 0 未満になったら止める」つもりで書いた条件式が「n が 0 以下になったら止める」になっていた場合、境界値によっては基底条件に到達せず呼び出しが続いてしまうことも起こり得るでしょう。境界値のテストケースを用意し、基底条件付近の挙動を個別に確認しておくと、こうした見落としを早い段階で洗い出せます。

コールスタックに積まれる様子

関数が自分自身を呼び出すたびに、実行環境の内部ではコールスタックと呼ばれる領域に、呼び出し元の状態(どこまで処理したか、どの変数を持っているか)が一段ずつ積まれていきます。基底条件に到達すると、そこから値を返しながらスタックを一段ずつ取り崩し、積まれた呼び出しを一つずつ完了させて元の場所へ戻っていくという流れです。

呼び出しの際にスタックへ積まれる情報は、実行中の行の位置や、その時点で使っていた変数の値一式です。これを「スタックフレーム」と呼びます。呼び出しが深くなるほどスタックフレームの枚数は増えていき、基底条件に到達した時点で一番内側のフレームから順に取り除かれ、値を一段ずつ呼び出し元へ渡しながら処理が完了していきます。下図は、ある処理を再帰的に呼び出し、基底条件に到達したあとに戻っていく様子を単純化して表したものです。

再帰処理の使いどころ

ここまでの仕組みを踏まえたうえで、実際にどのような場面で再帰処理が選ばれているのかを見ていきます。共通しているのは「問題やデータそのものが、同じ形の入れ子構造になっている」という性質です。この性質を持つ対象に出会ったら、再帰処理が候補に挙がりやすいと考えておくとよいでしょう。

木構造・階層データの走査

組織図、社内システムのディレクトリ構成、APIから返るJSONの入れ子構造など、業務システムには階層を持つデータが頻繁に登場します。こうしたデータは「ある要素の下に、また同じ形の要素がぶら下がっている」という構造を持つため、再帰処理と相性が良いといえます。

• 組織図の各部署配下に子部署が続く構造をたどり、全社員数を集計する
• フォルダの中にサブフォルダが続く構成を掘り下げ、対象ファイルを列挙する
• コメント欄の返信にさらに返信が連なるスレッドを表示順にたどる

これらは「どこまで階層が深いか」が事前に分からない点が共通しています。あらかじめ何重のループを書けばよいか決め打ちできない場面では、再帰処理のほうが構造をそのまま表現でき、コードも読みやすくなる傾向があります。

例えば承認ワークフローを考えると、申請者の上長、さらにその上長というように承認ルートの段数は部署や案件によって異なります。あらかじめ「3段階まで」と決め打ちしてループで書いてしまうと、組織改編で承認段数が変わるたびにコードの修正が生じがちです。承認者を再帰的にたどる形で書いておけば、組織構造の変化にもロジックを大きく書き換えずに対応しやすくなります。ECサイトの商品カテゴリツリーで、カテゴリの下にサブカテゴリ、さらにその下にサブサブカテゴリが続く画面のパンくずリストや絞り込みメニューを組み立てる処理も、同様の考え方で実装されている場合があります。

分割統治法によるアルゴリズム

大きな問題を同じ形の小さな問題に分割し、それぞれの答えを組み合わせて元の問題を解く考え方は、分割統治法と呼ばれています。マージソートはその代表例で、配列を半分に分割し、それぞれを再帰的に整列させたうえで、二つの整列済み配列を統合(マージ)します。

クイックソートや二分探索も同様の考え方に基づいており、探索範囲や対象データを毎回半分程度に絞り込みながら、再帰的に処理を進めていく手法です。データ件数が増えても、分割の回数が緩やかにしか増えないという特性は、こうしたアルゴリズムが大量データの処理で選ばれる理由の一つになっています。

業務システムの内部で自前のソートアルゴリズムを実装する場面は限られますが、標準ライブラリのソート関数やデータベースのインデックス探索といった、日常的に利用している機能の裏側では、こうした分割統治の考え方が使われています。仕組みを理解しておくと、性能に関する問い合わせや障害調査の際に、処理の内部で何が起きているかを推測しやすくなるでしょう。

数学的な定義との相性

階乗、フィボナッチ数列、木構造の高さの計算など、数学的にそもそも「nの答えは、n-1の答えを使って定義される」という形で定義されている対象もあります。定義そのものが再帰的であるため、コードも定義に沿ってそのまま書けるという利点があります。

フィボナッチ数列は「1番目と2番目の項は1、3番目以降の項は直前の二つの項の和」という定義で表される数列です。この定義をそのままコードに置き換えると、fib(n)はfib(n-1)とfib(n-2)を足し合わせる形で書けます。定義と実装の形が一致しているため、仕様書とコードの対応関係を追いやすいという利点がある一方、後述するとおり同じ計算を何度も繰り返してしまう性質も併せ持っており、注意点として押さえておく必要があります。

次は階乗を再帰処理で表した擬似コードです。基底条件と再帰ステップの対応関係を確認してみてください。

function factorial(n):
    if n <= 1:
        return 1                      # 基底条件
    return n * factorial(n - 1)       # 再帰ステップ(nを1減らして自分自身を呼ぶ)

factorial(4) を呼び出すと、内部では factorial(3)、factorial(2)、factorial(1) の順に呼び出しが積み重なり、n が1になった時点で基底条件に到達します。そこから 1、2、6、24 という順で値を掛け合わせながら呼び出し元へ戻っていく、というのが前述の図と対応する流れです。

再帰処理を使う際の注意点

スタックオーバーフローのリスク

コールスタックに積める呼び出しの段数には上限があります。基底条件に到達する前に呼び出しが積み上がりすぎると、スタック領域を使い果たし、実行時エラーで処理が異常終了します。この現象はスタックオーバーフローと呼ばれ、再帰処理を扱ううえで避けて通れない制約です。ループ処理であれば同じ繰り返し回数でもスタックを積み増さずに実行できるため、この制約は再帰処理ならではの特徴だといえます。

入力データの件数や階層の深さが利用者や外部システムに左右される処理では、想定より深い再帰が発生する余地が残ります。再帰の深さに上限を設ける、あるいは深くなりすぎる可能性がある処理は反復に置き換えるといった対策を、設計段階で検討しておくと後々の手戻りを抑えられます。

スタックに積める段数の上限は、言語や実行環境の設定によって異なります。開発時のテスト環境では問題なく動いていた処理が、入力件数が想定より多い本番データに触れた途端にエラーを起こす、という事例は決して珍しくないものです。外部から受け取るデータや、利用者が任意に階層を深くできる仕様の項目については、再帰の深さに関わる境界を洗い出しておく価値があります。加えて、フォルダ階層の走査のように利用者の操作次第で深さが変わる処理や、外部システムから受け取るJSONの入れ子構造を解析する処理は、想定外に深いデータが渡ってくる余地が相対的に大きい部類です。こうした処理の入り口では、階層の深さそのものに上限を設けて弾く、あるいは反復による書き方に置き換えるといった防御的な設計を検討しておくと、本番環境での予期しない停止を減らしやすくなります。

パフォーマンスと重複計算

再帰処理は書き方によっては、同じ計算を何度も繰り返してしまう場合があります。代表的な例がフィボナッチ数列の素朴な再帰実装で、fib(n)を求めるためにfib(n-1)とfib(n-2)をそれぞれ呼び出しますが、この二つの呼び出しの内部でも同じ値が何重にも計算し直されるという構造です。nが大きくなるほど計算量は急激に膨らみ、体感できるほど処理時間が伸びていきます。

この種の重複計算は、一度計算した結果を保持しておき、同じ引数で再度呼ばれたときはその値を使い回す手法(メモ化)によって抑えられます。木構造や階層データの走査では重複計算は起きにくい一方、数列や漸化式のように「同じ部分問題が複数の経路から参照される」処理では、事前にこの特性を見極めておく価値があります。

メモ化の考え方自体は単純で、引数と計算結果の対応を辞書やマップのような形で保持しておき、関数が呼ばれるたびに「すでに計算済みの引数かどうか」を確認するだけです。計算済みであれば保持しておいた値をそのまま返し、未計算であれば通常どおり再帰処理を進めて結果を保存します。バッチ処理やレポート集計のように同じ計算が繰り返し発生しやすい処理では、導入の有無で体感できる差が出ることもあるため、実装前に重複計算の有無を確認しておくとよいでしょう。

末尾再帰という書き方

再帰ステップの最後に、それ以上何もせず自分自身の呼び出し結果をそのまま返す形の再帰を、末尾再帰と呼びます。呼び出し元で結果を使って追加の計算を行う必要がないため、一部の言語や処理系ではこの形の再帰をループと同等の実行方法に変換し、スタックを積み増さずに実行する最適化が行われます。

ただし、この最適化(末尾呼び出し最適化)が言語仕様や実行環境によって働くかどうかはまちまちです。末尾再帰の形で書いたつもりでも、対象の言語やランタイムが最適化を行わない場合は、通常の再帰と同じくスタックを消費し続けます。特定の書き方に依存した設計をする前に、採用する言語・実行環境での挙動を確認しておく必要があるでしょう。また、末尾再帰の形にこだわるあまりコードの見通しが悪くなるようであれば、無理に末尾再帰へ寄せず、素直な再帰やループ処理で書いたほうが結果的に保守しやすくなる場合もあります。設計段階で「末尾再帰による最適化を前提にした処理」を選ぶ場合は、その前提を資料に残し、実行環境を変更する際に見落とされないようにしておくことが望ましいでしょう。

テストとデバッグの勘所

再帰処理を含む関数は、通常のループ処理に比べてデバッグ時に処理の流れを追いにくいと感じる担当者もいます。デバッガでステップ実行をすると、同じ関数名の呼び出しが何段にも重なって表示されるため、今どの段の呼び出しを見ているのか見失いがちです。

• 基底条件に該当する入力(単純なケース)を単独でテストする
• 基底条件のすぐ手前の入力(境界値)を個別にテストする
• 階層が深いデータや、想定より件数が多いデータでも処理が完了するかを確認する
• ログや出力に、現在の呼び出しの深さや引数の値を含めておき、追跡しやすくしておく

こうした観点でテストケースを整理しておくと、実装者以外がコードレビューを行う際にも、再帰処理がどのような入力を想定しているのかを共有しやすくなります。

ループ処理(反復)との使い分け

再帰処理とループ処理(反復)は、どちらも「同じ処理を繰り返す」という点では似ていますが、向いている場面は異なります。なお本記事は反復(ループ)やイテレータそのものの解説ではなく、あくまで自己呼び出しという構造とその使いどころに焦点を当てるものです。両者のおおまかな違いを整理すると、次のようになります。

階層の深さが読めないデータや、分割統治のように部分問題へ分けて考えたほうが素直な処理では再帰処理を、件数があらかじめ分かっている単純な繰り返しではループ処理を、という具合に対象の性質から選ぶのが妥当な進め方です。どちらか一方だけを使う前提に固定せず、処理の性質に応じて使い分ける姿勢がチームの保守性を支えます。

実装後にどちらの書き方を選んだかをコードコメントや設計資料に一言残しておくと、後から引き継いだ担当者が「なぜこの処理は再帰で書かれているのか」を推測する手間を省けます。特に階層データの走査など、深さが可変であることが選定理由になっている場合は、その旨を明記しておくと保守フェーズでの誤った書き換えを防ぎやすくなります。

まとめ

再帰処理は特別な小技ではなく、階層データや分割統治の考え方と地続きの、標準的なプログラミングの手法の一つです。仕組みと注意点を押さえたうえで、ループ処理との使い分けを判断できる状態にしておくと、コードレビューや設計の議論がより噛み合いやすくなるでしょう。要点を改めて整理します。

• 再帰処理とは、関数が自分自身を呼び出す構造で、基底条件(ベースケース)と再帰ステップの組み合わせで成り立つ
• 呼び出しのたびにコールスタックへ状態が積まれ、基底条件に到達すると一段ずつ戻りながら結果を組み立てる
• 組織図やディレクトリ構成のような階層データの走査、マージソートなどの分割統治法、階乗のような再帰的な数学的定義との相性が良い
• スタックオーバーフロー、重複計算によるパフォーマンス低下、末尾再帰の最適化が働くかどうかは、導入前に確認しておきたい注意点
• 階層構造や分割統治には再帰処理、件数が明確な単純な繰り返しにはループ処理と、対象の性質に応じて使い分ける
• 基底条件付近の境界値テストや、呼び出しの深さを記録するログを整えておくと、デバッグやレビューの負担を抑えやすい

よくある質問

著者：テレリモ総研編集部　鈴木 亮佑

出典

本記事の内容は、下記の公式ドキュメントで解説されている再帰・コールスタックの定義や、実行系における再帰の深さの制約に関する記述を参考にしています。より詳しい仕様や実装依存の挙動を確認したい場合は、各リンク先を参照してください。

• MDN Web Docs「Recursion(再帰)」用語集
• MDN Web Docs「Call stack(コールスタック)」用語集
• Python公式ドキュメント「sys.setrecursionlimit」

Tweet