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

再帰で呼び出した関数から戻った後、どの計算が再開されるのでしょうか？

呼び出し元に残った計算を、後から呼んだ順に再開します。停止条件へ向かう段階と、戻り値を受け取る段階を分けて追います。

停止する再帰の二つの確認点

ここでは停止する計算の再帰を扱います。停止条件と、各再帰呼出しがその条件へ近づくことを確認します。単に引数を減らすだけでは、入力範囲によって停止しない場合があります。

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

コールスタックの動き：下降（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 を計算して最終結果確定！

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

階乗、フィボナッチ、互除法、木の走査は、呼出しと戻り値の練習に適した代表例です。必要な入力範囲と停止条件をそれぞれ確認します。

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

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

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

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

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

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

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

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

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

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

1. 6

2. 9

3. 12

4. 15

【正解】イ

func(5)→func(3)→func(1)→func(−1)と呼びます。func(−1)は0を返します。戻ると1＋0＝1、3＋1＝4、5＋4＝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)

1. 2回

2. 3回

3. 4回

4. 5回

【正解】ウ

呼出しはgcd(48,18)、gcd(18,12)、gcd(12,6)、gcd(6,0)の順です。最後が停止条件なので、初回を含めて4回、再帰による追加呼出しは3回です。戻り値は6で、正解はウです。

停止条件があっても停止しない入力

nが0以上の階乗関数で、停止条件がn＝0、再帰がfact(n−2)の場合、奇数のnからは0へ到達しません。入力を制限するか、処理の目的に合う停止条件と更新に変える必要があります。

スタックを使い果たす前にエラーになることもあり、処理系の制限や末尾呼出し最適化によって挙動は変わります。深い再帰では反復処理への書換えも選択肢です。

呼出し数とスタックの深さを区別する

素朴なfib(4)は、fib(3)とfib(2)を呼び、同じ引数を何度も計算します。初回を含む総呼出し数は9回ですが、同時に積まれる最大フレーム数は4です。

メモ化は同じ引数の結果を保存して再計算を減らします。素朴なフィボナッチの時間は指数的ですが、メモ化では各nを1回計算してO(n)にできます。スタック使用量と計算回数は別に評価します。

出典と仕様を確認する

IPA：FEシラバス Ver.9.2

IPA：試験で使用する用語・プログラム言語 Ver.5.1

Python公式：再帰の深さ制限