階乗の再帰定義はなぜ n × F(n−1) になるのか
基本情報技術者試験では、再帰関数の考え方が問われることがあります。
今回の問題3-14は、再帰の中でも代表的な例である階乗を題材にした問題です。
「階乗」と聞くと難しく感じるかもしれませんが、ポイントは次の1つです。
nの階乗は、nに「1つ小さい階乗」を掛けたもの
つまり、
n! = n × (n - 1)!です。
この形が分かると、答えが自然に見えてきます。
問題
nの階乗を再帰的に計算する関数 F(n) の定義において、aに入れるべき式はどれか。
ここで、nは非負の整数とする。
n > 0 のとき、F(n) = a
n = 0 のとき、F(n) = 1選択肢は次の通りです。
ア n + F(n - 1)
イ n - 1 + F(n)
ウ n × F(n - 1)
エ (n - 1) × F(n)正解は、
ウ n × F(n - 1)です。
階乗とは何か
階乗とは、ある整数から1までを順に掛けていく計算です。
例えば、5の階乗は次のようになります。
5! = 5 × 4 × 3 × 2 × 1つまり、
5! = 120です。
4の階乗なら、
4! = 4 × 3 × 2 × 1なので、
4! = 24です。
5! は 5 × 4! と考えられる
ここで重要なのは、5! を次のように分解できることです。
5! = 5 × 4 × 3 × 2 × 1このうち、
4 × 3 × 2 × 1の部分は、4! です。
つまり、
5! = 5 × 4!と書けます。
同じように、
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 × 0!と考えることができます。
これを一般化すると、
n! = n × (n - 1)!になります。
F(n) は n! を表している
この問題では、階乗を計算する関数を F(n) としています。
つまり、
F(5) は 5!
F(4) は 4!
F(3) は 3!を表します。
先ほどの考え方を F(n) で書くと、
F(n) = n × F(n - 1)になります。
したがって、aに入る式は、
n × F(n - 1)です。
よって正解は、
ウです。
実際に F(4) で確認する
F(4) を考えてみましょう。
問題の定義に従うと、
F(4) = 4 × F(3)です。
次に F(3) は、
F(3) = 3 × F(2)です。
さらに、
F(2) = 2 × F(1)
F(1) = 1 × F(0)となります。
ここで問題文には、
n = 0 のとき、F(n) = 1とあります。
つまり、
F(0) = 1です。
これを戻していくと、
F(1) = 1 × 1 = 1
F(2) = 2 × 1 = 2
F(3) = 3 × 2 = 6
F(4) = 4 × 6 = 24となります。
つまり、
F(4) = 4 × 3 × 2 × 1 = 24となり、正しく4の階乗が計算できています。
なぜ F(0) = 1 なのか
初学者が疑問に感じやすいのが、
0! = 1という部分です。
「0個を掛けるのになぜ1なのか」と感じるかもしれません。
ここでは、まず試験対策としては、
0! は 1 と定義されていると覚えておけば大丈夫です。
再帰関数では、このような計算を止めるための条件が必要です。
もし F(0) = 1 がなければ、
F(4)
→ F(3)
→ F(2)
→ F(1)
→ F(0)
→ F(-1)
→ F(-2)のように、いつまでも関数を呼び続けてしまいます。
そのため、
n = 0 になったら 1 を返して終わるというルールが必要です。
これを終了条件といいます。
再帰は「1回分だけ考える」
再帰関数を理解するときは、すべてを一気に追いかけようとすると混乱します。
大事なのは、
今の n で何をするかだけを見ることです。
階乗の場合、F(n) がやることは次の1つです。
n に、1つ小さい階乗 F(n - 1) を掛けるつまり、
F(n) = n × F(n - 1)です。
F(n – 1) の中身まで一気に考えすぎると、再帰は難しく見えます。
まずは、
F(n - 1) は、ひとまず「1つ小さい階乗を計算してくれるもの」と考えるのがコツです。
選択肢を確認する
ア n + F(n – 1)
これは掛け算ではなく足し算です。
階乗は、
5 × 4 × 3 × 2 × 1のように掛け算で計算します。
そのため、
n + F(n - 1)では階乗になりません。
よってアは誤りです。
イ n – 1 + F(n)
これは F(n) の中で、また F(n) を使っています。
つまり、
F(n) = n - 1 + F(n)のような形になります。
これでは同じ F(n) を呼び続けてしまい、計算が前に進みません。
再帰では、通常、
F(n - 1)のように、少し小さい問題にしていく必要があります。
よってイは誤りです。
ウ n × F(n – 1)
これは、
n! = n × (n - 1)!という階乗の考え方そのものです。
F(n – 1) は、1つ小さい階乗を表します。
そのため、
F(n) = n × F(n - 1)で正しく階乗を表せます。
よってウが正解です。
エ (n – 1) × F(n)
これは F(n) の中で、また F(n) を使っています。
F(n) = (n - 1) × F(n)となるため、これも計算が前に進みません。
また、本来は n を掛ける必要があります。
n × F(n - 1)でなければなりません。
よってエは誤りです。
この問題のポイント
この問題で見るべきポイントは、次の3つです。
1. 階乗は掛け算である
2. n! は n × (n - 1)! と分解できる
3. 再帰では、F(n) ではなく F(n - 1) のように小さい問題へ進めるしたがって、
F(n) = n × F(n - 1)となります。
まとめ
問題3-14は、階乗の再帰定義を問う問題です。
階乗は、
5! = 5 × 4 × 3 × 2 × 1のように、1まで順に掛けていく計算です。
そして、
5! = 5 × 4!と考えることができます。
これを一般化すると、
n! = n × (n - 1)!です。
問題では階乗を F(n) と表しているので、
F(n) = n × F(n - 1)となります。
よって、正解は、
ウ n × F(n - 1)です。
再帰の問題では、まず
1回分の処理は何か
どこで止まるのか
小さい問題に進んでいるかを見ると、選択肢を判断しやすくなります。
