fact (n )は、非負の整数n に対してn の階乗を返す。
fact (n )の再帰的な定義はどれか。
ア | if n =0 then 0 else return n *fact (n -1) |
イ | if n =0 then 0 else return n *fact (n +1) |
ウ | if n =0 then 1 else return n *fact (n -1) |
エ | if n =0 then 1 else return n *fact (n +1) |
答え ウ
【解説】
n の階乗は“1×2×3×…×(n -1)×n ”であるため、これを書き換えると、“n !=n ×(n -1)!”「n ×(n -1)の階乗」である。
同様に、(n -1)の階乗は、(n -1)×(n -2)!である。
これをずっと繰り返すと、2の階乗は2×1!になり、1の階乗は1×0!になるが、0!(0の階乗)を“0”とすると、すべての数の階乗が“0”になってしまうので、0の階乗を“1”と定義する。
これを選択肢のように表すと
if n =0 then 1 else return n *fact (n -1)
(ウ)になる。
【キーワード】
・階乗
・再帰