次の関数g(x)の定義に従ってg(4)を再帰的に求めるとき、必要な加算の回数は幾らか。
g(x) = if x < 2 then 1ア | 3 |
イ | 4 |
ウ | 5 |
エ | 7 |
答え イ
【解説】
関数g(x)の定義から必要な加算の回数を数える。
g(4) = g(3) + g(2) = (g(2) + g(1)) + (g(1) + g(0))
= ((g(1) + g(0)) + g(1)) + (g(1) + g(0))
= g(1) + g(0) + g(1) + g(1) + g(0)
= 5
で4回(イ)である。
参考に関数g(x)の加算回数を表にまとめる。
引数(x) | 加算回数 | 処理内容 |
---|---|---|
0 | 0 | g(0) = 1 |
1 | 0 | g(1) = 1 |
2 | 1 | g(2) = g(1) + g(0) = 2 |
3 | 2 | g(3) = g(2) + g(1) = (g(1) + g(0)) + g(1) = 3 |
4 | 4 | g(4) = g(3) + g(2) = (g(2) + g(1)) + (g(1) + g(0)) = ((g(1) + g(0)) + g(1)) + (g(1) + g(0)) = 5 |
5 | 7 | g(5) = g(4) + g(3) = 5 + 3 = 8 |
6 | 12 | g(6) = g(5) + g(4) = 8 + 5 = 13 |
7 | 20 | g(7) = g(6) + g(5) = 13 + 8 = 21 |
【キーワード】
・再帰的処理