応用情報技術者試験
2012年度 ＝ 平成24年度・秋期
午前
問7
次の関数
g
(
x
)の定義に従って
g
(4)を再帰的に求めるとき、必要な加算の回数は幾らか。
g
(
x
) = if
x
< 2
then 1
else
g
(
x
-1) +
g
(
x
-2)
ア 3
イ 4
ウ 5
エ 7
解答
イ
解説
ボトムアップ解析を行ってみましょう。
g
(2)
=
g
(1) +
g
(0)
… 1回
g
(3)
=
g
(2) +
g
(1)
= (1回) +
g
(1)
… 2回
g
(4)
=
g
(3) +
g
(2)
= (2回) + (1回)
… 4回
