階乗を求める再帰関数の「乗算回数」を数える
今回は、基本情報技術者試験でよく出る 再帰関数 の問題です。
ポイントは、階乗の値そのものを求めるのではなく、
この関数を実行したとき、掛け算が何回行われるか を数えることです。
問題
n! の値を、次の関数 F(n) によって計算する。
乗算の回数を表す式はどれか。
F(n) =
1 （n = 0）
n × F(n - 1) （n > 0）選択肢
ア n - 1
イ n
ウ n^2
エ n!まず、n! とは何か
n! は 階乗 と読みます。
1からnまでの整数を、すべて掛け合わせたものです。
例えば、
4! = 4 × 3 × 2 × 1 = 24です。
今回の関数 F(n) は、この階乗を再帰で求めています。
この関数がしていること
関数 F(n) は、次の2つのルールで動きます。
n = 0 のとき
→ 1 を返す
n > 0 のとき
→ n × F(n - 1) を計算するつまり、n が0になるまで、1ずつ小さくしながら自分自身を呼び出します。
これを 再帰 といいます。
具体例として F(4) で考える
いきなり n で考えると分かりにくいので、まず F(4) で考えます。
F(4)
= 4 × F(3)ここで、掛け算が1回あります。
次に、F(3) を計算します。
F(3)
= 3 × F(2)ここでも、掛け算が1回あります。
さらに、
F(2)
= 2 × F(1)ここでも、掛け算が1回あります。
さらに、
F(1)
= 1 × F(0)ここでも、掛け算が1回あります。
最後に、
F(0)
= 1ここでは、掛け算はありません。
F(4) の乗算回数を数える
整理すると、次のようになります。
F(4) = 4 × F(3) 乗算1回
F(3) = 3 × F(2) 乗算1回
F(2) = 2 × F(1) 乗算1回
F(1) = 1 × F(0) 乗算1回
F(0) = 1 乗算0回したがって、F(4) の乗算回数は、
1 + 1 + 1 + 1 = 4回です。
つまり、F(4) では 4回 掛け算をしています。
一般の n ではどうなるか
F(n) の場合も同じです。
F(n) = n × F(n - 1)
F(n - 1) = (n - 1) × F(n - 2)
F(n - 2) = (n - 2) × F(n - 3)
...
F(1) = 1 × F(0)
F(0) = 1掛け算が行われるのは、次の部分です。
F(n)
F(n - 1)
F(n - 2)
...
F(1)つまり、
n, n - 1, n - 2, ... , 1の n個分 です。
一方、F(0) では掛け算をしません。
乗算回数は n 回
したがって、乗算回数は、
n回です。
よって、正解は、
イ nです。
初心者が間違えやすいポイント
この問題で間違えやすいのは、次の考え方です。
4! = 4 × 3 × 2 × 1 だから、掛け算は3回では？たしかに、数学的に式をまとめて計算するなら、
4 × 3 × 2 × 1は、見方によっては掛け算を3回と数えることがあります。
しかし、この問題は 数学の式を効率よく計算する話 ではありません。
問われているのは、
この関数 F(n) が、実行中に何回「×」を行うかです。
関数の定義では、n > 0 のたびに、
n × F(n - 1)という掛け算を1回行います。
そのため、F(1) の
1 × F(0)も、関数上は乗算1回として数えます。
まとめ
問題3-8は、階乗そのものを求める問題ではなく、
再帰関数の中で掛け算が何回実行されるか を数える問題です。
F(n) = n × F(n - 1) 1回
F(n - 1) = (n - 1) × F(n - 2) 1回
...
F(1) = 1 × F(0) 1回
F(0) = 1 0回F(n) から F(1) まで、掛け算は1回ずつ行われます。
その数は、
n個なので、乗算回数は
n回です。
正解は、
イ nです。