最終更新日:2026年11月1日
fe fe-technology algorithm programming trace
まず結論
再帰関数のトレースでは、同じ関数名でも呼び出しごとに別の状態を持つことが重要です。呼び出し元は一時停止し、呼び出し先の結果が戻ると、その続きから再開します。
このページは再帰処理の基本や再帰関数の展開を読んだ後、実行位置を見失わないための練習に使います。
直感的な説明
再帰は、途中まで書いた計算をいったん保留して、別の計算を先に済ませる仕組みです。
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ステップずつ動かす再帰トレース
再帰関数は、どの順に呼び出され、どの順に値を返すでしょうか?
- まず
f(3)を選び、「次へ」で1ステップずつ進める。 - 実行中のコード・呼び出しスタック・戻り値を見比べる。
- 戻る順番を確認したら、
f(4)でも試す。
見るポイント: 戻り値は、関数を数値に置き換える過程をカードで表示します。最新の結果は青色で強調されます。
再帰の行きと戻りを確認
① 実行中のコード
② 呼び出しスタック(下が最新)
③ 戻り値の流れ
青い行=今のステップで実行した行。青いスタック枠=現在処理中の呼び出し。灰色=呼び出し先の結果を待つ呼び出し。戻り値の青いカード=直近で確定した計算結果。
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) は結果を待っている |
| 終了条件に達したら全部終了 | そこから呼び出し元へ順番に戻る |
| 呼び出し順と戻る順は同じ | スタックなので戻る順番は逆 |
まとめ(試験直前用)
- 終了条件を先に確認する。
- 呼び出すたびに別のフレームを積む。
- 呼び出し元は待機中として残す。
- 戻り値が確定したら一段ずつ戻る。
- 再開位置は「呼び出しの後」である。