Récursivité terminale
Définition :
Une fonction récursive est dite terminale, si aucun traitement n'est effectué à la remontée d'un appel récursif (sauf le retour d'une valeur).
Une fonction récursive est dite non terminale, si le résultat de l'appel récursif est utilisé pour réaliser un traitement (en plus du retour d'une valeur).
Une fonction récursive terminale est en théorie plus efficace (mais souvent moins facile à écrire) que son équivalent non terminale : il n'y a qu'une phase de descente et pas de phase de remontée.
En récursivité terminale, les appels récursifs n'ont pas besoin d'être empilés dans la pile d'exécution, car l'appel suivant remplace simplement l'appel précédent dans le contexte d'exécution.
Il est possible de transformer, de façon simple, une fonction récursive terminale en une fonction itérative : c'est la dé-récursivation.