第1種情報処理技術者試験 1997年度 = 平成9年度 午前 問7

 次の関数g(x)の定義に従ってg(4)を再帰的に求めるとき、必要な加算の回数は幾らか。
   g(x) = if x < 2then 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回


BohYoh.comトップページへ