再帰関数の仕組みとコールスタック：ベースケースの見極めと再帰呼び出しトレース術

アルゴリズムを数学的に美しく、簡潔に記述するための強力な手法が「再帰呼び出し（リカーシブコール：Recursive Call）」です。

基本情報技術者試験の科目B（アルゴリズム）では、階乗計算、フィボナッチ数列、ユークリッドの互除法、木構造の深さ優先走査などで再帰関数が必ずと言っていいほど出題されます。

再帰が苦手な受験生の多くは「関数の中で自分自身を呼ぶと、頭の中で無限ループしてしまう」という壁にぶつかります。本記事では、コンピュータ内部の「コールスタック（スタックフレーム）」の動きを完全可視化し、下降と巻き戻りのトレース術を伝授します。

1. 再帰関数を成立させる「2大基本定理」

すべての正しい再帰関数は、例外なく以下の2つの要素で構成されています。

【注意】もしベースケースが存在しないか、引数の減少が停止条件を飛び越えてしまうと、自分自身を無限に呼び出し続け、メモリのスタック領域を食いつぶして「スタックオーバーフロー（Stack Overflow）」エラーで強制停止します。

2. コールスタックの動き：下降（Push）と巻き戻り（Pop）の完全追跡

コンピュータは関数が呼び出されるたび、その関数の「引数」「ローカル変数」「呼び出し元への戻り番地」をセットにした「スタックフレーム」をコールスタック（LIFO構造）へ積み上げます。

// 階乗を計算する再帰関数 fact(n)
function fact(n):
    if (n ≦ 1):
        return 1
    endif
    return n * fact(n - 1)

// fact(4) を実行したときの内部トレース
// 【下降フェーズ：スタックにフレームが積み上がる】
//   fact(4) 呼出し → fact(3) の結果待ち（中断）
//     fact(3) 呼出し → fact(2) の結果待ち（中断）
//       fact(2) 呼出し → fact(1) の結果待ち（中断）
//         fact(1) 呼出し → n=1 なので「1」を即座にリターン！（ベースケース到達！）
//
// 【上昇フェーズ：スタックから降ろされながら計算が巻き戻る】
//         fact(1) が 1 を返却
//       fact(2) が 2 * 1 = 2 を計算して返却
//     fact(3) が 3 * 2 = 6 を計算して返却
//   fact(4) が 4 * 6 = 24 を計算して最終結果確定！

3. 科目Bで出題される「4大再帰アルゴリズム」

試験に出る再帰アルゴリズムは、以下の4つのパターンを網羅しておけば確実に得点できます。

4. 試験本番での手書きトレース術：スタックボックス法

試験会場のメモ用紙で再帰問題を解く際は、頭の中で解こうとせず、「下から上へ四角い箱（スタックフレーム）を積み上げるメモ」を書きましょう。

1. メモ用紙に四角い枠を描き、呼び出された関数名と引数を記入する（例: [fact(4): 4 * ?]）。

2. 再帰呼び出しが発生したら、その上に新しい箱を描いて積み上げる（例: [fact(3): 3 * ?]）。

3. ベースケースに到達したら、戻り値を確定させ（例: fact(1) = 1）、矢印で下の箱へ値を渡しながら箱に斜線を引いて消していく。

4. 一番下の最初の箱まで戻り値が到達したときの計算結果が、最終的な正解となる。

5. 実戦演習問題とステップ別解説

【問1：再帰関数の戻り値トレース】

次の再帰関数 func(n) に対して、func(5) を呼び出したときの戻り値はどれか。

整数型: func(整数型: n)
    if (n ≦ 0)
        return 0
    endif
    return n + func(n - 2)

• ア：6

• イ：9

• ウ：12

• エ：15

【正解】イ

【解説】引数が 2 ずつ減少する再帰呼び出しをステップ順に追跡します。・func(5) = 5 + func(3)・func(3) = 3 + func(1)・func(1) = 1 + func(-1)・func(-1): n ≦ 0 の条件を満たすためベースケースとなり、0 を返却。巻き戻し計算を行います：・func(1) = 1 + 0 = 1・func(3) = 3 + 1 = 4・func(5) = 5 + 4 = 9したがって、戻り値は「9」となります。正解は イ です。

【問2：ユークリッドの互除法による最大公約数の導出】

正の整数 a, b に対する最大公約数を求める関数 gcd(a, b) が以下のように定義されている。gcd(48, 18) を実行した際、ベースケースに到達するまでに gcd が呼び出される総回数（最初の呼び出しを含む）はどれか。

整数型: gcd(整数型: a, 整数型: b)
    if (b = 0)
        return a
    endif
    return gcd(b, a mod b)

• ア：2回

• イ：3回

• ウ：4回

• エ：5回

【正解】ウ

【解説】呼び出しごとの引数の変化をトレースします。1回目: gcd(48, 18) → 48 mod 18 = 12 なので、gcd(18, 12) を呼び出す。2回目: gcd(18, 12) → 18 mod 12 = 6 なので、gcd(12, 6) を呼び出す。3回目: gcd(12, 6) → 12 mod 6 = 0 なので、gcd(6, 0) を呼び出す。4回目: gcd(6, 0) → b = 0 が成立し、ベースケースとなり 6 を返却して終了。したがって、最初の呼び出しからベースケース到達までの総呼び出し回数は「4回」です。正解は ウ です。