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

再帰関数の和計算【午前解説】

正解の理由

解法ステップ

1. 定義を確認： f(n) = 1 （n ≤ 1）、それ以外はf(n) = n + f(n-1)。
2. f(1) = 1（基底）。
3. f(2) = 2 + f(1) = 2 + 1 = 3。
4. f(3) = 3 + f(2) = 3 + 3 = 6。
5. f(4) = 4 + f(3) = 4 + 6 = 10。
6. f(5) = 5 + f(4) = 5 + 10 = 15。
7. 必要なら一般式 $f(n)={\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$（$n\ge 1$）を使って確認する。

選択肢別の誤答解説

• ア: 6 — f(5)=5+1=6のように、中間の再帰展開（4,3,2を足す）を飛ばしてしまった場合に出る誤答。
• イ: 9 — f(5)=5+4=9と一回だけ再帰を展開して終えてしまうミス。再帰はさらに続けてf(3), f(2), f(1) を評価する必要があります。
• ウ: 正解（15） — 5+4+3+2+1の和で正しい値です。
• エ: 25 — 掛け算（5×5）や二乗の誤解、あるいは問題文を読み違えて別の操作を適用した結果に相当します。

よくある誤解

• 基底条件をn≤0と誤解してしまい、f(1) を再帰でさらに展開してしまう（結果がずれる）。
• 再帰の展開を途中で打ち切ってf(5)=5+f(0) のようにしてしまい、5+1＝6を誤答とする。
• 再帰ではなく掛け算や別の操作（例えば5×5＝25）だと誤解して25を選んでしまう。

補足コラム

• 一般式と証明：$n\ge 1$ に対して $$f(n)=\sum _{k=1}^{n}k=\frac{n(n+1)}{2}.$$ 帰納法で示せます。初期n=1で成立し、仮定f(n)=n(n+1)/2とすると $f(n+1)=n+1+f(n)=n+1+\frac{n(n+1)}{2}=\frac{(n+1)(n+2)}{2}$ となり成立します。
• 実装例（Python）：

def f(n):
    if n <= 1:
        return 1
    return n + f(n-1)

print(f(5))  # 15

• 注意点：自然数の定義によって0を含む場合でも、本関数はn=0のとき1を返すので一般式はn≥1に限定して扱うと安全です。

FAQ