Récursivité terminale

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

$$\mathtt{f(5,1)} \to \mathtt{f(4,5)} \to \mathtt{f(3,20)} \to \mathtt{f(2,60)} \to \mathtt{f(1,120)} \to$$

dont la suite de retours

$$\mathtt{f(1,120)} \stackrel{120}{\to} \mathtt{f(2,60)} \stac... ...(4,5)} \stackrel{120}{\to} \mathtt{f(5,1)} \stackrel{120}{\to}$$

est en fait une suite d'égalités

$$\mathtt{f(5,1)} = \mathtt{f(4,5)} = \mathtt{f(3,20)} = \mathtt{f(2,60)} = \mathtt{f(1,120)} = \mathtt{120}$$

La plupart des langages fonctionnels, notamment Scheme et CAML, 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;
}