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... ...o \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 f... ...vert 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.

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 et plus condensée :

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

La figure 3 représente l'arbre des appels de fib(4), et la figure 4 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 3: 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 4: Pile d'exécution pour la suite de Fibonacci