Récursivité terminale

Une invocation récursive d'une fonction f est dite terminale si elle est de la forme return f(...); ; autrement dit, la valeur retournée est directement la valeur obtenue par l'invocation récursive, sans qu'il n'y ait d'opération sur cette valeur. Par exemple, l'invocation récursive de la factorielle

    return n*f(n-1);

n'est pas terminale, puisqu'il y a multiplication par n avant de retourner. Par contre, l'invocation récursive dans

  static int f(int n, int a) {
    if (n<=1) {
      return a;
    } else {
      return f(n-1,n*a);
    }
  }

est terminale. Dans cette version, le paramètre a joue le rôle d'un accumulateur ; l'évaluation de f(5,1) conduit à la suite d'invocations

$$\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)} \stack... ...(4,5)} \stackrel{120}{\to} \mathtt{f(5,1)} \stackrel{120}{\to}$$

est en fait une suite d'égalités

f(5,1) = f(4,5) = f(3,20) = f(2,60) = f(1,120) = 120

Une définition de méthode est récursive terminale quand toute invocation récursive est terminale. La plupart des langages fonctionnels, notamment CAML, exécutent un programme à récursivité terminale comme s'il était itératif, c'est-à-dire en espace constant. Certains compilateurs d'autres langages 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 :

  static int factIter(int n) {
    int a = 1;
    while (n>1) {
      a = n*a;
      n = n-1;
    }
    return a;
  }