平成24年度 秋期 応用情報技術者試験 午前 問7
次の関数g(x)の定義に従ってg(4)を再帰的に求めるとき，必要な加算の回数は幾らか。
g(x) = if x < 2 then 1
else g(x−1) + g(x−2)
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
x < 2 のときは加算なしで1を返し，x ≧ 2 のときは g(x−1) + g(x−2) を計算するので1回の加算が発生します。各値を求めるのに必要な加算回数をA(x)とすると，
- A(0) = A(1) = 0
- A(2) = A(1) + A(0) + 1 = 1
- A(3) = A(2) + A(1) + 1 = 2
- A(4) = A(3) + A(2) + 1 = 2 + 1 + 1 = 4
したがって，g(4)を求めるのに必要な加算は4回です。
答え
イ: 4
出典：平成24年度 秋期 応用情報技術者試験 午前 問7
