Récursivité multiple

Quand le corps d'une fonction comporte plusieurs invocations récursives, leur évaluation est organisée sous la forme d'un arbre. L'exemple classique est celui de la définition récursive de la suite de Fibonacci :

44#44

ce qui se traduit immédiatement en Java par :

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

La figure 1.3 représente l'arbre des invocations de fib(4), et la figure 1.4 représente les états successifs de la pile, pour une invocation de fib(4) dans main(...) (pour alléger, les cadres d'invocation de main(), fib(4), fib(3), etc, y sont désignés par m, 4, 3, etc). On remarquera que certaines invocations sont exécutées plusieurs fois : fib(2) est exécutée deux fois, fib(1) trois fois, fib(0) deux fois. Rappelons que les sous-expressions étant évaluées de gauche à droite, l'invocation fib(n-1) est évaluée avant fib(n-2).

Figure 1.3: Arbre d'invocation de la suite de Fibonacci

45#45

Figure 1.4: Évolution de la pile pour la suite de Fibonacci

46#46