基本情報技術者 2016年 春期 午前（科目A） 問07

階乗の再帰関数【午前解説】

正解の理由

解法ステップ

1. 問題の対象が「階乗」であることを確認する。数学的定義は $n!$。
2. 階乗の再帰定義 $n!=n\times (n-1)!$ を思い出す。
3. それを関数 $F$ に置き換え、$n>0$ のとき $F(n)=n\times F(n-1)$ とする。
4. 基底ケース $n=0$ に対して $F(0)=1$ が与えられていることを確認して終了。

選択肢別の誤答解説

• ア: $n+F(n-1)$
  誤り。階乗は乗算の反復であり、加算では正しい値になりません（例：$3!=6$ だが $3+F(2)=3+2$ は 5）。
• イ: $n-1+F(n)$
  誤り。右辺に $F(n)$ が残るため、再帰で引数が減らず無限ループ（無限再帰）になります。
• ウ: $n\times F(n-1)$
  正解。数学的定義 $n!=n\times (n-1)!$ に一致し、基底 $F(0)=1$ と合わせて正しく停止します。
• エ: $(n-1)\times F(n)$
  誤り。引数 $n$ が変わらないため無限再帰になるほか、演算も階乗定義に合致しません。

よくある誤解

• 1. 加算と乗算を混同する：階乗は掛け算の繰り返しなので $n+F(n-1)$（ア）は誤りです。
• 1. 引数が変わらない再帰：$F(n)$ を右辺にそのまま残す（イ, エ）は無限再帰を招きます。
• 1. 基底ケースを忘れると停止しない：必ず $F(0)=1$ のような停止条件を確認する必要があります。

補足コラム

• 実装例（Python）：

def F(n):
    if n == 0:
        return 1
    else:
        return n * F(n-1)

• 実践上の注意：再帰深度が大きいとスタックオーバーフロー（RecursionError）が起きるため、大きな $n$ はループで計算するか、言語の再帰深度設定を考慮してください。
• 最適化：尾再帰最適化がある言語では累積引数を使った実装（尾再帰形）で効率化できますが、Pythonは標準で尾再帰最適化を行いません。
• オーバーフロー：大きな階乗は桁数が急増するため、整数の扱いに注意（任意精度整数を持たない言語では溢れる）。

FAQ