Hitung jumlah pemanggilan fungsi

Mari kita tinjau contoh klasik rekursi – deret Fibonacci, direpresentasikan oleh bilangan bulat tak negatif mulai dari 0, dengan setiap elemen \(F(n)\) sama dengan jumlah dua elemen sebelumnya: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Anda diberikan sebuah fungsi yang mengembalikan sebuah tuple berisi elemen ke-\(n\) dari deret tersebut dan jumlah pemanggilan ke fib() yang digunakan:

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)

Berapa banyak pemanggilan ke fib() yang dibutuhkan untuk menghitung elemen ke-\(15\) dan ke-\(20\) dari deret tersebut?