平成24年度秋期 応用情報技術者試験 午前 問7
次の関数g(x)の定義に従ってg(4)を再帰的に求めるとき，必要な加算の回数は幾らか。g(x)＝if x<2 then 1 else g(x−1)＋g(x−2)
- ア 3
- イ 4
- ウ 5
- エ 7
解答・解説を見る
正解：イ
AI解説
g(x)はx<2のとき1、それ以外はg(x−1)+g(x−2)と定義される。g(4)=g(3)+g(2)で加算1回、g(3)=g(2)+g(1)で1回、g(2)=g(1)+g(0)で1回だがg(2)は2回呼ばれるため加算も2回発生する。合計1+1+2=4回でイが正しい。 ア: 3はg(2)の計算結果を使い回す(メモ化する)場合の加算回数であり、単純な再帰では重複計算が発生する。 イ: 正解。g(4)で1回、g(3)で1回、2回のg(2)呼出しで各1回、計4回の加算が必要である。 ウ: 5は呼出し回数や加算回数の数え間違いによる値である。 エ: 7は関数呼出しの総回数(g(4),g(3),g(2)×2,g(1)×2,g(0)×2など)と混同した値に近い。 💡 再帰の計算量問題は呼出しツリーを描き、加算が起こるのは「else側の節(ノード)」だけと数えるのが確実。同じ引数の呼出しが複数回現れる点がフィボナッチ型再帰の特徴である。
出典：平成24年度 秋期 応用情報技術者試験 午前 問7 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。