Récursion terminale

En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération. Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c'est-à-dire qu'elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition. Par exemple, dans un langage de programmation fictif : fonction récursionTerminale(n) : // ... renvoie récursionTerminale(n - 1) fonction récursionNonTerminale(n) : // ... renvoie n + récursionNonTerminale(n - 1) récursionNonTerminale() n'est pas une récursion terminale car sa dernière instruction est une composition faisant intervenir l'appel récursif. Dans le premier cas, aucune référence aux résultats précédents n'est à conserver en mémoire, tandis que dans le second cas, tous les résultats intermédiaires doivent l'être. Les algorithmes récursifs exprimés à l'aide de fonctions à récursion terminale profitent donc d'une optimisation de la pile d'exécution. Lors de la compilation (si elle existe), la récursion terminale peut être transformée en itération, c'est-à-dire en une série d'étapes séquentielles totalement dénuée de toute nature récursive. La récursion terminale est utilisée principalement dans les langages de programmation fonctionnels pour exprimer un processus itératif dans une forme fonctionnelle récursive (en général très condensée et « élégante »). Les langages de programmation fonctionnels peuvent généralement détecter la récursion terminale et optimiser son exécution en transformant la récursion en itération, économisant ainsi l'espace de la pile d'exécution, comme le montre l'exemple ci-dessous. Prenons ce programme Scheme comme exemple : (define (factorielle n) (define (iterer n acc) (if (