うごく基本情報

サンプル問題セット(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 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型: factorial(整数型: n)n = 6
22行目if (n = 0)偽
31行目○整数型: factorial(整数型: n)n = 5
42行目if (n = 0)偽
51行目○整数型: factorial(整数型: n)n = 4
62行目if (n = 0)偽
71行目○整数型: factorial(整数型: n)n = 3
82行目if (n = 0)偽
91行目○整数型: factorial(整数型: n)n = 2
102行目if (n = 0)偽
111行目○整数型: factorial(整数型: n)n = 1
122行目if (n = 0)偽
131行目○整数型: factorial(整数型: n)n = 0
142行目if (n = 0)真
153行目return 1
165行目return n × factorial(n - 1)n = 1
175行目return n × factorial(n - 1)n = 2
185行目return n × factorial(n - 1)n = 3
195行目return n × factorial(n - 1)n = 4
205行目return n × factorial(n - 1)n = 5
215行目return n × factorial(n - 1)n = 6

戻り値:720

サイトで、1行ずつ予想しながら動かす →