読み方のヒント

矢印ボタン(または ← → キー)でページを移動できます。

第4節 再帰

4.3 呼び出しの回数

フィボナッチ数を求める再帰です。

○整数型: fib(整数型: n)
  if (n ≦ 1)
    return n
  else
    return fib(n - 1) + fib(n - 2)
  endif

fib(5) は5を返しますが、関数は合わせて15回呼び出されます。同じ値(fib(2) など)を何度も計算しているためです。

呼び出し回数
fib(5)1
fib(4)1
fib(3)2
fib(2)3
fib(1)5
fib(0)3
解答

戻り値は120(5×4×3×2×1)、呼び出しの回数は5回(階乗(5)、(4)、(3)、(2)、(1))です。

19 / 30