テクノロジ系
秋期
応用情報技術者 2012年 秋期 問7
7 / 80
次の関数 g(x) の定義に従って g(4) を再帰的に求めるとき，必要な加算の回数は幾らか。 g(x) ＝ if x＜2 then 1 else g(x-1) ＋ g(x-2)
正解と解説
表示する
正解 イ
4
g(4)=g(3)+g(2)、g(3)=g(2)+g(1)、g(2)=g(1)+g(0)と展開されます。加算が発生するのはx≥2の呼出し、すなわちg(4)・g(3)・2回現れるg(2)で、合計4回の加算が必要です。