Récursivité terminale1#1

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

82#82

dont la suite de retours

83#83

est en fait une suite d'égalités

84#84

Une définition de fonction 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;
  }