次の関数 g(x)の定義に従って g(4) を再帰的に求めるとき、必要な加算の回数は幾らか。
g(x) = if x < 2 then 1
else g(x-1) + g(x-2)
ア 3 イ 4 ウ 5 エ 7
イ
g(4) = g(4-1) + g(4-2) = g(3) + g(2)
= g(3-1) + g(3-2) + g(2-1) + g(2-2) = g(2) + g(1) + g(1) + g(0)
= g(2-1) + g(2-2) + 1 + 1 +1 = g(1) + g(0) + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1
= 5
必要な加算回数は4回で、計算結果は5となる。
| 問６ | 目次 | 問８ |