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

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

正解の理由

解法ステップ

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

補足コラム

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

FAQ