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

問題文

自然数

n

に対して、次のように再帰的に定義される関数

f (n)

を考える。

f (5)

の値はどれか。

f (n)

: if

n \leq 1

then return 1 else return

n + f (n - 1)

🖊️ 解答を隠して解いてみる

選択肢

ア：6

イ：9

ウ：15（正解）

エ：25

🔒 解説は解答すると表示されます

再帰による階差和【午前解説】

正解の理由

定義に従い f(n) を展開すると、f(5) は 1 から 5 までの整数の和そのものになります。閉形式で書けば

f (n) = k = 1 \sum n k = \frac{n ( n + 1 )}{2}

なので

f (5) = \frac{5 \times 6}{2} = 15

です。したがって正解はウ（15）です。

解法ステップ

定義を確認： if $n \leq 1$ then return 1, else return $n + f (n - 1)$ .
基底値を適用： $f (1) = 1$ （定義より）。
漸次計算：
- $f (2) = 2 + f (1) = 2 + 1 = 3$
- $f (3) = 3 + f (2) = 3 + 3 = 6$
- $f (4) = 4 + f (3) = 4 + 6 = 10$
- $f (5) = 5 + f (4) = 5 + 10 = 15$
あるいは総和公式を使って $f (5) = \frac{5 \times 6}{2} = 15$ と即座に求める。

選択肢別の誤答解説

ア: 6 — これは $f (3)$ の値に相当します。5 まで計算するべきところを 3 で止めてしまった誤りです。
イ: 9 — 部分和の計算ミス（例えば 5+4=9 のような誤った途中計算）や、1 を基底として正しく加算できなかった結果です。
ウ: 15 — 正解。1 から 5 までの和、または公式 $n (n + 1) /2$ から得られます。
エ: 25 — $5^{2}$ を当てはめたミス。和ではなく二乗を誤って使う典型的なミスです。

よくある誤解

「基底が n≤1 のとき 1 を返す」を見落として f(1)=0 として計算する誤り。これで全体が1足りなくなります。
5 の二乗（25）や別の二項計算を誤って当てはめ、合計ではなく $n^{2}$ を答えるミス。
再帰展開を途中で止めてしまい、例えば f(3) までしか足さないなど範囲の勘違いをすること。

補足コラム

この問題は「三角数（triangular number）」の基礎問題です。一般に再帰 f(n)=n+f(n-1)、かつ f(1)=1 のとき

f (n) = 1 + 2 + \dots + n

となり、

T_{n} = \frac{n ( n + 1 )}{2}

と表現されます。プログラム的には再帰でも反復でも実装できますが、再帰深さやオーバーヘッドを考えると反復（ループ）で計算するほうが効率的です。

例：Python での実装

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

def f_iterative(n):
    s = 0
    for i in range(1, n+1):
        s += i
    return s

print(f_recursive(5))  # 15
print(f_iterative(5))  # 15

FAQ

Q1: f(0) はどうなるか？
A1: 定義では「n ≤ 1 のとき 1 を返す」とあるので、数学的に 0 を含めるなら f(0)=1 です。ただし問題は自然数 n を対象としているので通常は n≥1 を想定します。

Q2: 総和の公式はどう導けるか？
A2: ガウス和の方法などで示せます。

S = \sum_{k = 1}^{n} k

として前後を足すと

2 S = n (n + 1)

となり、

S = \frac{n ( n + 1 )}{2}

を得ます。帰納法でも証明可能です。

Q3: 再帰と反復、どちらで解くべきか？
A3: 思考での計算や試験回答ではどちらでも構いませんが、実装では反復がスタックを使わず安定して高速です。時間計算量はどちらも O(n) です。

関連キーワード: 再帰関数、等差数列、三角数、帰納法、アルゴリズム、再帰展開、総和公式

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！