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

要点まとめ

• 結論→ f(5)=15。再帰定義を一段ずつ展開すると 5+4+3+2+1 の和になり三角数に等しいため、選択肢は ウ が正答です。
• 根拠→ 基底条件 n≤1 のとき f(n)=1 であり、それ以外は f(n)=n+f(n-1) を繰り返すため 1 から n までの和に還元されます。
• 差がつくポイント→ 「基底条件の境界（n≤1 と n≤0 の違い）」や「再帰展開を途中で止めるミス」を避け、全ての項を足し切ることが重要です。

正解の理由

よくある誤解

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

解法ステップ

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\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