Calculez le nombre d’appels de fonction

Considérons un exemple classique de récursivité : la suite de Fibonacci, définie sur les entiers naturels à partir de 0, où chaque élément \(F(n)\) est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13, 21, .... On vous donne une fonction qui renvoie un tuple contenant le \(n\)-ième élément de la suite et le nombre d’appels à fib() effectués :

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)

Combien d’appels à fib() sont nécessaires pour calculer les \(15^{th}\) et \(20^{th}\) éléments de la suite ?