Calcola il numero di chiamate di funzione

Consideriamo un classico esempio di ricorsione: la successione di Fibonacci, rappresentata da interi non negativi a partire da 0, in cui ogni elemento \(F(n)\) è la somma dei due precedenti: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Ti viene data una funzione che restituisce una tupla con l’\(n\)-esimo elemento della successione e il numero di chiamate a fib() utilizzate:

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)

Quante chiamate a fib() servono per calcolare il \(15^{th}\) e il \(20^{th}\) elemento della successione?