Fibonacci de 0 et 1 : les cas de base
fib(0) et fib(1) ne demandent qu'un seul appel : ce sont les cas de base de la récursion.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Valeur de F(1)
- 1
- Appels de la version récursive naïve
- 1
- Appels avec mémorisation
- 1
- Additions de la version itérative
- 0
- Durée de la version naïve
- 20 ns
Le cas en détail
Toute fonction récursive a besoin de cas de base pour s'arrêter. Pour Fibonacci, ce sont les rangs 0 et 1, qui retournent directement leur valeur. Sans eux, la fonction s'appellerait indéfiniment.
À retenir : Quand vous écrivez une fonction récursive, écrivez d'abord les cas de base, puis l'appel récursif.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Rang n (0 à 200) : 1
- Appels de fonction par seconde : 50000000
- Valeur de F(1)
- 1
- Appels de la version récursive naïve
- 1
- Appels avec mémorisation
- 1
- Additions de la version itérative
- 0
- Durée de la version naïve
- 20 ns
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
Avec fib(0) = 0 et fib(1) = 1, le nombre d'appels C(n) vérifie C(n) = 1 + C(n-1) + C(n-2), ce qui donne C(n) = 2 F(n+1) - 1. Avec mémorisation, chaque valeur n'est calculée qu'une fois : 2n - 1 appels. La version itérative fait n - 1 additions.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.