함수 호출 횟수 계산하기

재귀의 고전적인 예인 피보나치 수열을 살펴보겠습니다. 0부터 시작하는 음이 아닌 정수로 구성되며, 각 원소 $F(n)$은 바로 앞의 두 원소의 합입니다: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... 아래 함수는 수열의 $n$번째 원소와 그 값을 구하는 데 사용된 fib() 호출 횟수를 튜플로 반환합니다:

def fib(n):

  if n < 2:
    return (n, 1)

  fib1 = fib(n-1)
  fib2 = fib(n-2)

  return (fib1[0] + fib2[0], fib1[1] + fib2[1] + 1)

수열의 \(15^{th}\) 원소와 \(20^{th}\) 원소를 계산하는 데 fib() 호출이 각각 몇 번 필요할까요?