基本情報 科目B 再帰のトレース練習｜コールスタックで階乗を1段ずつ追う

基本情報 科目B 再帰のトレース練習

基本情報技術者試験の科目Bで、探索・ソートと並んで頻出でありながら 最もつまずきやすい のが 再帰（さいき） です。再帰とは「関数が自分自身を呼び出す」しくみで、コードは短いのに頭の中で追うと「今どの呼び出しの中にいるのか」が分からなくなります。本記事は、再帰を コールスタック（呼び出しの積み重なり） を表に書きながら 1 段ずつ追う トレース で攻略する練習帳です。合計・最大値・線形探索のトレース練習・二分探索のトレース練習・ソート（整列）のトレース練習 の続編にあたります。

本記事は 過去問AI が学習用に作成したオリジナルの例題です。掲載している擬似言語は IPA の過去問・公式サンプルの転載ではなく、説明用に書き起こしたものです。擬似言語の正式な記述形式は必ず IPA 公式ページ で確認してください。記法そのものの読み方は 基本情報 科目Bの擬似言語 記法早見表 にまとめています。

再帰は「自分自身を呼び出す」関数

再帰関数には必ず 2 つの部分があります。

• 基底条件（ていしじょうけん）：それ以上は再帰せず、答えを直接返す行き止まり。これが無いと永遠に自分を呼び続けて止まりません
• 再帰呼び出し：問題を「1 段小さくした自分自身」に丸投げし、その結果を使って自分の答えを作る

この記事の例題は、次の約束ごとで進めます（科目Bの標準的なルールです）。

• 代入は ←（右の値を左の変数に入れる）。本記事の関数は主に return（呼び出し元へ値を返す）と ×（乗算）を使います
• 条件式の中の ＝・≦ は比較（「等しいか？」「以下か？」）
• 関数定義の先頭の ○ は「ここから関数の中身」を表します

記法そのものが不安なら、先に 記法早見表 で ← や return の扱いを確認してから戻ってくるとスムーズです。

例題のコード（階乗）

整数 n の 階乗（n! ＝ 1 × 2 × … × n）を再帰で求める関数です。たとえば 4! ＝ 1 × 2 × 3 × 4 ＝ 24 です。

○整数型: 階乗(整数型: n)
    if (n ≦ 1)
        return 1
    endif
    return n × 階乗(n - 1)

読み方はこうです。n が 1 以下なら（基底条件）そのまま 1 を返す。そうでなければ「n × （n を 1 減らした階乗）」を返す。つまり 階乗(4) は 4 × 階乗(3)、その 階乗(3) は 3 × 階乗(2)……と、答えが出せる 階乗(1) まで自分を呼び続けます。

ステップ1：呼び出しが深くなる（スタックが積み上がる）

階乗(4) を呼ぶと、基底条件に届くまで呼び出しがどんどん深くなります。新しい呼び出しは コールスタック に積まれます（あとから呼んだものが上に乗る）。

ここで重要なのは、段 1〜3 はまだ答えを返せず「途中で止まって待っている」 ことです。階乗(4) は「階乗(3) の結果が出たら 4 を掛けて返す」と決めただけで、まだ返していません。この「待っている呼び出し」がスタックに 4 段積まれた状態が、再帰の最も深いところです。

ステップ2：戻り値が巻き戻る（スタックが崩れる）

基底条件で 階乗(1) ＝ 1 が確定すると、こんどは 積んだ順と逆（深いところから）に戻り値が巻き戻っていきます。

最後に呼ばれた 階乗(1) が 最初に 返り、最初に呼ばれた 階乗(4) が 最後に 返ります。この「あとに入れたものが先に出る」順序を LIFO（後入れ先出し） と呼び、スタックそのものの動きです。途中で止まって待っていた各段が、下の段の結果を受け取って自分の掛け算を完成させ、24 という答えにたどり着きます。

つまずきやすい3つのポイント

1. 基底条件を必ず確認する。再帰は「いつ止まるか」が命です。階乗で if (n ≦ 1) を書き忘れると、n が 0 や負になっても呼び続け、コールスタックがあふれて止まります（スタックオーバーフロー）。問題のコードを見たら、まず「どの行で再帰せずに返すか」を探してください。
2. 戻り値は深いところから巻き戻る。トレースのとき「呼び出しは上から下、戻り値は下から上」と向きを分けて書くのがコツです。階乗(4) の答えは、いちばん奥の 階乗(1) が返ってこないと確定しません。
3. 各呼び出しの n は独立。階乗(4) の n と 階乗(3) の n は別物で、上書きされません。各段が自分専用の n を持って待っているイメージです。これを「n がどんどん書き換わる」と勘違いすると、戻り値の掛け算が合わなくなります。

もう一つの定番：フィボナッチ（枝分かれする再帰）

