Tính số lần gọi hàm

Hãy xét một ví dụ kinh điển về đệ quy – dãy Fibonacci, gồm các số nguyên không âm bắt đầu từ 0, trong đó mỗi phần tử \(F(n)\) bằng tổng của hai phần tử liền trước: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Bạn được cho một hàm trả về một bộ giá trị (tuple) gồm phần tử thứ \(n\) của dãy và số lần gọi fib() đã dùng:

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)

Cần bao nhiêu lần gọi fib() để tính các phần tử thứ \(15^{th}\) và \(20^{th}\) của dãy?