再帰とは？

詳細解説

再帰（Recursion）とは、関数や手続きが自分自身を呼び出す処理構造です。問題を同一形式のより小さな部分問題に分割し、最終的に解を持ちあわせている最小ケース（基底ケース・ベースケース）まで到達したら、結果を逆順に積み上げて最終解を得る仕組みです。代表的な例として階乗（n! = n × (n-1)!）やフィボナッチ数列があります。再帰を実現するために関数呼び出しのたびにスタックフレームが積まれ（呼び出し履歴）、再帰の深さが深すぎると**スタックオーバーフロー**が発生します。FE試験では「再帰の実行トレース（呼び出しと戻りの順序を手で追う）」が科目Bの中核問題の一つです。疑似言語では「自分自身を呼び出す手続き」として表現されます。「末尾再帰」は関数の最後の操作として再帰呼び出しが行われる形式で、一部の処理系ではループに変換（末尾再帰最適化）されます。クイックソート・マージソート・木の探索（DFS）は再帰で自然に記述できます。

FE試験での出題ポイント

• 1基底ケース（終了条件）の設定がないと無限再帰・スタックオーバーフロー
• 2実行トレース：呼び出しの積み重ねと戻りの順序を手で追う練習
• 3再帰とループの相互変換（再帰→スタック利用でループに変換可能）
• 4FE科目B頻出：フィボナッチ・階乗・ハノイの塔の再帰実装を読む

関連用語