Beräkna antalet funktionsanrop

Låt oss titta på ett klassiskt exempel på rekursion – Fibonacci-sekvensen, som består av icke-negativa heltal med start från 0, där varje element \(F(n)\) är summan av de två föregående: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Du har en funktion som returnerar en tupel med det \(n\)-te elementet i sekvensen och antalet anrop till fib() som använts:

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)

Hur många anrop till fib() krävs för att beräkna det \(15^{e}\) och det \(20^{e}\) elementet i sekvensen?