À retenir
- L'appel récursif doit être la dernière instruction exécutée.
- Permet d'économiser énormément de mémoire vive (RAM).
- Évite l'erreur classique du Stack Overflow (dépassement de pile).
- Est traitée par certains compilateurs comme une simple boucle (itération).
La récursion terminale est une manière particulière d'écrire une fonction qui s'appelle elle-même, où cet appel est la toute dernière action effectuée par la fonction. Contrairement à une récursion classique, l'ordinateur n'a pas besoin de garder en mémoire l'état de l'étape précédente, car il n'y a plus aucun calcul à faire après l'appel. C'est un peu comme une course de relais où le coureur transmet le témoin et quitte immédiatement la piste, au lieu de devoir attendre que le coureur suivant revienne pour terminer sa propre course.
Étymologie
Le terme vient du latin recurrere (revenir en arrière) et de l'adjectif terminale, car l'appel se situe à l'extrémité finale du bloc de code. En anglais, on parle de tail recursion (récursion de queue).
Exemples d'usage
- Une fonction qui calcule la somme des nombres d'une liste en passant le résultat partiel (un accumulateur) à l'appel suivant.
- Un compte à rebours où la fonction s'appelle avec
n-1sans rien faire d'autre après.
Cas d'usage
Ce concept est massivement utilisé dans les langages de programmation fonctionnelle (comme Haskell, Elixir ou Lisp) qui préfèrent la récursion aux boucles traditionnelles. Il intervient dès qu'une performance optimale est requise pour des processus répétitifs profonds.
Bonnes pratiques
Pour transformer une récursion classique en récursion terminale, la technique habituelle consiste à utiliser un accumulateur : un paramètre supplémentaire qui transporte le résultat au fur et à mesure des appels, évitant ainsi de laisser des calculs en attente.
Synonymes
Antonymes
Conseil
Si vous travaillez sur des algorithmes traitant de très grandes quantités de données, vérifiez si votre langage de prédilection supporte l'optimisation d'appel terminal (TCO). Si c'est le cas, privilégiez cette structure pour rendre votre code aussi rapide qu'une boucle for ou while.
Questions fréquentes
Pourquoi est-ce plus performant ?
Parce que le système remplace l'emplacement mémoire de la fonction actuelle par la suivante au lieu d'empiler de nouvelles couches de mémoire.
Est-ce que tous les langages le gèrent ?
Non, certains langages comme Python ne l'optimisent pas automatiquement, tandis que d'autres comme Scheme ou Elixir en dépendent pour fonctionner.