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

階乗を求める再帰関数の乗算回数【午前2 解説】

要点まとめ

• 結論→与えられた再帰定義では基底ケース F(0)=1 を除き n>0 の各再帰呼び出しで1回乗算が発生し、合計は n です。
• 根拠→乗算回数を M(n) と置くと M(0)=0、M(n)=M(n-1)+1 となり、漸化式を展開すると明確に M(n)=n となります。
• 差がつくポイント→反復的に 1×2×...×n と計算すると n-1 になることがあり、再帰で n=1 のときに 1 を掛ける操作を見落とさないこと。

正解の理由

よくある誤解

• 「階乗の乗算は n-1 回」と誤解する人が多い：反復的に 1×2×...×n を順に掛ければ n-1 回ですが、本問の再帰定義では n=1 のときにも 1 を掛ける操作があるため回数が1増えます。
• 「関数呼び出し回数と乗算回数を混同」：再帰呼び出し回数は n+1（n から 0 まで）だが、乗算は n>0 の呼び出しでのみ発生する点を区別する必要があります。
• 「基底ケースの扱い忘れ」：F(0)=1 の扱いを誤ると M(0) を 1 と数えてしまい誤答につながります。

解法ステップ

1. 乗算回数を M(n) と定義する。
2. ベースケースを考える：F(0)=1 のとき乗算は行われないので M(0)=0。
3. 再帰式から漸化式を立てる：n>0 のときの処理は「1回の乗算 + F(n-1) の乗算数」なので $M(n)=M(n-1)+1$。
4. 漸化式を展開または帰納的に解く：$M(1)=M(0)+1=1$, $M(2)=M(1)+1=2$, したがって一般に $M(n)=n$。
5. よって乗算回数を表す式は $n$ であり、選択肢は イ。

選択肢別の誤答解説

• ア: $n-1$
  反復的に 1×2×...×n と計算する場合は確かに n-1 回ですが、問題の再帰定義では n=1 のときにも「1 × F(0)」という乗算を行うため回数が1多くなります。従って本問には当てはまりません。
• イ: $n$
  正解。理由は上記の通り。F(0) では乗算が発生せず、n>0 の各レベルで1回ずつ乗算が発生するため合計 n 回です。
• ウ: $n^2$
  オーダーが大きすぎます。漸化式 $M(n)=M(n-1)+1$ に従う単純な線形増加であり二次になる理由はありません。
• エ: $n!$
  乗算の回数が階乗の値そのものになることはありません。n! は演算結果の数値であり、乗算回数を表すには不適切です。

補足コラム

• 再帰での「操作回数」と「関数呼び出し回数」は別物です。今回の例では関数呼び出しは n+1 回（n, n-1, ..., 0）ですが、乗算は n>0 の呼び出しのみで発生するため n 回になります。
• もし問題の関数を F(1)=1、F(n)=n×F(n-1)（n>1）という形に変えると、乗算回数は n-1 回になります。定義の微妙な違いが回数に直接影響します。
• 実装によっては「1 を掛ける操作は意味がない」として最適化することもありますが、問題文の定義に従って数えるのが試験対策では重要です。

FAQ