平成29年度 秋期 応用情報技術者試験 午前 問7

• ア: if n=0 then return 0 else return n×fact(n−1)
  誤り。0! は 1 なので、n=0 で 0 を返すのは誤りです。また、この定義では掛け算の最後に必ず 0 が掛かるため、全ての n に対して 0 を返してしまいます。

• イ: if n=0 then return 0 else return n×fact(n+1)
  誤り。n=0 で 0 を返す点が誤りです。さらに fact(n+1) を呼び出すため n が増え続け、再帰が終了しません。

• ウ: if n=0 then return 1 else return n×fact(n−1)
  正しい。0! = 1 を終了条件とし、n! = n × (n−1)! という関係で再帰的に定義しています。例えば fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 6 となり、正しく階乗を返します。

• エ: if n=0 then return 1 else return n×fact(n+1)
  誤り。fact(n+1) を呼び出すため n が増え続け、n=0 の終了条件に到達せず再帰が終了しません。

答え

ウ: if n=0 then return 1 else return n×fact(n−1)