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文の方が処理効率が良い場合が多いです。ただし木構造の探索など「再帰の方が自然に書ける」問題も多くあります。 試験では「このコードは再帰を使っている」と見抜いて読む力が問われます。

呼ばれるたびに、別のメモリ領域で同じコードが動くイメージ

sum(3) を呼ぶと、再帰の中で sum(2)、sum(1) が呼ばれます。 関数のコード自体はメモリ上に1つだけですが、呼び出されるたびに別のメモリ領域が確保され、それぞれが自分用の n を持って動くと考えると分かりやすいです。 下に同じ関数を3つ並べたので、それぞれの n の値の違いを見てみてください。 

○整数型: sum(整数型: n)   // n = 3 で呼ばれる
    if ( n が 1 と等しい )
        return 1
    endif
    return n + sum(n-1)
○整数型: sum(整数型: n)   // n = 2 で呼ばれる
    if ( n が 1 と等しい )
        return 1
    endif
    return n + sum(n-1)
○整数型: sum(整数型: n)   // n = 1 で呼ばれる
    if ( n が 1 と等しい )
        return 1
    endif
    return n + sum(n-1)

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) が自分自身を参照しており無限ループになります。

発展問題（FE試験スタイル）

ここからは応用問題です。 使う知識はこれまでに学んだもの（再帰、if文、引数、戻り値）だけ。 これは基本情報技術者試験（FE）の科目B でよく出る形です。

発展問題11-A

次の関数を g(4) として呼び出したとき、戻り値はどれか。

○整数型: g(整数型: n)
    if ( n が 0 以下 )
        return 0
    endif
    return n + g(n - 1)
解説を表示 正解：ウ
g(4) = 4 + g(3) = 4 + 3 + g(2) = 4 + 3 + 2 + g(1) = 4 + 3 + 2 + 1 + g(0) = 4+3+2+1+0 = 10
つまりこの関数は「1 から n までの合計」を返す再帰関数です。
ポイント：n を 1 ずつ減らしながら足し算していくパターン。再帰の典型例。

発展問題11-B

次の関数を h(5) として呼び出したとき、出力されるものはどれか。

○ h(整数型: n)
    if ( n が 0 と等しい )
        return
    endif
    n を出力
    h(n - 1)
    n を出力
解説を表示 正解：ウ
「n を出力 → 再帰呼び出し → n を出力」の構造。
行きがけ（再帰呼び出しの前）に 5, 4, 3, 2, 1 と出力し、
帰りがけ（再帰呼び出しの後）に 1, 2, 3, 4, 5 と出力する。
結果：5 4 3 2 1 1 2 3 4 5
ポイント：呼び出しと「戻ってきた後」の処理で、同じ変数が異なるタイミングで使われる。 再帰のスタック（積み上げと巻き戻し）を意識すると見えやすい。