L'itération utilise des boucles ; la récursion utilise des auto-appels. Elles sont également puissantes (tout ce que tu peux faire avec l'une, tu peux le faire avec l'autre), mais elles diffèrent en clarté et en coût.
():
total =
i (, n + ):
total += i
total
():
n == :
n + sum_rec(n - )
| Aspect | Itération | Récursion |
|---|---|---|
| Mémoire | O(1) supplémentaire | O(profondeur) pile |
| Lisibilité | excellente pour le travail linéaire | excellente pour les arbres / diviser-et-conquérir |
| Risque | boucle infinie | débordement de pile |
| Vitesse | généralement plus rapide (pas de surcharge d'appel) | surcharge d'appel par frame |
La récursion profonde risque le débordement de pile ; convertis le code récursif critique en itération (souvent avec une pile explicite) quand la profondeur est non bornée.
Choisir le bon style garde le code à la fois correct et lisible.
La récursion rend le code d'arbre et de graphe élégant, mais connaître son coût en mémoire te permet d'éviter les plantages sur les entrées profondas.
Ce jugement de compromis est exactement ce que les recruteurs sondent quand ils te demandent de « convertir ceci en itératif ».