Overview
L'implémentation récursive de Fibonacci calcule fib(n) = fib(n-1) + fib(n-2), illustrant l'élégance de la récursion et ses pièges.
Analogy
Comme supposer que quelqu'un d'autre peut résoudre les petits problèmes, et combiner simplement ses réponses.
Step-by-step
- Cas de base : fib(0) = 0, fib(1) = 1
- Pour n > 1 : retourne fib(n-1) + fib(n-2)
- Chaque appel crée deux sous-appels
- Résultat : arbre d'appels exponentiel sans mémoïsation
Visual
fib(4)
├─ fib(3)
│ ├─ fib(2)
│ │ ├─ fib(1)=1
│ │ └─ fib(0)=0
│ └─ fib(1)=1
└─ fib(2)...
Common mistakes
- Utiliser sans mémoïsation (O(2^n))
- Oublier les deux cas de base (0 et 1)
Practice questions
- Ajoute @lru_cache et compare les temps
- Convertis en version itérative
Time
O(2^n) sans mémo, O(n) avec mémo