サンプル問題セット(2022年12月公開) 科目B 問7
次のプログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。
関数 factorial は非負の整数 n を引数にとり,その階乗を返す関数である。非負の整数 n の階乗は n が 0 のときに 1 になり,それ以外の場合は 1 から n までの整数を全て掛け合わせた数となる。
○整数型: factorial(整数型: n)
if (n = 0)
return 1
endif
return [ a ]
| a | |
|---|---|
| ア | (n - 1) × factorial(n) |
| イ | factorial(n - 1) |
| ウ | n |
| エ | n × (n - 1) |
| オ | n × factorial(1) |
| カ | n × factorial(n - 1) |
出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問7
正解と解説を見る
正解:カ
ポイント:再帰の形:n! = n × (n-1)!。終わりの条件(0! = 1)と、1つ小さい自分自身の呼び出し。
階乗は n! = n × (n-1) × … × 1、0! = 1 です。n! = n × (n-1)! と書けるので、n が 0 でなければ n × factorial(n - 1) を返します(カ)。
確かめ:factorial(3) = 3 × factorial(2) = 3 × 2 × factorial(1) = 3 × 2 × 1 × factorial(0) = 6。
ア:factorial(n) をそのまま呼ぶので、n が小さくならず終わりません。
イ:n を掛けていないので、常に 1 を返します。
エ:n × (n-1) は、再帰になっておらず 2 つの積だけです(4! が 12 になる)。
トレースで呼び出しの深さが1つずつ増え、0 に着いてから掛け算しながら戻ってくる様子を見ると、再帰がよく分かります。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
factorial(6) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 21 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○整数型: factorial(整数型: n) | n = 6 |
| 2 | 2行目if (n = 0) | 偽 |
| 3 | 1行目○整数型: factorial(整数型: n) | n = 5 |
| 4 | 2行目if (n = 0) | 偽 |
| 5 | 1行目○整数型: factorial(整数型: n) | n = 4 |
| 6 | 2行目if (n = 0) | 偽 |
| 7 | 1行目○整数型: factorial(整数型: n) | n = 3 |
| 8 | 2行目if (n = 0) | 偽 |
| 9 | 1行目○整数型: factorial(整数型: n) | n = 2 |
| 10 | 2行目if (n = 0) | 偽 |
| 11 | 1行目○整数型: factorial(整数型: n) | n = 1 |
| 12 | 2行目if (n = 0) | 偽 |
| 13 | 1行目○整数型: factorial(整数型: n) | n = 0 |
| 14 | 2行目if (n = 0) | 真 |
| 15 | 3行目return 1 | |
| 16 | 5行目return n × factorial(n - 1) | n = 1 |
| 17 | 5行目return n × factorial(n - 1) | n = 2 |
| 18 | 5行目return n × factorial(n - 1) | n = 3 |
| 19 | 5行目return n × factorial(n - 1) | n = 4 |
| 20 | 5行目return n × factorial(n - 1) | n = 5 |
| 21 | 5行目return n × factorial(n - 1) | n = 6 |
戻り値:720