基本情報 2022 サンプル問題 問8：テクノロジ系に関する問題

答えは c「15」 です。

この問題は 「関数が自分自身を呼ぶ(再帰)」 という仕組み。やってることは「n + (n-1) + (n-2) + ... + 1」みたいに、足し算をどんどん遡る、ロシアのマトリョーシカ人形のような動き。

f(5) を計算してみると:

• f(5) = 5 + f(4)
• f(4) = 4 + f(3)
• f(3) = 3 + f(2)
• f(2) = 2 + f(1)
• f(1) = 1(これ以上は呼ばない=底)

下から組み立てると: f(1)=1 → f(2)=3 → f(3)=6 → f(4)=10 → f(5)=15。

👉 覚え方: 「1から5まで全部足す = 1+2+3+4+5 = 15」。

ほかの選択肢: a「6」は f(3) だけ・b「9」は計算ミス・d「25」は 5×5 や別の式の答え。

なぜこれが正解か

正解は c「15」。再帰関数 f(n) は n ≤ 1 で1を返し、それ以外は n + f(n−1) を返す。これは 1 + 2 + 3 + … + n の総和を計算する関数(ガウスの和の公式 n(n+1)/2 に一致)。

f(5) を底から積み上げ:

```

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

```

または n(n+1)/2 = 5×6/2 = 15 で検算可能。

各選択肢の解説

• a「6」: f(3) の値。途中で止まった誤り。
• b「9」: 該当する経路なし。計算ミス。
• d「25」: 5² = 25 と勘違い、もしくは f(n) = n + f(n) のような無限再帰を誤想定。

覚え方・ひっかけ注意

再帰トレースは 「底(base case)から組み上げる」 のが正攻法。トップダウンで f(5) を展開すると混乱しやすい。

ベースケースの境界に注意: 本問は `n ≤ 1 then return 1`。「n=0でも n=1でも1を返す」点を見落とすと、f(1) で再帰を継続して無限ループ誤読するミスが起きる。基本情報試験では境界条件のひっかけが頻出。

再帰の理論

再帰関数は数学的帰納法の計算機による具現化。ベースケース(基底) と 再帰ケース(帰納部) の2要素で定義される。本問では:

• 基底: f(1) = 1
• 帰納: f(n) = n + f(n−1)

停止性(termination)は再帰引数が単調減少し有限ステップで基底に到達することで保証される。

計算量とスタック

本関数の時間計算量 O(n)、空間計算量 O(n)(再帰呼び出しごとにスタックフレームを消費)。閉形式 n(n+1)/2 を用いれば O(1) 時間・空間で済む。再帰深度が大きいと スタックオーバーフロー が発生(Java 既定 512KB で約数万深度、Python は sys.setrecursionlimit() で制限あり)。

末尾再帰最適化(TCO)

本関数は厳密には末尾再帰ではない: `return n + f(n−1)` で f の戻り値に加算する処理が後続するため。末尾再帰形に変換するにはアキュムレータを追加:

```

f_tail(n, acc): if n ≤ 1 then return acc + 1 else return f_tail(n-1, acc + n)

```

この形にすればコンパイラが末尾呼び出し最適化を適用し、ループに展開してスタック消費 O(1) に削減可能。Scheme・Scala・Erlang は標準で TCO 対応、JavaScript ES6 仕様にもあるが実装は限定的、Java/Python は非対応。

再帰 vs 反復

反復版:

```

sum = 0; for i in 1..n: sum += i

```

性能では反復が優位だが、分割統治法(マージソート、クイックソート、二分探索木)や バックトラック(N-クイーン、迷路探索)、動的計画法(メモ化再帰)では再帰の方が自然に書ける。

試験での位置づけ

アルゴリズムの必出単元。基本情報技術者試験では本問のような単純再帰のトレース、フィボナッチ数列、ハノイの塔、二分探索、二分木の巡回が頻出。応用情報以降では計算量解析(マスター定理による T(n) = aT(n/b) + f(n) の漸近評価)、相互再帰、継続(continuation)まで踏み込む。

選択肢の発展補足

• 三角数(triangular number): n(n+1)/2 で表される数列(1, 3, 6, 10, 15, 21, ...)。本問は三角数の第5項を求めている。Σ k=1..n の総和公式はガウスが幼少期に発見した逸話で有名。
• メモ化(memoization): 関数値をキャッシュして再計算を回避する技法。本問のような線形再帰では効果が薄いが、フィボナッチでは O(2^n) → O(n) に劇的改善。
• 相互再帰: 関数 f と g が互いを呼び合う形。例: 偶数判定 even(n) と奇数判定 odd(n)。コンパイラの相互再帰型解析、parser combinator で頻出。
• 構造的再帰: リストや木のような再帰的データ構造に対する再帰関数(map, fold, reduce)。関数型言語の中核概念。