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)!と定義され、再帰の終了条件は0!＝1である。したがってn=0のとき1を返し、それ以外はnとfact(n-1)の積を返す形が正しい。0で1ではなく0を返すと全体が0になり、引数を増やす形では再帰が終わらない。

選択肢ごとの解説

• ア0のときに0を返すため、結果が常に0になってしまう。
• イ0を返すうえに引数が増えるので終了しない。
• ウ正解。0!＝1を終了条件とし、n×fact(n-1)で階乗を求める。
• エ終了条件は正しいが引数が増えるので再帰が終わらない。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3