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

自然数の再帰関数 f(n) の値を求める【午前2 解説】

要点まとめ

• 結論：再帰定義に従うと f(5)=5+4+3+2+1=15、したがって選択肢の正解はウです。計算は再帰を逆展開して行います。
• 根拠：定義は f(n)=1 (n≤1)、それ以外は f(n)=n+f(n-1) であり、n≥1 に対して $f(n)={\sum }_{k=1}^{n}k$ と表せます。
• 差がつくポイント：基底条件(n≤1)の扱いを誤らないこと、再帰を展開して項を明示すること、公式 $n(n+1)/2$ の適用範囲を確認すること。

正解の理由

よくある誤解

• 基底条件を「n=0 のとき 0 を返す」と誤解してしまう。問題文では n≤1 のとき 1 を返す点に注意。
• 再帰展開を途中で止めて合計項を漏らす（例えば 5+4 までで止めるなど）。必ず最後の基底まで展開する。
• 和の公式を使う際に適用範囲を確認せず n=0 を含めるなどして誤用すること。

解法ステップ

1. 定義を確認：f(n)=1（n≤1）、それ以外は f(n)=n+f(n−1）。
2. n=5 に対して再帰を逆展開する：f(5)=5+f(4), f(4)=4+f(3), …, f(1)=1。
3. 各項を足す：5+4+3+2+1=15。
4. 必要なら公式を適用：$f(5)=\frac{5\times 6}{2}=15$。

選択肢別の誤答解説

• ア: 6 — これは 1+2+3 の合計に相当し、n=3 の場合の値。再帰を途中で止めた可能性。
• イ: 9 — たとえば 5+4 を答えとして終了させた誤り、または項を取り違えた計算ミス。
• ウ: 15 — 正解。再帰を正しく展開すると得られる合計値。
• エ: 25 — 5 の二乗を取る誤解（$n^2$ と誤認）や、誤った公式適用によるもの。問題定義からは導けない。

補足コラム

• 一般公式の導出（簡単な帰納法）： 基底：$n=1$ のとき ${\sum }_{k=1}^{1}k=1$ は成り立つ。
  帰納：$f(n)={\sum }_{k=1}^{n}k$ と仮定すると $f(n+1)=(n+1)+f(n)={\sum }_{k=1}^{n+1}k$。したがって全ての $n\ge 1$ で $f(n)=\frac{n(n+1)}{2}$。
• 実行例（Python）

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

print(f(5))  # 15

• 注意：問題では基底が「n≤1 のとき 1」であるため、$f(0)=1$ となり、$n=0$ の場合は公式 $\frac{n(n+1)}{2}$ と一致しません。公式は $n\ge 1$ を前提とする点に留意してください。

FAQ