修了試験 2017-12-10実施分 基本情報技術者試験 問8

解説

正解は3です。 nの階乗n!は、1からnまでの整数をすべて掛け合わせた値です。 n!＝n×(n－1)!という関係があるので、F(n)はn×F(n－1)と、1つ小さい問題の結果を使って定義できます。 n＝0のときのF(0)＝1が再帰の終了条件です。 【選択肢別解説】 1：× n＋F(n－1)は足し算なので、階乗ではなく0からnまでの和を求める式になります。 2：× n－1＋F(n)は、右辺に同じF(n)が現れるため、再帰呼出しが終わらず値が定まりません。 3：○ n×F(n－1)は、n!＝n×(n－1)!という階乗の性質そのものです。 nが1ずつ減ってF(0)＝1で止まるので、正しく計算できます。 4：× (n－1)×F(n)は、右辺に同じF(n)が現れるため、再帰呼出しが終わりません。 【計算】 F(3)＝3×F(2)です。 F(2)＝2×F(1)、F(1)＝1×F(0)、F(0)＝1です。 戻りながら計算すると、F(1)＝1、F(2)＝2、F(3)＝6となり、3!＝6と一致します。 【ポイント】 再帰的な定義では、引数が終了条件に近づく形（ここではn－1）になっているかを必ず確認します。 同じ引数で自分を呼ぶ式は、終了しない再帰になります。