第１種情報処理技術者試験
1997年度 ＝ 平成9年度
午前
問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回
