階乗の再帰的定義
出典: 平成29年度 秋期 応用情報技術者試験 午前 問7 (IPA)
fact (n) は，非負の整数 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)
正解と解説を見る
正解: ウ
- ア: n = 0 のとき 0 を返すと、全ての結果が 0 になってしまいます。0! は 1 です。
- イ: n = 0 のとき 0 を返すうえ、fact(n ＋ 1) では n が大きくなっていき、終わりません。
- ウ: n = 0 のとき 1 を返し、それ以外は n × fact(n − 1) を返すので正しい定義です。
- エ: fact(n ＋ 1) では n がどんどん大きくなり、n = 0 にたどり着かないので終わりません。
ポイント
- 階乗は n! = n × (n − 1) × … × 1 で、0! = 1 と決められています。
- 再帰的に書くと「n = 0 なら 1、それ以外は n × fact(n − 1)」です。n − 1 と小さくしていくことで、いずれ n = 0 にたどり着いて終わります。