Facteurs de branchement
Lorsque l’on travaille avec des fonctions récursives, il peut être pertinent d’appeler la fonction courante plusieurs fois avec des arguments différents. Par exemple, si nous souhaitons calculer le n-ième nombre de Fibonacci à l’aide d’une fonction récursive, cela pourrait ressembler à ceci :
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Ici, pour chaque argument
n, nous effectuons 2 appels récursifs à la fonction fib avec les arguments n-1 et n-2.Challenge - Fibonacci récursif
Calculez le nombre de fois que la fonction récursive Fibonacci est appelée.
Entrée
L’entrée consiste en un seul entier
n (0 ≤ n ≤ 20).Sortie
Le programme doit afficher le nombre de fois que la fonction
fib a été appelée.Exemples
Input | Output |
0 | 1 |
1 | 1 |
2 | 3 |
5 | 15 |
6 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB