基本情報技術者試験対策（56）「擬似言語（17）再帰」

基本情報技術者試験の科目Bでは、擬似言語（疑似コード）を用いたプログラム問題が出題される。今回のテーマは「再帰（さいき）」である。再帰は多くの受験者がつまずきやすいが、仕組みさえ理解すれば得点源にできる分野である。

再帰とは何か

再帰とは、関数（手続き）が自分自身を呼び出すという処理の仕組みである。日常的な例で言えば、「鏡に映った鏡」のように、同じ構造が内側にどんどん入れ子になっていくイメージに近い。

再帰処理を書く際には、必ず次の2つの要素が必要になる。

1. 基底部（ベースケース）：これ以上再帰呼び出しをせず、直接答えを返す条件
2. 再帰部（再帰ステップ）：問題を少し小さくして、自分自身を呼び出す部分

基底部がないと、関数が無限に自分自身を呼び出し続けてしまい、スタックオーバーフローなどの異常終了を引き起こす。試験問題でも「基底部が欠けているとどうなるか」という形で出題されることがある。

擬似言語での基本構文

基本情報技術者試験の擬似言語では、再帰は通常の手続き（関数）呼び出しと同じ記法で表現される。特別なキーワードがあるわけではなく、手続きの中で自分自身の名前を呼び出しているかどうかで再帰だと判断する。

○整数型: kaijo(整数型: n)
　if (n が 0 と等しい)
　　return 1
　else
　　return n * kaijo(n - 1)
　endif

上記は階乗（n!）を求める代表的な再帰の例である。n が 0 のときが基底部、else 節が再帰部にあたる。

具体例1：階乗のトレース

kaijo(4) を呼び出した場合の流れを、実際に手を動かしてトレースしてみる。試験本番でも、このように呼び出しの流れを図や表に書き出すことが正答への近道になる。

kaijo(4)
 = 4 * kaijo(3)
 = 4 * (3 * kaijo(2))
 = 4 * (3 * (2 * kaijo(1)))
 = 4 * (3 * (2 * (1 * kaijo(0))))
 = 4 * (3 * (2 * (1 * 1)))
 = 4 * (3 * (2 * 1))
 = 4 * (3 * 2)
 = 4 * 6
 = 24

ポイントは、呼び出しが深く潜っていく段階（下り）と、基底部に到達した後に値を戻しながら計算していく段階（上り）の2つのフェーズがあるということである。試験問題では、この「下り」の途中で止めた状態や、「上り」の途中の計算結果を問う設問がよく出る。

スタックのイメージで理解する

再帰呼び出しの裏側では、呼び出しのたびに「今どこまで計算していたか」という情報がスタック（後入れ先出し：LIFO）に積まれていく。

kaijo(0) ← 一番あとに呼ばれて、一番先に返る
kaijo(1)
kaijo(2)
kaijo(3)
kaijo(4) ← 一番先に呼ばれて、一番あとに返る

この「後入れ先出し」の性質を理解しておくと、再帰関数の中に複数の再帰呼び出しがある場合（後述のフィボナッチ数列など）でも、処理順序を混乱せずに追うことができる。

具体例2：フィボナッチ数列（複数回の再帰呼び出し）

再帰部の中で自分自身を2回呼び出すパターンも頻出である。フィボナッチ数列を求める手続きを見てみる。

○整数型: fib(整数型: n)
　if (n が 0 と等しい)
　　return 0
　elseif (n が 1 と等しい)
　　return 1
　else
　　return fib(n - 1) + fib(n - 2)
　endif

このタイプは基底部が2つ存在する点、そして1回の呼び出しから2方向に呼び出しが枝分かれしていく点が特徴である。fib(4) を呼び出すと、呼び出しの木（再帰木）は次のように広がる。

fib(4)
├─ fib(3)
│   ├─ fib(2)
│   │   ├─ fib(1) → 1
│   │   └─ fib(0) → 0
│   └─ fib(1) → 1
└─ fib(2)
    ├─ fib(1) → 1
    └─ fib(0) → 0

fib(1) や fib(0) のような同じ呼び出しが何度も重複して発生している点に注目してほしい。これは、この素朴な再帰実装の効率が悪いことを示しており、応用情報や高度試験ではメモ化（計算結果を保存して再利用する手法）とセットで問われることもある。基本情報では、まず「重複呼び出しが発生している」ことに気づけるかがポイントになる。

試験でよくある出題パターン

• トレース問題：与えられた引数で再帰関数を実行した際の戻り値や、途中の変数の値を答えさせる
• 穴埋め問題：基底部の条件式や、再帰呼び出しの引数部分を空欄にして選ばせる
• 呼び出し回数を数える問題：再帰関数が何回呼び出されるかを問う（特にフィボナッチ型で頻出）
• 反復（ループ）との書き換え：再帰で書かれた処理と同じ動作をする、for文やwhile文を使った反復版を選ばせる、あるいはその逆

反復との書き換え問題は特に頻出である。例えば階乗の再帰版は、次のような反復版と同じ結果になる。

○整数型: kaijo_loop(整数型: n)
　整数型: kekka
　kekka を 1 とする
　for (i を 1 から n まで 1 ずつ増やす)
　　kekka を kekka * i とする
　endfor
　return kekka

再帰と反復は「同じ処理を異なる書き方で表現したもの」であるという対応関係を意識しておくと、この手のひっかけ問題に強くなる。

学習のポイント

1. 必ず基底部を探す：問題文中のif文で、再帰呼び出しをしていない分岐がどれかをまず確認する
2. 手を動かしてトレースする：暗算で追おうとせず、呼び出しの様子を紙に書き出す
3. 戻り値がどこに使われるか意識する：return の右辺に再帰呼び出しが含まれる場合、その戻り値がどう計算に使われるかを追う
4. 呼び出し回数・スタックの深さに注意する：特にフィボナッチ型では、呼び出し回数が指数的に増えることを理解しておく

まとめ

再帰は「自分自身を呼び出す」というシンプルな仕組みでありながら、基底部・再帰部の組み合わせによって様々な処理を表現できる強力な考え方である。基本情報技術者試験の科目Bでは、階乗やフィボナッチ数列のような典型パターンを題材に、トレース力・穴埋め力を問う問題が繰り返し出題されている。まずは典型パターンを自分の手でトレースできるようにし、反復処理との対応関係も合わせて押さえておくとよい。