Définitions récursives

Une définition de méthode est récursive si son corps contient une expression d'invocation d'elle-même, dite invocation récursive   :

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

Une invocation fact(3) dans le corps de main provoque la suite d'invocations :

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

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

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

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, appelée diviser pour régner permet d'écrire assez facilement des algorithmes parmi les plus intéressants, voire les plus efficaces.

  

 

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).

  static final double EPS = 1e-5;

  static double zero_dicho(double a, double b) 
    // on suppose que f(a)*f(b) < 0
  {
    double m = (a+b)/2;
    double fm = f(m);
  
    if (Math.abs(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 Math.abs(fm)<EPS, EPS étant une variable statique, et Math.abs étant la fonction déclarée dans la classe Math calculant la valeur absolue d'un double.

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 :    

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

La figure A.3 représente l'arbre des invocations de fib(4), et la figure A.4 représente les états successifs de la pile d'exécution, 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.

  

Figure A.3: Arbre d'invocation de la suite de Fibonacci

  

Figure A.4: Pile d'exécution pour la suite de Fibonacci

 

Il n'y a aucune différence de principe, du point de vue de l'exécution, entre des méthodes définies récursivement ou pas. Le mécanisme d'allocation sur la pile s'applique de façon identique. Cependant, en l'absence de définitions récursives, chaque méthode a au plus un seul cadre d'invocation en cours. Il en résulte que la pile d'exécution est bornée ; elle peut être allouée initialement et ne croît pas en cours d'exécution. Le programme opère par transformations de cette zone mémoire fixe. On dit que le programme est itératif. S'il existe des définitions récursives, la pile d'exécution n'est pas bornée, croissant et décroissant pendant l'exécution. C'est le principal reproche adressé aux programmes utilisant des définitions récursives : ils consomment de l'espace mémoire, et bien qu'automatique, la gestion de la pile prend aussi du temps. Les programmeurs soucieux de l'efficacité de leurs programmes préfèrent donc les programmes itératifs, basés sur des structures d'itération. Ceux qui privilégient la facilité d'écriture et de compréhension des programmes n'hésitent pas à écrire des programmes récursifs.