応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問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を返す(終了条件)』と『それ以外は n×fact(n−1) を返す(自分自身を引数を1減らして呼ぶ)』の2点が必要である。終了条件で1を返し，かつ引数を減らして再帰するウが正しい。0を返すと結果全体が0になり，引数を n+1 と増やすと終了せず無限再帰になる。

選択肢ごとの解説

• ア.誤り。終了時に0を返すため，最後に0が掛けられて結果全体が0になってしまい階乗にならない。
• イ.誤り。終了時に0を返す点に加え，fact(n+1)と引数が増えていくので n=0 に到達せず無限再帰になる。
• ウ.正しい。0!=1 を終了条件とし，n×fact(n−1) で引数を1ずつ減らして再帰するので，正しく n の階乗を計算できる。
• エ.誤り。終了条件で1を返す点は正しいが，fact(n+1)と引数が増え続け n=0 に到達しないため無限再帰になる。