応用情報技術者 2012年 秋期 午前2 問07

再帰呼び出しの加算回数【午前2解説】

正解の理由

解法ステップ

1. ベース条件を確認：ベースは $x<2$ → $x=0,1$ がベース（加算を行わない）。$x\ge 2$ が非ベース（加算を行う）。
2. 再帰展開を行う：
   • $g(4)=g(3)+g(2)$ → ここで加算1回（g(4)）
   • $g(3)=g(2)+g(1)$ → ここで加算1回（g(3)）
   • $g(2)=g(1)+g(0)$ → ここで加算1回（g(2)）
   • 同様に $g(2)$ は2箇所から呼ばれるため、もう1回の加算が発生（別の g(2)）
3. 非ベース呼び出しの個数を数えると $4$ になり、これが加算回数。

選択肢別の誤答解説

• ア: 3
  多くは $g(2)$ をベース（加算が発生しない）と誤認して $g(4),g(3),g(2)$ を1回ずつしか数えないため。だが $g(2)$ は非ベースであり2回呼ばれるので誤り。
• イ: 正しい（加算4回）。上記の通り非ベース呼び出しが4回あるため。
• ウ: 5
  1つ余分に数えてしまうケース。例えばベース呼び出し（g(1)やg(0)）を加算回数に含めたり、同じ g(2) のカウント方法を誤って合算した結果などが原因。
• エ: 7
  再帰木の全ノード数や完全二分木とみなして過剰に数えた誤り。実際には多くの葉がベースであり、加算は非ベース呼び出しのみで発生する。

よくある誤解

• 「g(2)はベース」だと勘違いする：ベース条件は $x<2$ なので $x=2$ は非ベースで必ず加算を行う点に注意。
• 同じ引数の関数呼び出しを1回しか数えてしまう：再帰的に同じ $g(2)$ が複数回呼ばれる場合、それぞれで加算が発生する（メモ化しない場合）。
• 関数呼び出し回数と加算回数を混同する：呼び出し回数にはベース呼び出しが含まれるが、加算は非ベース呼び出しごとに1回だけ発生する。

補足コラム

# 単純再帰で加算回数をカウント
count = 0
def g(n):
    global count
    if n < 2:
        return 1
    count += 1  # g(n) が非ベースなので加算が行われる
    return g(n-1) + g(n-2)

count = 0
g(4)
print(count)  # 結果は 4

FAQ