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

再帰的な和の計算【午前解説】

正解の理由

解法ステップ

1. 定義を確認：if n ≤ 1 then return 1 else return n + f(n-1)。
2. 再帰を展開する： f(5) = 5 + f(4)
   f(4) = 4 + f(3)
   f(3) = 3 + f(2)
   f(2) = 2 + f(1)
   f(1) = 1（ここで打ち切り）
3. 足し合わせる：f(5) = 5+4+3+2+1 = 15
4. 必要なら公式を用いる：$f(n)={\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$ に代入して $f(5)=5\cdot 6/2=15$。

選択肢別の誤答解説

• ア: 6
  6は「n+1」や「部分和を途中で止めた」などの誤った理解から出やすい値です。例えばf(5)=5+1のように誤ってf(4) を1として打ち切ると出ますが定義に反します。
• イ: 9
  9は「1+2+3+3のように重複や打ち間違いで項を誤る」か、「f(2)=3をそのまま繰り返す」などの計算ミスで現れます。正しい展開では1 〜 5の和になります。
• ウ: 15
  正しい再帰展開と和の計算の結果です。
• エ: 25
  25は5^2の値で、二乗と誤解した結果や「(n+0)^2」的な誤りから出ます。問題の定義は乗算や二乗ではなく加算の再帰です。

よくある誤解

1. 基底（base case）を誤解してn=0が必ず0になると考える。与題ではn ≤ 1のとき1を返すためf(0)=1です。基底を変えるときはどのnに影響するかを確認する必要があります。
2. 再帰を掛け算（階乗）や別の操作と混同する。n + f(n-1) をn × f(n-1) と見間違えるとまったく別の成長（階乗）になります。
3. 展開途中で打ち切る、又は項の順序や個数を見誤る（例えばf(5) を5+4+1としてしまうなど）。

補足コラム

• 数学的帰納法による公式の証明（スケッチ）:
  命題P(n): f(n)=n(n+1)/2。n=1のとき左辺f(1)=1、右辺は1·2/2=1で成り立つ。あるk≥1でP(k) が成り立つと仮定すると、 f(k+1)= (k+1) + f(k) = (k+1) + k(k+1)/2 = (k+1)(k/2+1) = (k+1)(k+2)/2、 よってP(k+1) も成り立ち、帰納法によりn≥1で公式が成立します。
• 基底をf(0)=0に変更した場合の影響:
  基底を0にして $f(0)=0$ としても、n≥1に対する値は変わりません（n≥1のときは依然として1からnまでの和になるため）。変わるのはn=0の値のみで、公式は0からnまでの和としてn≥0まで拡張して扱うことができます（${\sum }_{k=0}^{n}k=\frac{n(n+1)}{2}$）。
• 実装例（Python）:

# 再帰実装
def f(n):
    if n <= 1:
        return 1
    return n + f(n-1)

# 反復実装（効率的）
def f_iter(n):
    s = 0
    for k in range(1, n+1):
        s += k
    return s

FAQ