피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1) + fib(n−2)를 반환한다'로 재귀적으로 정의했다. fib(5)를 호출했을 때 fib가 호출되는 횟수는 첫 호출을 포함하여 몇 회인가?

정답: C. 15회

fib(n)의 호출 횟수를 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입니다. 같은 값을 몇 번이고 다시 계산하기 때문에 횟수는 n에 대해 지수적으로 늘어나며, fib(30)에서는 약 269만 회가 됩니다. 계산한 값을 표에 기억해 두는 메모이제이션(동적 계획법)을 사용하면 계산은 fib(0)~fib(5)의 6가지로 끝나고, 호출도 9회(2n − 1)로 줄어듭니다. 6회는 서로 다른 인수의 수, 9회는 메모이제이션을 한 경우의 호출 횟수입니다.