平成24年度 秋期 基本情報技術者試験 午前 問7
テクノロジ／アルゴリズムn!の値を，次の関数F(n)によって計算する。乗算の回数を表す式はどれか。 F(n)＝1（n＝0のとき） F(n)＝n×F(n－1)（n＞0のとき）
出典：平成24年度 秋期 基本情報技術者試験 午前 問7
- アn－1
- イn
- ウn²
- エn！
正解：イ
解説
F(n)はn＝0のとき1を返し，n＞0のときはn×F(n－1)を計算します。この再帰呼出しはn，n－1，…，1と1回ずつ乗算を行いながらn＝0に達するまで続くため，乗算はF(n)からF(1)までのn回分（n×F(n－1)，(n－1)×F(n－2)，…，1×F(0)）実行されます。乗算の回数はnです。
選択肢ごとの解説
- ア誤り。最後のF(1)×F(0)の呼出しで乗算しない場合を想定した数ですが，実際にはn回の乗算が行われます。
- イ正しい。F(n)からF(1)まで，それぞれの呼出しでn×F(n－1)の形の乗算が1回ずつ行われるため，合計n回です。
- ウ誤り。乗算回数がnの2乗になるのは，二重ループなど別の処理の場合であり，この再帰処理には当てはまりません。
- エ誤り。n！はF(n)の計算結果であり，乗算の回数ではありません。