11　再帰

「自分自身を呼び出す」という発想——再帰。

関数の中から、同じ関数をもう一度呼び出す——これを再帰（さいき）と言います。 最初に聞くと「無限ループになるのでは？」と思うかもしれません。 しかし正しく設計された再帰には必ず「終了条件（基底条件）」があり、 問題を少しずつ小さくしながら最終的に止まります。

再帰は「木構造の探索」「ソートアルゴリズム」「数学的な定義の実装」など、 繰り返し文では書きにくい問題を簡潔に解決できます。 基本情報技術者試験でも頻出のテーマです。

1. 再帰の仕組み

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

① 基底条件（終了条件） 再帰を止める条件。 これがないと無限ループになる ② 再帰呼び出し 自分自身を呼び出す。 問題を少しずつ小さくする

2. 最もシンプルな例：階乗

n の階乗（n!）は「1からnまでの整数をすべて掛け合わせた値」です。
例：4! = 4 × 3 × 2 × 1 = 24

これを再帰的に定義すると：

○整数型: factorial(整数型: n)
    if ( n が 0 と等しい )
        return 1               // ① 基底条件
    endif
    return n * factorial(n - 1) // ② 再帰呼び出し

factorial(4) の展開過程

factorial(4) = 4 × factorial(3) factorial(3) = 3 × factorial(2) factorial(2) = 2 × factorial(1) factorial(1) = 1 × factorial(0) factorial(0) = 1 ← 基底条件 ここで止まる 戻り値が戻っていく： 1 → 1×1=1 → 2×1=2 → 3×2=6 → 4×6=24
読み方：上から下へ「呼び出しが積み重なり」、基底条件に到達したら下から上へ「戻り値が返ってくる」イメージです。

3. 別の例：合計を再帰で求める

1からnまでの整数の合計を再帰で書いてみます。

○整数型: sum(整数型: n)
    if ( n が 1 と等しい )
        return 1               // 基底条件
    endif
    return n + sum(n - 1)      // 再帰呼び出し

sum(4) の展開

呼び出し 計算式 戻り値 sum(4) を呼ぶ 4 + sum(3) 待機中… └ sum(3) を呼ぶ 3 + sum(2) 待機中… └ sum(2) を呼ぶ 2 + sum(1) 待機中… └ sum(1) 基底条件 n=1 → return 1 1 を返す sum(2) に戻る 2 + 1 = 3 3 を返す sum(3) に戻る 3 + 3 = 6 6 を返す sum(4) 完了 4 + 6 = 10 10 を返す

4. 再帰とfor文の比較

同じ問題をfor文と再帰の両方で解いてみます。

for文で合計 整数型: total ← 0 for ( i を 1 から n まで ) total ← total + i endfor 繰り返しで順に足す 再帰で合計 ○整数型: sum(整数型: n) if ( n が 1 と等しい ) return 1 return n + sum(n-1) 自分自身を使って定義する
どちらを使うべき？
for文の方が処理効率が良い場合が多いです。ただし木構造の探索など「再帰の方が自然に書ける」問題も多くあります。 試験では「このコードは再帰を使っている」と見抜いて読む力が問われます。

5. 基底条件を忘れると…

基底条件のない再帰は無限ループ（スタックオーバーフロー）になります。

関数を呼び出すたびに「戻るための情報」がメモリに積み重なります（これをコールスタックといいます）。 永遠に呼び出し続けるとメモリが溢れてプログラムが強制終了します。
必ず「n が 0 になったら止まる」などの終了条件を設けましょう。

6. 理解度チェック問題

問題11-1

次の関数を factorial(4) として呼び出したとき、戻り値はいくつか。

○整数型: factorial(整数型: n)
    if ( n が 0 と等しい )
        return 1
    endif
    return n * factorial(n - 1)
解説を表示 正解：ウ
factorial(4) = 4 × factorial(3) = 4 × 3 × factorial(2) = 4 × 3 × 2 × factorial(1) = 4 × 3 × 2 × 1 × factorial(0) = 4 × 3 × 2 × 1 × 1 = 24

問題11-2

次の関数を sum(5) として呼び出したとき、戻り値はいくつか。

○整数型: sum(整数型: n)
    if ( n が 1 と等しい )
        return 1
    endif
    return n + sum(n - 1)
解説を表示 正解：イ
5 + 4 + 3 + 2 + 1 = 15。sum(n) は 1 から n までの合計を返します。

問題11-3

次の関数を count(5) として呼び出したとき、何回 "●" が出力されるか。

○ count(整数型: n)
    if ( n が 0 と等しい )
        return
    endif
    "●" を出力する
    count(n - 1)
解説を表示 正解：エ
count(5)→"●"→count(4)→"●"→count(3)→"●"→count(2)→"●"→count(1)→"●"→count(0)で終了。5回出力されます。

問題11-4　空欄補充

次の関数は n の階乗を返す。空欄 ［ A ］ に入る基底条件として正しいものを選びなさい。

○整数型: factorial(整数型: n)
    if ( ［ A ］ )
        return 1
    endif
    return n * factorial(n - 1)
解説を表示 正解：ア
0! = 1 が数学的な定義です。n=0 のときに 1 を返すことで再帰が止まります。
イ・ウ・エはいずれも再帰が止まる条件として機能しません。

問題11-5　空欄補充

次の関数は n 番目のフィボナッチ数を返す（fib(1)=1, fib(2)=1, fib(n)=fib(n-1)+fib(n-2)）。空欄 ［ B ］ に入るものとして正しいものを選びなさい。

○整数型: fib(整数型: n)
    if ( n が 1 以下 )
        return 1
    endif
    return ［ B ］
解説を表示 正解：ウ
フィボナッチ数の定義は「直前の2つの値の和」です。
fib(3) = fib(2) + fib(1) = 1 + 1 = 2、fib(4) = fib(3) + fib(2) = 2 + 1 = 3 と続きます。
アは fib(n) が自分自身を参照しており無限ループになります。