関数 f を「n が0または1のとき1を返し、n が2以上のとき f(n−1) + f(n−2) を返す」と再帰的に定義する。f(5) を計算するとき、最初の呼出しも含めて f は何回呼び出されるか。

解説

正解は「15」です。f(n) の呼出し回数を C(n) とすると、f(n) 自身の1回に f(n−1) と f(n−2) の呼出し回数が加わるので、$C(n)=1+C(n-1)+C(n-2)$、$C(0)=C(1)=1$ です。順に計算すると C(2)=3、C(3)=5、C(4)=9、C(5)=15 となります。f(3) が2回、f(2) が3回計算されるなど、同じ計算が重複していることが分かります。「8」は f(5) の値そのもので、呼出し回数ではありません。「9」は f(4) を求めるときの呼出し回数です。「16」は呼出しのたびに回数がちょうど2倍になると考えた $2^4$ の値で、f(0) や f(1) では再帰しないことを考慮していません。