平成25年度春期 応用情報技術者試験 午前 問6
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)
解答・解説を見る
正解：ウ
AI解説
階乗は 0!＝1（基底条件）、n!＝n×(n−1)!（n≧1）と再帰的に定義される。再帰定義には「終わりの条件（基底）」と「問題を小さくする再帰呼出し」の両方が正しく必要で、n＝0のとき1を返し、それ以外はn×fact(n−1)を返すウが正しい。 ア: 基底値が0だと、どのnでも掛け算の連鎖の最後に0が掛かり、結果が常に0になってしまう。 イ: 基底値が0である上に、fact(n＋1)ではnが増え続けて基底条件に到達せず、無限再帰になる。 ウ: 正しい。0!＝1を基底とし、fact(n−1)でnを減らしながら基底に到達する正しい再帰定義である。 エ: 基底値1は正しいが、fact(n＋1)ではnが増え続けて停止しない。 💡 再帰定義の検証は「基底値は正しいか（0!＝1）」「再帰呼出しで引数が基底に近づくか（n−1）」の2点チェックで機械的に行える。0!＝1は数学上の定義として必ず覚える。
出典：平成25年度 春期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。