基本情報技術者 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