基本情報技術者試験対策！再帰アルゴリズムを「階乗」から理解する
基本情報技術者試験では、再帰（recursive）に関する問題が出題されます。
例えば、次のような問題です。
nの階乗を再帰的に計算する関数F(n)の定義で、aに入る式はどれか。
このような問題を見ると、
「再帰って何？」
「F(n-1)って何をしているの？」
と混乱する受講生が多いです。
しかし、ポイントは1つです。
再帰とは、自分自身を呼び出しながら、少しずつ終了条件へ近づいていく仕組み
です。
まず「階乗」を理解する
階乗とは、
「1からその数までを全部掛ける計算」
です。
例えば、3!
は、
3 × 2 × 1なので、
6になります。
また、5!
なら、
5 × 4 × 3 × 2 × 1です。
階乗を小さく分解してみる
ここで考え方を変えます。
3!
を、
3 × 2 × 1ではなく、
3 × 2!と考えます。
なぜなら、
2! = 2 × 1だからです。
さらに、
2! = 2 × 1!です。
つまり、
3!
↓
3 × 2!
↓
3 × 2 × 1!
↓
3 × 2 × 1 × 0!と分解できます。
ここで再帰が登場する
問題文では、
n = 0 のとき
F(n)=1と決めています。
つまり、
F(0)=1です。
これを利用すると、
F(3)は、
次のようになります。
F(3)
↓
3 × F(2)
↓
3 × 2 × F(1)
↓
3 × 2 × 1 × F(0)
↓
3 × 2 × 1 × 1
↓
6になります。
つまり、aに入る式は？
流れを見ると、
F(3)
↓
3 × F(2)です。
一般化すると、
F(n)
↓
n × F(n-1)になります。
したがって、
です。
答えは、
ウ
になります。
他の選択肢を確認する
ア
これは足し算になっています。
例えば、
F(3)
↓
3+F(2)
↓
3+2+F(1)
↓
3+2+1+F(0)となります。
計算すると、
3+2+1+1=7です。
しかし、
3!=6なので違います。
イ
を見ると、
F(3)
↓
2+F(3)となります。
あれ？
またF(3)が出ています。
つまり、
F(3)
↓
F(3)
↓
F(3)
↓
・・・となり、永遠に終わりません。
エ
も同じです。
例えば、
F(3)
↓
2×F(3)となります。
また自分自身を呼んでいます。
これも終了しません。
再帰プログラムで重要な2つのポイント
① 終了条件があるか？
再帰では必ず、
「ここまで来たら終了」
という条件が必要です。
今回なら、
F(0)=1です。
これがなければ、
F(3)
↓
F(2)
↓
F(1)
↓
F(0)で止まれません。
② 少しずつ終了条件へ近づいているか？
正しい再帰：
F(n)
↓
F(n-1)
↓
F(n-2)
↓
・・・
↓
F(0)数字が小さくなっています。
つまり、
終了へ近づいています。
一方、
間違った再帰：
F(n)
↓
F(n)
↓
F(n)
↓
・・・これは永久ループになります。
プログラムで見るとどうなる？
例えばC#では、階乗は次のように書けます。
static int Factorial(int n)
{
if (n == 0)
{
return 1;
}
return n * Factorial(n - 1);
}実行すると、
Factorial(3)
↓
3 * Factorial(2)
↓
3 * 2 * Factorial(1)
↓
3 * 2 * 1 * Factorial(0)
↓
3 * 2 * 1 * 1
↓
6という流れになります。
まとめ
再帰問題では、式を暗記するより、
次の流れを理解することが重要です。
現在の値
↓
少し小さい値へ
↓
終了条件へ近づく階乗の場合は、n!
なので、
「現在の数字 × 1つ小さい階乗」
になります。
つまり、
です。
基本情報技術者試験では、
「自分自身を呼び出しているが、必ず終了条件に近づいているか」
を見ることが、再帰問題を解くポイントになります。
