再帰呼出しの回数
次の再帰関数 f について、f(5) を呼び出したとき、f が呼び出される回数は何回か。ここで、最初の f(5) の呼出しも1回と数える。
関数 f(n)
n ≦ 1 ならば 1 を返す
それ以外ならば f(n-1) + f(n-2) を返す
- A
8回
- B
9回
- C
15回
- D
31回
正解と解説を見る
正解:C
呼出し回数は「自分の1回+子の呼出し回数の合計」という漸化式で求める。小さいnから順に計算すると C(5)=15 になる。
- A
誤り。f(5)の戻り値(1, 1, 2, 3, 5, 8)であり、呼出し回数ではない。
- B
誤り。f(4)を呼び出した場合の回数C(4)である。
- C
正しい。呼出し回数をC(n)とすると、C(0)=C(1)=1、C(n)=1+C(n-1)+C(n-2)。C(2)=3、C(3)=5、C(4)=9、C(5)=15となる。
- D
誤り。呼出しの木を深さ5の完全2分木とみなして2^5-1で計算している。実際はn≦1で呼出しが止まる枝があり、完全2分木にならない。
このサイトの問題は、公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。独立行政法人情報処理推進機構(IPA)の公式サービスではありません。