階乗は 1 段につき自分を 1 回 呼ぶ「一本道の再帰」ですが、フィボナッチ数（fib(n) ＝ fib(n-1) ＋ fib(n-2)）のように、1 段で自分を 2 回 呼ぶ「枝分かれする再帰」もよく出ます。こちらは呼び出しが木のように広がるため、トレースでは どちらの枝を今たどっているか を見失いやすくなります。追い方の基本は同じで、呼び出し（下り）と戻り値（上り）を分けて、基底条件から巻き戻すこと。まずは一本道で追いやすい階乗で、コールスタックの上り下りの感覚をつかむのがおすすめです。

トレースで詰まらないためのコツ

再帰は、「下り（呼び出し）」と「上り（戻り値）」で表を 2 つに分ける のが最大のコツです。下りでは n を 1 つずつ小さくしながら段を増やし、基底条件に着いたら折り返して、上りでは下の段の結果を受け取りながら式を完成させます。各段の n を必ず書いておくと、「今どの呼び出しの中にいるか」を見失いません。

次のステップ

再帰まで追えるようになれば、科目Bのアルゴリズム設問の主要パターンはほぼ制覇です。アルゴリズムに加えて、データ構造として頻出の スタックとキューのトレース練習 では、後入れ先出し（LIFO）と先入れ先出し（FIFO）の違いを操作表で追えます。基礎の 合計・最大値・線形探索のトレース練習、二分探索のトレース練習、ソート（整列）のトレース練習 をまだ見ていなければ先にそちらを、読む速度を上げる訓練法は 基本情報科目B｜擬似言語アルゴリズム読解の3ステップ訓練法 で扱っています。つまずきが記法なのかトレースなのか切り分けたいときは 科目Bがわからない人へ、科目B 全体の進め方は 基本情報技術者 科目B完全対策 が地図になります。

手を動かす練習台としては、過去問AI の 基本情報 アルゴリズムとプログラミング分野の過去問 が使えます（こちらは科目A 相当の選択式で、科目B そのものの形式ではない点だけ意識してください）。各問題ページの AI コパイロットに「この再帰関数を、呼び出しの下りと戻り値の上りに分けて 1 段ずつトレースして」と頼めば、本記事と同じ追い方を対話でその場で再現できます。

よくある質問

Q. 基底条件が無いと再帰はどうなりますか？ 止まらなくなります。再帰は基底条件（それ以上呼ばずに答えを返す行き止まり）に到達して初めて巻き戻せます。階乗で if (n ≦ 1) を書き忘れると、n が 0 や負になっても自分を呼び続け、コールスタックが積み上がり続けてあふれます（スタックオーバーフロー）。問題のコードを読むときは、まず「どの行で再帰せずに値を返すか」を最初に確認してください。

Q. 戻り値はどの順番で返ってきますか？ 最後に呼ばれたものから先に返ります。階乗(4) → 階乗(3) → 階乗(2) → 階乗(1) の順に呼び出しが深くなり、基底の 階乗(1) が 1 を返したあと、階乗(2)＝2、階乗(3)＝6、階乗(4)＝24 と逆向きに巻き戻ります。「あとに入れたものが先に出る（後入れ先出し・LIFO）」というスタックの順序です。呼び出しは下り、戻り値は上りと向きを分けて表に書くと混乱しません。

Q. 各呼び出しの変数 n は共有されますか？ 共有されません。階乗(4) の n と 階乗(3) の n はそれぞれ別の値で、上書きされません。各呼び出しは自分専用の変数を持ったまま、下の段の結果が返るのを待っています。n が 1 つの箱を全員で書き換えていると勘違いすると、戻り値の掛け算が合わなくなるので注意してください。

Q. 再帰とループ（繰り返し）はどちらで書くべきですか？ どちらでも同じ計算はできますが、科目Bでは「再帰で書かれたコードを正しく追えるか」が問われます。階乗やフィボナッチのように「自分より 1 段小さい問題の答えを使う」構造は再帰で素直に書けます。実務では深い再帰はスタックを消費するためループに書き換えることもありますが、試験対策としては、まず再帰のコードをトレースで追えるようにするのが先決です。

まとめ

• 再帰は 自分自身を呼ぶ 関数。必ず 基底条件（行き止まり）と 再帰呼び出し の 2 つを持つ
• 呼び出しは コールスタック に積まれ、基底条件まで深くなってから巻き戻る
• 戻り値は 深いところから（後入れ先出し・LIFO） 巻き戻る。階乗(1)→(2)→(3)→(4) の順で 1→2→6→24
• 各段の n は独立。上書きされず、自分専用の値を持って待つ
• トレースは 下り（呼び出し）と上り（戻り値）で表を分ける と迷子にならない

線形探索 → 二分探索 → ソート → 再帰とトレースで追えるようになれば、科目Bのアルゴリズム設問は読めない問題がほぼ無くなります。