こんにちは。今日は「再帰処理（Recursion）」について学びました。
基本情報技術者試験の午後問題でもよく出るテーマで、アルゴリズムの穴埋めやトレース問題として頻出です。
この記事で分かること（目次）
📌 再帰処理の基本
再帰処理とは、
関数（処理）の中で、自分自身を呼び出すこと
をいいます。
ポイントは次の2つです。
- **終了条件（ベースケース）**が必ずある
- 同じ構造を繰り返すのに便利（木構造探索、分割統治法などで活躍）
🍼 幼稚園バージョンの例え
部屋が何個も並んでいて、奥の部屋にいる友だちに手紙を渡したい。
1つの部屋に入ったら「ここに友だちはいる？」と確認。
いなかったら、次の部屋に手紙を渡してもらうようお願いする。
これを繰り返して、最後の部屋まで進み、手紙を渡したら戻ってくる。
この「進んで→戻る」流れが、再帰の特徴です。
📚 試験で出るパターン
- 数値計算系（階乗
n!、フィボナッチ数列など） - 木構造探索（前順・中順・後順の走査）
- 分割統治法（マージソート、クイックソート）
- 呼び出し回数や出力順を問うトレース問題
📝 出題パターン例
1️⃣ 数値計算系（代表例：階乗）
問題例
n!（階乗）を求める関数 factorial(n) を再帰で実装する。
n! = n × (n-1) × (n-2) × ... × 1
擬似コード（穴埋め問題形式）
function factorial(n):
if n == 0:
return 1
else:
return ( ① ) * factorial( ② )
解答
① n
② n – 1
2️⃣ 数列生成系（フィボナッチ数列）
問題例
フィボナッチ数列を求める関数 fibonacci(n) を再帰で作る。
f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)
擬似コード
function fibonacci(n):
if n == 0: return 0
if n == 1: return 1
return fibonacci(①) + fibonacci(②)
解答
① n – 1
② n – 2
3️⃣ データ構造探索（木構造）
問題例
二分木のすべてのノードを探索して表示する処理
擬似コード
function traverse(node):
if node is null: return
traverse(node.left)
print(node.value)
traverse(node.right)
試験では、呼び出し順序を答える問題や、ノード番号を出力順に並べる問題として出る。
4️⃣ 分割統治法（ソートなど）
- クイックソートやマージソートの処理手順
- 再帰で配列を分割 → 部分配列を処理 → 結果を結合
例
function quickSort(A):
if length(A) <= 1: return A
pivot = A[0]
left = [x in A if x < pivot]
right = [x in A if x >= pivot]
return quickSort(left) + [pivot] + quickSort(right)
出題例：
- 再帰呼び出しの回数を答える
- ある入力に対しての処理手順を追う
📝 午後問題風 練習問題📄 再帰処理トレース問題
【問題】
次の擬似言語は、整数 n を入力すると、n から 1 までの整数を順に出力し、その後に 1 から n までの整数を順に出力する関数 printNumbers を定義している。
function printNumbers(n):
if n == 0:
return
output n
printNumbers(n - 1)
output n
問1
printNumbers(3) を呼び出したとき、出力される数字を順番に書け。
問2
printNumbers(4) を呼び出したとき、関数 printNumbers は全部で何回呼び出されるか答えよ。
【解答・解説】
問1 の解答手順
- 呼び出しの流れ（左が先に進む方向、右が戻る方向）
n=3 → 出力3 → printNumbers(2)
n=2 → 出力2 → printNumbers(1)
n=1 → 出力1 → printNumbers(0)
n=0 → return
出力1
出力2
出力3
- 出力順
コピーする編集する3 2 1 1 2 3
✅ 答え： 3 2 1 1 2 3
問2 の解答手順
- 呼び出し回数は「n から 0 まで下がる」＋「戻りながら再帰終了」
- 実際に数える：
n=4 → 呼び出し1回
n=3 → 呼び出し2回
n=2 → 呼び出し3回
n=1 → 呼び出し4回
n=0 → 呼び出し5回（ここで終了）
✅ 答え： 5回
💡 今日のまとめ
午後問題では処理の流れをトレースできる力が大事
再帰処理は「行き」と「帰り」を意識する
呼び出し回数はベースケースに到達するまでの回数＋1
出力位置が前か後かで結果が変わる