Skip to the content.

最終更新日:2026年11月1日

まず結論

再帰関数のトレースでは、同じ関数名でも呼び出しごとに別の状態を持つことが重要です。呼び出し元は一時停止し、呼び出し先の結果が戻ると、その続きから再開します。

このページは再帰処理の基本や再帰関数の展開を読んだ後、実行位置を見失わないための練習に使います。

直感的な説明

再帰は、途中まで書いた計算をいったん保留して、別の計算を先に済ませる仕組みです。

f(3) = 3 × f(2)  ← f(2)の結果を待つ
f(2) = 2 × f(1)  ← f(1)の結果を待つ
f(1) = 1         ← ここで止まる

戻る順番は逆になります。

f(1) = 1 → f(2) = 2 → f(3) = 6

定義・仕組み

  • 呼び出しスタック:現在実行中の呼び出しと、結果を待っている呼び出しを保持する仕組み
  • スタックフレーム:1回の呼び出しに対応する引数・ローカル変数・戻り先などの情報
  • 終了条件(基底条件):それ以上自分自身を呼び出さず、値を返す条件
  • 戻り値:呼び出し先から呼び出し元へ渡される結果

次の例は説明用のオリジナル擬似言語です。

○整数型: f(整数型: n)
  if (n = 1)
    return 1
  endif
  return n × f(n - 1)

見るポイント: return n × f(n - 1) では、先に f(n - 1) の結果を待ち、戻ってきた値に n を掛けます。

科目Aでどう出る?

再帰・終了条件・スタック(後入れ先出し)の関係を区別します。終了条件に近づく引数の変化を確認しましょう。

科目Bでどう使う?

1ステップずつ動かす再帰トレース

再帰関数は、どの順に呼び出され、どの順に値を返すでしょうか?

  1. まず f(3) を選び、「次へ」で1ステップずつ進める。
  2. 実行中のコード・呼び出しスタック・戻り値を見比べる。
  3. 戻る順番を確認したら、f(4) でも試す。

見るポイント: 戻り値は、関数を数値に置き換える過程をカードで表示します。最新の結果は青色で強調されます。

再帰の行きと戻りを確認

① 実行中のコード

f(n)
 if (n = 1)
  return 1
 return n × f(n - 1)

② 呼び出しスタック(下が最新)

まだ呼び出していません。

③ 戻り値の流れ

まだ戻り値はありません。

開始前です。次のステップを押してください。

青い行=今のステップで実行した行。青いスタック枠=現在処理中の呼び出し。灰色=呼び出し先の結果を待つ呼び出し。戻り値の青いカード=直近で確定した計算結果。

JavaScriptを使えない場合は、以下の静的なトレース表でも同じ順番を確認できます。

順番 動作 スタックの状態(下が最新)
1 f(3) 呼び出し f(3)
2 f(2) 呼び出し、f(3) は待機 f(3), f(2)
3 f(1) 呼び出し、f(2) は待機 f(3), f(2), f(1)
4 f(1) が 1 を返す f(3), f(2)
5 f(2) が 2 × 1 = 2 を返す f(3)
6 f(3) が 3 × 2 = 6 を返す 空

応用:3つのスタックを再帰で移す

次は、データ用スタック A・B・C と 再帰の呼び出しスタック を区別する練習です。これは説明用のオリジナル例で、各スタックの右端を取り出し口とします。

初期値:A = [1, 2, 3]、B = [1, 2, 3]、C = [1, 2, 3]

f():
  Aが空なら何もしない
  そうでなければ
    AからpopしてCへpush
    f()を呼ぶ
    CからpopしてBへpush

見るポイント: 再帰呼び出しの前は A → C、再帰呼び出しの後は C → B です。「次へ」を押し、戻り処理がどの呼び出しから始まるかを確認してください。

A・B・Cと再帰の行き・戻り

開始前です。

① データ用スタック(右端が一番上)

② 呼び出しスタック(下が最新)

JavaScriptが無効な場合も、次の表で確認できます。

段階 A B C 実行内容
開始 [1,2,3] [1,2,3] [1,2,3] 初期状態
行き① [1,2] [1,2,3] [1,2,3,3] 3をCへ
行き② [1] [1,2,3] [1,2,3,3,2] 2をCへ
行き③ [] [1,2,3] [1,2,3,3,2,1] 1をCへ
終了条件 [] [1,2,3] [1,2,3,3,2,1] Aが空
戻り③ [] [1,2,3,1] [1,2,3,3,2] 1をBへ
戻り② [] [1,2,3,1,2] [1,2,3,3] 2をBへ
戻り① [] [1,2,3,1,2,3] [1,2,3] 3をBへ

最初にAから取り出す順番は 3 → 2 → 1 ですが、再帰から戻るときにBへ入れる順番は 1 → 2 → 3 です。Bの最終状態は [1,2,3,1,2,3] になります。

よくある誤解・混同

誤解 正しい見方
同じ関数なので n も一つだけ 呼び出しごとに n が別々に存在する
f(3) が f(2) を呼んだら f(3) は終了 f(3) は結果を待っている
終了条件に達したら全部終了 そこから呼び出し元へ順番に戻る
呼び出し順と戻る順は同じ スタックなので戻る順番は逆

まとめ(試験直前用)

  1. 終了条件を先に確認する。
  2. 呼び出すたびに別のフレームを積む。
  3. 呼び出し元は待機中として残す。
  4. 戻り値が確定したら一段ずつ戻る。
  5. 再開位置は「呼び出しの後」である。

関連:スタックの仕組み・IPA公式:基本情報技術者試験

© 2024-2026 stemtazoo. All rights reserved.