情報処理安全確保支援士試験 情報処理安全確保支援士試験 平成29年度秋期 午前Ⅰ 問3: 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)

解説

階乗の再帰定義は、基底(終了)条件と再帰呼出しの両方が正しく必要。0の階乗は1なのでn=0のときreturn 1、それ以外はn×fact(n-1)で1ずつ減らして基底へ収束させる。ウがこの形でn!=n×(n-1)!を正しく表す。プログラミングで再帰を書く際は、必ず停止する基底条件と、引数が確実に基底へ近づく再帰式を備えることが鉄則。

選択肢ごとの解説

• ア.基底でreturn 0だと階乗が常に0になり誤り。0!=1でなければならない。
• イ.基底が0かつfact(n+1)で引数が増え、停止せず誤り。0!=1にもならない。
• ウ.n=0で1を返し、n×fact(n-1)で確実に基底へ収束する正しい階乗の定義。
• エ.fact(n+1)では引数が増え続けて停止しないので誤り。再帰が収束しない。