分野別過去問題テクノロジ系　プログラミング No.13

プログラミング(全20問中13問目)

nの階乗を再帰的に計算する関数F(n)の定義において，aに入れるべき式はどれか。ここで，nは非負の整数である。

　n＞0のとき， F(n)＝a
　n＝0のとき， F(n)＝1

出典：平成20年秋期　問14

正解　ウ問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：プログラミング

解説

階乗とは、1からある自然数nまでの数をすべて掛け合わせた積のことをいいます。nの階乗は記号！を使って「n!」と表記します。仮に4!であれば「4×3×2×1＝24」というように計算します。

この問題ではこの4!を仮の値として、解答群の各式をaに代入することで正しいどうかかを検証していきます。

　F(4)＝4＋F(3)＝4＋3＋F(2)
＝4＋3＋2＋F(1)＝4＋3＋2＋1＋F(0)
＝4＋3＋2＋1＋1＝11 …×
　F(4)＝4－1＋F(4)＝4－1＋4－1＋F(4)
＝4－1＋4－1＋4－1＋F(4) …×
再帰呼び出しが永遠に続くため結果が計算できません
　F(4)＝4×F(3)＝4×3×F(2)
＝4×3×2×F(1)＝4×3×2×1×F(0)
＝4×3×2×1×1＝24 …○
　F(4)＝(4－1)×F(4)＝(4－1)×(4－1)×F(4)
＝(4－1)×(4－1)×(4－1)×F(4)　…×
「イ」と同様に再帰関数の引数が変化していかないので、計算が永遠と続いてしまいます。

以上より、aに入れるべき式として適切なのは「n×F(n－1)」だとわかります。