対象試験と出題頻度
再帰アルゴリズム（リカーシブ）は、基本情報技術者・応用情報技術者で出題されるテーマです。
科目Aでは「再帰関数の戻り値を求める」計算問題、科目Bでは疑似言語による再帰処理のトレース問題として定番化しており、終了条件の見極めと呼び出しの流れを正確に追えるかが問われます。
FE サンプル問題 科目A 問8、AP R6春期 午前 問6、AP H25秋期 午前 問8など、複数の試験区分で繰り返し出題されています。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「再帰って結局何？ループと何が違うの？」と混乱しがちです。
再帰アルゴリズム（Recursive Algorithm）とは、一言で言うと
「関数やプロシージャが、処理の中で自分自身を呼び出すことで問題を解く手法」
のことです。
イメージとしては、「合わせ鏡」です。
2枚の鏡を向かい合わせにすると、鏡の中にさらに鏡が映り、その中にまた鏡が映り…と無限に続きます。
再帰も同じで、関数の中で同じ関数が呼ばれ、その中でまた同じ関数が呼ばれます。ただし、プログラムでは「ここで止める」という終了条件（ベースケース）を必ず設けて、無限に続かないようにします。
📊 再帰アルゴリズムの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Recursive Algorithm（recursive＝再帰的な） |
| 別名 | リカーシブ（プログラムの性質としての呼称） |
| 必須の構成要素 | ①自分自身の呼び出し ②終了条件（ベースケース） |
| 代表例 | 階乗計算、フィボナッチ数列、2分木の探索、マージソート |
解説
ループ（for文やwhile文）でも繰り返し処理は書けますが、「問題を小さな同じ形の部分問題に分割して解く」構造の場合、再帰を使うとコードが格段に簡潔になります。
階乗計算で動きを理解する
最も定番の例が「nの階乗（n!）」です。5! = 5 × 4 × 3 × 2 × 1 = 120 ですが、これを再帰で定義すると次のようになります。
// 再帰による階乗の定義
function F(n)
if n = 0 then
return 1 ← 終了条件（ベースケース）
else
return n × F(n – 1) ← 自分自身を呼び出す
F(3)を呼び出すと、内部で何が起きるのかを図で追ってみましょう。
📊 F(3) の呼び出しの流れ
F(3) = 3 × F(2) … F(2)の結果を待つ
F(2) = 2 × F(1) … F(1)の結果を待つ
F(1) = 1 × F(0) … F(0)の結果を待つ
F(0) = 1 ← 終了条件に到達！
F(1) = 1 × 1 = 1 ← 戻る
F(2) = 2 × 1 = 2 ← 戻る
F(3) = 3 × 2 = 6 ← 戻る（最終結果）
呼び出しが深くなるたびに「まだ計算途中の情報」をどこかに保存しておく必要があります。
この保存場所がスタック（LIFO：後入れ先出し）です。
スタックとの関係
関数を呼び出すたびに、引数や戻りアドレスなどの情報がコールスタックに積まれます（push）。終了条件に達して結果が返ると、最後に積んだものから順に取り出されます（pop）。
📊 コールスタックの動き（F(3)の場合）
| 手順 | 動作 | スタックの状態（↑が先頭） |
|---|---|---|
| 1 | F(3)を呼ぶ | [F(3)] |
| 2 | F(2)をpush | [F(2)] [F(3)] |
| 3 | F(1)をpush | [F(1)] [F(2)] [F(3)] |
| 4 | F(0)をpush → 終了条件 | [F(0)] [F(1)] [F(2)] [F(3)] |
| 5 | F(0)=1 を返しpop | [F(1)] [F(2)] [F(3)] |
| 6 | F(1)=1 を返しpop | [F(2)] [F(3)] |
| 7 | F(2)=2 を返しpop | [F(3)] |
| 8 | F(3)=6 を返しpop | （空） |
終了条件がなければスタックに際限なく積み上がり、スタックオーバーフローでプログラムが異常終了します。終了条件は再帰の命綱です。
▶ 「リカーシブ」と似た4つのプログラム性質（クリックで展開）
試験では、プログラムの4つの性質（Re-系）を区別させる問題が定番です。
| 性質名 | 意味 |
|---|---|
| リカーシブ （再帰的） |
実行中に自分自身を呼び出しても正しい結果を返せる性質 |
| リエントラント （再入可能） |
複数のタスクから同時に呼ばれても正しい結果を返せる性質 |
| リユーザブル （再使用可能） |
終了後に再ロードなしで再実行しても正しく動く性質 |
| リロケータブル （再配置可能） |
メモリ上のどのアドレスに配置しても実行できる性質 |
覚え方のコツは「誰から呼ばれるか」で分けることです。リカーシブは「自分が自分を呼ぶ」、リエントラントは「他人が同時に呼ぶ」と整理すれば混同しません。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 再帰アルゴリズムの核心を3行で
・関数が自分自身を呼び出して、問題をより小さな同じ形の部分問題に分解する手法
・終了条件（ベースケース）がなければ無限ループになりスタックオーバーフローが起きる
・呼び出し途中の状態はスタック（LIFO）に保存され、終了条件到達後に逆順で値が返る
試験ではこう出る！
再帰アルゴリズムは、科目Aの午前問題と科目Bのアルゴリズム問題の両方で繰り返し出題されています。
出題パターンは大きく3つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE サンプル 科目A 問8 |
再帰的に定義された関数f(n)について、f(5)の値を求める問題。 | ・終了条件を見極め、呼び出しをトレースして戻り値を計算できるか |
| AP R6春 午前 問6 |
2分木の各ノードを再帰処理で探索し、出力順を求める問題。 | ・再帰処理の定義を読み取り、木構造の走査順（後行順）を追えるか |
| AP H30春 午前 問8 |
再帰処理を実現するための記憶管理方式を選ぶ問題。 | ・スタック（LIFO）が正解。FIFO・LFU・LRUとの区別 |
| AP H25秋 午前 問8 |
再帰的手続きproc(5)を実行した際の印字結果を求める問題。 | ・呼び出し前の印字と復帰後の印字を正しく追えるか |
📝 IPA試験での出題パターン
パターン1：「再帰関数の戻り値を求めよ」
f(n)の定義が与えられ、f(5)などの具体的な値を計算させる形式。終了条件から順に戻り値を積み上げれば解ける。FE科目Aでの最頻出パターン。
パターン2：「再帰処理のトレース結果を選べ」
手続きの定義が与えられ、出力される文字列や数列を選ぶ形式。AP H25秋のように「呼び出し前の処理」と「復帰後の処理」の両方がある場合、順序を間違えやすいのがひっかけポイント。
パターン3：「再帰処理に必要な記憶管理方式を選べ」
AP H30春のように、LIFO（スタック）を選ばせる問題。FIFO（キュー）との区別ができれば即答できる。
試験ではここまででOKです。再帰の数学的な理論やメモ化再帰の最適化手法まで深追いする必要はありません。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 再帰アルゴリズム（リカーシブ）の説明として、最も適切なものはどれでしょうか？
- A. 関数が処理の中で自分自身を呼び出し、終了条件に到達するまで問題をより小さな部分問題に分解して解く手法であり、呼び出し途中の状態はスタック（LIFO）に保存される。
- B. 複数のタスクから同時に呼び出されても、それぞれのタスクに対して正しい結果を返すことができるプログラムの性質。
- C. プログラムの実行が終了した後、主記憶への再ロードを行わずに再度実行しても正しい結果を返すことができる性質。
正解と解説を見る
正解：A
解説：
再帰アルゴリズムは、関数が自分自身を呼び出して問題を分割し、終了条件で処理を打ち切る手法です。途中経過の保存にはスタック（LIFO）が使われます。
選択肢Bはリエントラント（再入可能）の説明です。複数タスクからの同時呼び出しに対応する性質であり、「自分自身を呼び出す」再帰とは異なります。選択肢Cはリユーザブル（再使用可能）の説明です。再ロードなしで再実行できる性質であり、自己呼び出しの概念は含みません。
よくある質問（FAQ）
Q. 再帰で書ける処理は、すべてループでも書けますか？
書けます。理論上、再帰で表現できる処理はすべてループとスタックの組み合わせで書き直せます。逆に、ループで書ける処理は再帰でも書けます。ただし、木構造の探索やクイックソートのように「分岐して再び同じ処理に戻る」構造は、再帰のほうがコードが格段に短くなるため実務でも再帰が選ばれます。
Q. スタックオーバーフローはどのくらいの深さで起きますか？
言語や実行環境によって異なりますが、一般的なCやJavaの環境では数千〜数万回の再帰呼び出しでスタック領域が不足し、異常終了します。Pythonはデフォルトで再帰の上限が1000回に設定されています。試験では具体的な回数は問われないため、「終了条件がないと無限に呼び出しが続き、スタックオーバーフローになる」という事実だけ押さえれば十分です。
Q. 「末尾再帰」とは何ですか？試験に出ますか？
末尾再帰（tail recursion）とは、関数の最後の処理が再帰呼び出しだけになっている形式です。この形式ではコンパイラが最適化を行い、スタックを消費せずにループと同等の効率で実行できます。IPA試験の出題範囲ではここまで問われることはないので、参考程度で構いません。
Q. 実務で再帰が使われる代表的な場面を教えてください。
ファイルシステムのディレクトリ探索が典型例です。あるフォルダの中にサブフォルダがあり、その中にさらにサブフォルダがある…という入れ子構造を処理するとき、「フォルダを開く → 中身を調べる → サブフォルダがあれば同じ処理を繰り返す」という流れがそのまま再帰になります。JSONやXMLのような入れ子構造のデータ解析にも再帰は日常的に使われます。
