Définitions récursives

Une définition de fonction est récursive si son corps contient un appel à elle-même, dit appel récursif :

int fact_rec(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n*fact_rec(n-1);
  }
}

Un appel fact_rec(3) dans le corps de main provoque la suite d'invocations :

$$\verb*\vert main()\vert \to \verb*\vert fact_rec(3)\vert \to... ... \verb*\vert fact_rec(1)\vert \to \verb*\vert fact_rec(0)\vert$$

et la suite de retours, qui retourne finalement 6 à main() :

$$\verb*\vert fact_rec(0)\vert \stackrel{1}{\to} \verb*\vert ... ...ert fact_rec(3)\vert \stackrel{6}{\to} \verb*\vert main()\vert$$

Les blocs d'activation sont successivement empilés sur la pile d'exécution, puis dépilés.

L'intérêt des définitions récursives est double. D'une part, elles permettent de transcrire de façon quasiment littérale certaines définitions mathématiques, souvent appelées récurrentes.

D'autre part, on obtient facilement des définitions récursives à partir de la conception récursive d'un algorithme : pour résoudre un problème par un algorithme, on applique ce même algorithme à un ou plusieurs sous-problèmes. Cette méthode de décomposition/recomposition, aussi appelée diviser pour régner permet d'écrire assez facilement des algorithmes parmi les plus intéressants, voire les plus efficaces ; pour accroître encore leur efficacité, on cherche souvent à les dérécursiver, c'est-à-dire à les transformer en définitions itératives.

La dichotomie est un exemple simple de cette méthode. On cherche à calculer un zéro d'une fonction réelle continue $f$ sur un intervalle $[a,b]$, prenant des valeurs de signes opposés aux extrémités. Le théorème des valeurs intermédiaires assure l'existence d'un zéro. L'idée de la dichotomie est de chercher un zéro sur $[a,(a+b)/2]$ ou bien sur $[(a+b)/2,b]$, selon le signe de $f((a+b)/2)$.

const double eps = 0.0001;                // définition de eps
double f(double);                         // déclaration de f

double zero_dicho(double a, double b) {
  double m = (a+b)/2;
  double fm = f(m);

  if (fabs(fm)<eps) {
    return m;
  } else {
    if (f(a)*fm<0) {
      return zero_dicho(a,m);
    } else {
      return zero_dicho(m,b);
    }
  }
}

La condition d'arrêt est fabs(fm)<eps, eps étant une variable globale, et fabs étant la fonction déclarée dans <cmath> calculant la valeur absolue d'un double.

Quand le corps d'une fonction comporte plusieurs appels récursifs, les différentes activations sont organisées sous la forme d'un arbre. L'exemple classique est celui de la définition récursive de la suite de Fibonacci :

int fib(int n) {
  if (n <= 1) {
    return 1;
  } else {
    return fib(n-1) + fib(n-2);
  }
}

L'expression conditionnelle permet une définition équivalente plus concise :

int fib(int n) {
  return n<=1 ? 1 : fib(n-1) + fib(n-2);
}

La figure 4 représente l'arbre des appels de fib(4), et la figure 5 représente les états successifs de la pile d'exécution, pour un appel de fib(4) dans main() (pour alléger, les blocs d'activation de main(), fib(4), fib(3), etc, y sont désignés par m, 4, 3, etc).

Figure 4: Arbre des appels de la suite de Fibonacci

On remarquera que certains appels sont exécutés plusieurs fois : fib(2) est exécuté deux fois, fib(1) trois fois, fib(0) deux fois.

Figure 5: Pile d'exécution pour la suite de Fibonacci