平成29年度 秋期 応用情報技術者試験 午前 問7
テクノロジ／アルゴリズムfact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。
出典：平成29年度 秋期 応用情報技術者試験 午前 問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)
正解：ウ
解説
階乗の再帰的定義は，基底部でfact(0)＝1とし，それ以外はn×fact(n－1)で定義します。基底値を1とせずに0とすると，全ての結果が0になってしまい正しい階乗が求まりません。
選択肢ごとの解説
- ア誤り。基底部をreturn 0とすると，fact(1)＝1×fact(0)＝1×0＝0となり，本来1であるべき1の階乗が0になってしまい誤りです。
- イ誤り。基底部が0であることに加え，fact(n＋1)のように引数を増やす方向に再帰すると計算が終了せず無限再帰になります。
- ウ正しい。基底部をfact(0)＝1とし，それ以外をn×fact(n－1)とする定義は，階乗の性質n！＝n×(n－1)！と一致する正しい再帰的定義です。
- エ誤り。基底部は正しく1ですが，fact(n＋1)のように引数を増やす方向に再帰すると計算が終了せず無限再帰になります。