Une définition de fonction f est récursive terminale quand tout appel récursif est de la forme return f(...); ; autrement dit, la valeur retournée est directement la valeur obtenue par un appel récursif, sans qu'il n'y ait aucune opération sur cette valeur. Par exemple, l'appel récursif de la factorielle
return n*f(n-1);
n'est pas terminal, puisqu'il y a multiplication par n avant de retourner. Par contre, l'appel récursif dans
int f(int n, int a) { if (n<=1) { return a; } else { return f(n-1,n*a); } }
est terminal ; le paramètre a joue le rôle d'un accumulateur ; l'évaluation de f(5,1) conduit à la suite d'appels
dont la suite de retours
est en fait une suite d'égalités
La plupart des langages fonctionnels, notamment Scheme et ML, exécutent un programme à récursivité terminale comme s'il était itératif, c'est-à-dire en espace constant. Certains compilateurs C ont partiellement cette capacité. Sinon, il est facile de transformer une définition récursive terminale en itération pour optimiser l'exécution. Le programme dérécursivé est :
int fact_iter(int n) { int a = 1; while (n>1) { a = n*a; n = n-1; } return a; }