応用情報技術者試験 応用情報技術者試験 令和7年度春期 午前 問7: fact(n) は，非負の整数 n に対して n の階乗を返す。fact(n) の再帰的な定義はどれか。

問題本文

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)

正解

ウ. if n＝0 then return 1 else return n×fact(n－1)

解説

階乗 n! は n×(n－1)×…×1 で定義され、0!＝1 と決められています。再帰では「処理が止まる基底条件」と「自分自身を引数を減らして呼ぶ再帰部」の両方が必要です。正解ウは基底条件 n＝0 のとき 1 を返し（0!＝1）、それ以外は n×fact(n－1) で n に 1 つ小さい階乗を掛けます。これにより fact(3)＝3×fact(2)＝3×2×fact(1)＝…＝3×2×1×1 と正しく計算され、引数が必ず 0 に向かって減るため再帰も停止します。

選択肢ごとの解説

• ア.再帰部 n×fact(n－1) は正しいものの、基底条件で 0 を返しています。最後に fact(0)＝0 が掛けられて結果全体が 0 になってしまうため誤りです（0!＝1 でなければなりません）。
• イ.基底条件が 0 を返す点（結果が 0 になる）に加え、再帰部の引数が fact(n＋1) と増えていくため、n が永遠に 0 にならず無限再帰になります。二重に誤りです。
• ウ.基底条件 n＝0 で 1 を返し（0!＝1）、再帰部 n×fact(n－1) で引数を減らしながら階乗を計算します。停止条件と計算の両方が正しく、これが正解です。
• エ.基底条件で 1 を返す点は正しいですが、再帰部の引数が fact(n＋1) と増え続けるため n が 0 に到達せず無限再帰となり、停止しないので誤りです。