À retenir
- L'appel récursif doit être la dernière instruction de la fonction.
- Elle évite l'erreur classique de « dépassement de pile » (stack overflow).
- Elle permet à l'ordinateur de réutiliser la même zone mémoire pour chaque appel.
C'est une technique de programmation où une fonction s'appelle elle-même, mais de manière très spécifique : cet appel est la toute dernière action effectuée par la fonction. Imaginez un coureur de relais qui, au moment où il passe le témoin, s'arrête définitivement au lieu de devoir attendre que le coureur suivant revienne vers lui.
Étymologie
Vient du latin recurrere (« courir en arrière ») et de l'adjectif « finale » car l'appel récursif se situe en position de sortie. En anglais, on parle de tail recursion (récursion de queue).
Exemples d'usage
- Calcul d'une factorielle où le résultat intermédiaire est passé en paramètre (accumulateur) à l'étape suivante.
- Recherche d'un élément dans une liste où l'on passe à l'élément suivant sans rien faire au retour de l'appel.
Cas d'usage
Elle est fondamentale dans les langages de programmation fonctionnelle (comme Haskell, Elixir ou Lisp) qui n'utilisent pas de boucles classiques for ou while. On s'en sert pour traiter de grandes quantités de données sans saturer la mémoire vive de l'ordinateur.
Bonnes pratiques
Pour transformer une récursion classique en récursion finale, on utilise souvent un accumulateur, c'est-à-dire une variable passée en argument qui transporte le résultat au fur et à mesure. Il faut aussi s'assurer que le langage utilisé supporte l'optimisation d'appel terminal (TCO) pour que cela soit réellement efficace.
Synonymes
Antonymes
Conseil
Si vous débutez, entraînez-vous à passer le résultat de vos calculs dans les paramètres de votre fonction récursive plutôt que de faire l'opération au moment du return. C'est le secret pour passer d'une récursion classique à une récursion finale.
Questions fréquentes
Est-ce que tous les langages l'utilisent ?
Non, certains langages comme Python ne l'optimisent pas nativement, tandis que d'autres comme les langages fonctionnels ou certains moteurs JavaScript le font.
Est-ce plus rapide qu'une boucle ?
Généralement non, c'est équivalent en termes de performance brute, mais c'est une approche plus élégante et nécessaire dans certains paradigmes de programmation.