階乗の再帰的定義
出典: 令和7年度 春期 応用情報技術者試験 午前 問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 = 0 のとき 1 を返し、それ以外は n × fact(n−1) を返すので、階乗の定義どおりです。正しい答えです。
- エ: fact(n＋1) で呼ぶと、n が 0 に近づかず、再帰が止まりません。
ポイント
- n の階乗は n! = n × (n−1)! で、0! = 1 です。
- 再帰的定義では、終了条件 (n = 0 のとき 1 を返す) と、より小さい値での呼出し (fact(n−1)) が必要です。
- n + 1 で呼ぶと終了条件に近づかず、止まりません。