Oblicz liczbę wywołań funkcji

Rozważmy klasyczny przykład rekurencji – ciąg Fibonacciego, reprezentowany przez nieujemne liczby całkowite zaczynające się od 0, gdzie każdy element \(F(n)\) jest sumą dwóch poprzednich: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Dana jest funkcja, która zwraca krotkę zawierającą \(n\)-ty element ciągu oraz liczbę wywołań 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)

Ile wywołań fib() jest potrzebnych do obliczenia \(15.\) i \(20.\) elementu ciągu?