基本情報技術者試験のサンプル問題を解こう！（11）（科目B）「整数の階乗を返す関数」

基本情報技術者試験のサンプル問題（科目B）を解いてみよう。

今回のテーマは、「整数の階乗を返す関数」である。

関数 factorial は非負の整数 n を引数にとり，その階乗を返す関数である。非負の整数nの階乗はnが0のときに1になり，それ以外の場合は1からnまでの整数を全て掛け合わせた数となる。

解答群
ア 　(n － 1) × factorial(n)
イ　 factorial(n － 1)
ウ 　n
エ 　n × (n － 1)
オ　 n × factorial(1)
カ　 n × factorial(n － 1)

「非負整数 n の階乗」を求める再帰関数 factorial(n) の定義についての問題である。
再帰とは、処理中に自分自身を呼び出すことができる性質のことを指す。

階乗の定義は次の通りである。

• 0! = 1
• n! = n × (n − 1)! （n ≧ 1）

プログラムの流れ

1. n = 0 の場合、return 1 で終了（ベースケース）。
2. それ以外の場合、n! を得るためには「n × (n−1)!」を返す必要がある。

正解：カ　 n × factorial(n － 1)　を確認しよう

例えば n = 4 のときは、
呼び出し（再帰の「行きがけ」）

factorial(4) = 4 × factorial(3)
factorial(3) = 3 × factorial(2)
factorial(2) = 2 × factorial(1)
factorial(1) = 1 × factorial(0)　
factorial(0) = 1   ← ここがベースケース

戻り（再帰の「帰りがけ」）

factorial(1) = 1 × 1 = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6
factorial(4) = 4 × 6 = 24

誤りとなる他の選択肢を確認しよう

ア 　(n−1) × factorial(n)
n = 4 を代入すると、
factorial(4)
→ return (4 – 1) × factorial(4)
→ return 3 × factorial(4)
ここで factorial(4) をもう一度呼び出すことになり、
factorial(4) = 3 × factorial(4)
= 3 × (3 × factorial(4))
…
factorial(n) を再帰で呼び出しても、factorial(4)なので、 無限ループ となり、 誤り。

イ　 factorial(n−1)
n = 4 を代入すると、
factorial(4)
→ return factorial(3)
→ return factorial(2)
→ return factorial(1)
→ return factorial(0)
→ return 1（ベースケース）

このように最終的に 1 を返す。
この選択肢では、単に再帰的に呼び出しているだけなので、
どんな n でも結果は常に 1 になり、 誤り。

ウ　 n
factorial(4) =n=4
常に引数のnを返すだけで、階乗にならず 誤り。

エ 　n × (n−1)
(n−1)！ではなく、2項の積なので、例えば、n = 4 を代入すると、 4×（4-1)=12。誤り。

オ　 n × factorial(1)
例えば、n = 4 を代入すると、
factorial(4) = 4 × factorial(1)
ここで factorial(1) の値が必要になる。
つまり、n にかかわらず factorial(1) を呼び出し続けるため、
式が終了せず、無限ループになる。よって誤り。