次の関数g (x )の定義に従ってg (4)を再帰的に求めるとき、必要な加算の回数は幾らか。
g (x ) = if x < 2 then 1
else g (x - 1) + g (x - 2)
ア | 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 |
【キーワード】
・再帰的処理