擬似言語の再帰とは（全体像）
擬似言語の再帰は、「関数の中で自分自身をもう一度呼ぶ」コードを読み解く問題。科目Bでは、こうした再帰のコードを手で実行して（トレースして）、最後の答えを求めることが問われる。
再帰には必ず2つの要素がある。
- 基底条件 … これ以上分けられない最小のケース（ここで止まる）。例：`n = 0` のとき。
- 再帰呼び出し … 自分自身を、ひとまわり小さい問題で呼ぶ。
大事なのは、基底条件がないと止まらないこと。終わりの条件がないと自分を呼び続け、メモリを使い切ってスタックオーバーフロー（あふれ）になる。
詳しく：トレース実行だけ覚えれば戦える
ここが記事の心臓部。代表例階乗 fact(n)で、再帰の追い方（トレース）を見る。
``` ○整数型 fact（整数型: n） if (n ＝ 0) // 基底条件 return 1 endif return n × fact(n − 1) // 再帰呼び出し ```
これを `fact(3)` で1段ずつ展開すると、こうなる。
fact(3) のトレース
| 段階 | 式 |
|---|---|
| 1 | fact(3) ＝ 3 × fact(2) |
| 2 | ＝ 3 × 2 × fact(1) |
| 3 | ＝ 3 × 2 × 1 × fact(0) |
| 4 | fact(0)＝1 なので ＝ 3 × 2 × 1 × 1 ＝ 6 |
ポイントは、基底条件（fact(0)＝1）に届くまで深く進み、そこから答えを計算しながら戻ること。途中の呼び出しを紙に書き出すと迷わない。つまり、行き（深く進む）と帰り（計算しながら戻る）の2方向で追うのがトレースのコツ、というわけだね。
トレースのコツ
| コツ | 内容 |
|---|---|
| 呼び出しを書き出す | fact(3)→fact(2)→… と紙に積む |
| 引数と戻り値を追う | 各呼び出しの「入れた値」と「返る値」を記録 |
| 基底条件で折り返す | 最小ケースに届いたら、戻りながら計算 |
なお、再帰とふつうの繰り返し（ループ）は、実行のされ方が違う（再帰は呼び出しが積み重なる）。だから「再帰はループと同じ」と思い込まず、トレースで動きを確かめるのが大事だ。
わかりやすく言い換えると
要するに、擬似言語の再帰は「マトリョーシカ人形を開けて、また閉じる」ことだ。
①深く進む … 人形を開け続ける（fact(3)→fact(2)→fact(1)→fact(0)）
②基底条件 … いちばん小さい人形（fact(0)＝1）。ここで開くのをやめる
③戻りながら計算 … 小さい人形から順に閉じていく（1→1→2→6）
トレースは、この「開けて・止まって・閉じる」を紙に書き出して追うこと。手で1段ずつ追えば、複雑に見える再帰も答えが出せる、というわけだね。
試験のツボ
🔴 一番出る：トレース実行の進め方
①基底条件まで深く進み、戻りながら計算する
②fact(3)＝3×2×1×1＝6 のように1段ずつ追う
🔴 次に出る：再帰の必須要素
①基底条件（最小ケースで止まる）
②再帰呼び出し（より小さな問題で自分を呼ぶ）
🟡 押さえると安定：注意点
①基底条件がないと止まらずスタックオーバーフロー
②再帰とループは実行のされ方が違う（呼び出しが積み重なる）
よくある間違い
①「再帰には基底条件がなくても正しく止まる」→ ✗ 基底条件がないと止まらず、スタックオーバーフローになる。
②「再帰は手で追わなくても、見ただけで答えが分かる」→ ✗ 科目Bでは手で1段ずつ追うトレース実行が必要。
③「fact(3)はfact(0)に届かず、途中で勝手に止まる」→ ✗ 基底条件のfact(0)＝1まで進み、そこから戻りながら6を計算する。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（トレース）
fact(n)＝n×fact(n−1)、fact(0)＝1のとき、fact(3)の値として正しいものはどれか。
- 基底条件fact(0)＝1まで展開し、3×2×1×1を計算して6になる
- 基底条件には届かず途中で止まるため、fact(3)は3のままになる
- 再帰呼び出しは無視され、fact(3)はそのまま3を返すものである
- 基底条件を2回使うため、fact(3)は3×2×1×1×1で12になる
解答は 1 だよ。
fact(3)は3×fact(2)→3×2×fact(1)→…→fact(0)＝1まで展開し、戻りながら3×2×1×1＝6になるんだ。基底条件まで進んで折り返すのがコツだよ。
選択肢2は「届かず止まる」が誤り。選択肢3は「再帰を無視」が誤り。選択肢4は「12」になる計算が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 展開して3×2×1×1＝6 |
| 2 | ✗ | 基底条件まで展開される |
| 3 | ✗ | 再帰呼び出しが行われる |
| 4 | ✗ | 正しくは6 |
オリジナル問題2（必須要素）
擬似言語の再帰の必須要素に関する次の記述のうち、正しいものはどれか。
- 再帰呼び出しだけがあればよく、止まるための条件は不要なものである
- 基底条件だけがあればよく、自分自身を呼ぶ部分は不要なものである
- 基底条件（止まる最小ケース）と再帰呼び出しの両方ともに必要である
- 再帰には条件も呼び出しも要らず、変数の宣言だけで動くものである
解答は 3 だよ。
再帰には基底条件（止まる最小ケース）と再帰呼び出し（小さな問題で自分を呼ぶ）の両方が必要なんだ。どちらが欠けても正しく動かないよ。
選択肢1は「止まる条件が不要」が誤り。選択肢2は「呼び出しが不要」が誤り。選択肢4は「条件も呼び出しも要らない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 基底条件がないと止まらない |
| 2 | ✗ | 再帰呼び出しも必要 |
| 3 | ✓ | 基底条件と再帰呼び出しの両方 |
| 4 | ✗ | 両方の要素が必要 |
オリジナル問題3（注意点）
擬似言語の再帰の注意点に関する次の記述のうち、正しいものはどれか。
- 基底条件を書き忘れても、再帰は安全に止まるので問題は起きないとされる
- 基底条件を書き忘れると止まらず、スタックオーバーフローになってしまう
- 再帰はループとまったく同じ動きなので、トレースで追う必要はないとされる
- 再帰呼び出しは1回しか実行されず、深く進むことはないものとされている
解答は 2 だよ。
基底条件を書き忘れると止まらず、スタックオーバーフローになってしまうんだ。再帰では「止まる条件」がいちばん大事だよ。
選択肢1は「書き忘れても安全」が誤り。選択肢3は「ループと同じ・トレース不要」が誤り。選択肢4は「1回しか実行されない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 書き忘れると止まらない |
| 2 | ✓ | 止まらずスタックオーバーフロー |
| 3 | ✗ | 手でトレースして追う必要がある |
| 4 | ✗ | 基底条件まで深く進む |
まとめ
押さえどころ
- 🔴 トレース実行 ＝ 基底条件まで深く進み、戻りながら計算（fact(3)＝3×2×1×1＝6）。
- 🔴 必須要素 ＝ 基底条件（止まる最小ケース）と再帰呼び出しの両方。
- 🟡 注意点 ＝ 基底条件がないとスタックオーバーフロー。再帰はループと実行のされ方が違う。
次に学ぶ
- 再帰（末尾再帰・メモ化） ── 再帰を速く・安全にする工夫（末尾再帰・メモ化）。トレースの次のステップとして押さえたい。
- 擬似言語の制御構造 ── 再帰と並ぶ、繰り返し（ループ）の書き方。両方をトレースできると科目Bが読める。
執筆: SikakuQuest編集部