令和7年度 春期 応用情報技術者試験 午前 問7
テクノロジ／アルゴリズムfact(n) は，非負の整数 n に対して n の階乗を返す。fact(n) の再帰的な定義はどれか。
出典：令和7年度 春期 応用情報技術者試験 午前 問7
- ア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)
正解：ウ
解説
階乗は 0!＝1，n!＝n×(n−1)!（n≧1）と定義されます。したがって再帰的な定義では，基底部で n＝0 のときに 1 を返し，再帰部で n×fact(n−1) と引数を1ずつ減らしていく必要があります。
選択肢ごとの解説
- ア誤り。n＝0 のときに 0 を返すため，掛け算の連鎖の最後に 0 が掛かり，どの n に対しても結果が 0 になってしまいます。
- イ誤り。n＝0 で 0 を返す上に fact(n＋1) と引数が増えていくので，正しい値が得られず再帰も終了しません。
- ウ正しい。0!＝1 という基底部と n!＝n×(n−1)! という再帰部を正しく表しています。
- エ誤り。基底部は正しいものの fact(n＋1) と引数が増え続けるため，n＝0 に到達せず再帰が終了しません。