応用情報技術者 2017年 秋期 午前2 問07
問題文
fact(n)は、非負の整数nに対しての階乗を返す。fact(n)の再帰的な定義はどれか。
選択肢
ア：if n=0 then return 0 else return n×fact(n-1)
イ：if n=0 then return 0 else return n×fact(n+1)
ウ：if n=0 then return 1 else return n×fact(n-1)（正解）
エ：if n=0 then return 1 else return n×fact(n+1)
階乗の再帰的定義【午前2 解説】
要点まとめ
- 結論：階乗の再帰的定義は「n=0のとき1を返し、それ以外はn×fact(n-1)」である。
- 根拠：階乗は0! = 1が基本で、n! = n × (n-1)!の関係が成り立つため。
- 差がつくポイント：ベースケースの値設定と引数の減少方向を正しく理解しているかが重要。
正解の理由
選択肢ウは、階乗の定義通り「n=0なら1を返し、それ以外はn×fact(n-1)」となっており、正しい再帰関数の形です。0!が1であることと、再帰呼び出しが引数を1ずつ減らしていく点が正確に表現されています。
よくある誤解
0!を0と誤認したり、再帰呼び出しの引数を増やす方向にしてしまうと無限ループや誤った結果になります。
解法ステップ
- 階乗の定義を確認する（0! = 1、n! = n × (n-1)!）。
- ベースケース（n=0）で返す値を決める。
- 再帰呼び出しの引数が減少することを確認する。
- 選択肢の条件と返り値を比較し、正しいものを選ぶ。
選択肢別の誤答解説
- ア: n=0のとき0を返すため誤り。0!は1。
- イ: n=0のとき0を返し、fact(n+1)で引数が増加し無限再帰になる。
- ウ: 正解。0! = 1で、引数を減らす正しい再帰定義。
- エ: n=0のとき1を返すが、fact(n+1)で引数が増加し無限再帰になる。
補足コラム
階乗は数学的に0! = 1と定義されており、再帰関数では必ずベースケースを設けて無限再帰を防ぎます。引数を減らすことで最終的にベースケースに到達し、計算が終了します。
FAQ
Q: なぜ0!は1なのですか？
A: 0! = 1は数学的な約束事で、組み合わせの定義や階乗の連続性から導かれています。
A: 0! = 1は数学的な約束事で、組み合わせの定義や階乗の連続性から導かれています。
Q: 再帰関数で引数を増やすと何が問題ですか？
A: ベースケースに到達できず無限ループやスタックオーバーフローが発生します。
A: ベースケースに到達できず無限ループやスタックオーバーフローが発生します。
関連キーワード: 階乗、再帰関数、ベースケース、無限再帰、数学的定義
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！