Précédent Remonter Suivant

Chapitre 6  Récursivité

Jusqu'à présent, nous avons programmé des fonctions simples, qui éventuellement en appelaient d'autres. Rien n'empêche d'imaginer qu'une fonction puisse s'appeler elle-même. C'est ce qu'on appelle une fonction récursive. L'intérêt d'une telle fonction peut ne pas apparaître clairement au premier abord, ou encore faire peur. D'un certain point de vue, elles sont en fait proches du formalisme de la relation de récurrence en mathématique. Bien utilisées, les fonctions récursives permettent dans certains cas d'écrire des programmes beaucoup plus lisibles, et permettent d'imaginer des algorithmes dont l'analyse sera facile et l'implantation récursive aisée. Nous introduirons ainsi plus tard un concept fondamental de l'algorithmique, le principe de diviser-pour-résoudre. Les fonctions récursives seront indispensables dans le traitement des types récursifs, qui seront introduits en INF-421.

Finalement, on verra que l'introduction de fonctions récursives ne se limite pas à une nouvelle syntaxe, mais qu'elle permet d'aborder des problèmes importants de l'informatique, comme la non-terminaison des problèmes ou l'indécidabilité de certains problèmes.

6.1  Premiers exemples

L'exemple le plus simple est celui du calcul de n!. Rappelons que 0!=1!=1 et que n! = n × (n-1)!. De manière itérative, on écrit :
    static int factorielle(int n){
        int f = 1;

        for(int k = n; k > 1; k--)
            f *= k;
        return f;
    }
qui implante le calcul par accumulation du produit dans la variable f.

De manière récursive, on peut écrire :
    static int fact(int n){
        if(n == 0) return 1; // cas de base
        else return n * fact(n-1);
    }
On a collé d'aussi près que possible à la définition mathématique. On commence par le cas de base de la récursion, puis on écrit la relation de récurrence.

La syntaxe la plus générale d'une fonction récursive est :
static <type_de_retour> <nomFct>(<args>){
    [déclaration de variables]
    [test d'arrêt]
    [suite d'instructions]
    [appel de <nomFct>(<args'>)]
    [suite d'instructions]
    return <résultat>;
}

Regardons d'un peu plus près comment fonctionne un programme récursif, sur l'exemple de la factorielle. L'ordinateur qui exécute le programme voit qu'on lui demande de calculer fact(3). Il va en effet stocker dans un tableau le fait qu'on veut cette valeur, mais qu'on ne pourra la calculer qu'après avoir obtenu la valeur de fact(2). On procède ainsi (on dit qu'on empile les appels dans ce tableau, qui est une pile) jusqu'à demander la valeur de fact(0) (voir figure 6.1).


Figure 6.1 : Empilement des appels récursifs.


Arrivé au bout, il ne reste plus qu'à dépiler les appels, pour de proche en proche pouvoir calculer la valeur de fact(3), cf. figure 6.2.


Figure 6.2 : Dépilement des appels récursifs.


La récursivité ne marche que si on ne fait pas déborder cette pile d'appels. Imaginez que nous ayons écrit :
    static int fact(int n){
        if(n == 0) return 1; // cas de base
        else return n * fact(n+1);
    }
Nous aurions rempli la pièce du sol au plafond sans atteindre la fin du calcul. On dit dans ce cas là que la fonction ne termine pas. C'est un problème fondamental de l'informatique de pouvoir prouver qu'une fonction (ou un algorithme) termine. On voit apparaître là une caractéristique primordiale de la programmation, qui nous rapproche de ce que l'on demande en mathématiques.

Exercice. On considère la fonction Java suivante :
    static int f(int n){
        if(n > 100)
            return n - 10;
        else
            return f(f(n+11));
    }
Montrer que la fonction retourne 91 si n ≤ 100 et n-10 si n > 100.

Encore un mot sur le programme de factorielle. Il s'agit d'un cas facile de récursivité terminale, c'est-à-dire que ce n'est jamais qu'une boucle for déguisée. Prenons un cas où la récursivité apporte plus. Rappelons que tout entier strictement positif n peut s'écrire sous la forme
n =
p
i=0
bi 2i = b0 + b1 2 + b2 22+ ⋯ + bp 2p,    bi ∈ {0, 1}
avec p ≥ 0. L'algorithme naturel pour récupérer les chiffres binaires (les bi) consiste à effectuer la division euclidienne de n par 2, ce qui nous donne n = 2 q1 + b0, puis celle de q par 2, ce qui fournit q1 = 2 q2 + b1, etc. Supposons que l'on veuille afficher à l'écran les chiffres binaires de n, dans l'ordre naturel, c'est-à-dire les poids forts à gauche, comme on le fait en base 10. Pour n=13=1+0⋅ 2+1⋅ 22+1⋅ 23, on doit voir
1101
La fonction la plus simple à écrire est :
    static void binaire(int n){
        while(n != 0){
            System.out.println(n%2);
            n = n/2;
        }
        return;
    }
Malheureusement, elle affiche plutôt :
1011
c'est-à-dire l'ordre inverse. On aurait pu également écrire la fonction récursive :
    static void binairerec(int n){
        if(n > 0){
            System.out.print(n%2);
            binairerec(n/2);
        }
        return;
    }
qui affiche elle aussi dans l'ordre inverse. Regardons une trace du programme, c'est-à-dire qu'on en déroule le fonctionnement, de façon analogue au mécanisme d'empilement/dépilement :

1. On affiche 13 modulo 2, c'est-à-dire b0, puis on appelle binairerec(6).

2. On affiche 6 modulo 2 (=b1), et on appelle binairerec(3).

3. On affiche 3 modulo 2 (=b2), et on appelle binairerec(1).

4. On affiche 1 modulo 2 (=b3), et on appelle binairerec(0). Le programme s'arrête après avoir dépilé les appels.

Il suffit de permuter deux lignes dans le programme précédent
    static void binairerec2(int n){
        if(n > 0){
            binairerec2(n/2);
            System.out.print(n%2);
        }
        return;
    }
pour que le programme affiche dans le bon ordre ! Où est le miracle ? Avec la même trace :

1. On appelle binairerec2(6).

2. On appelle binairerec2(3).

3. On appelle binairerec2(1).

4. On appelle binairerec2(0), qui ne fait rien.

3.' On revient au dernier appel, et maintenant on affiche b3 = 1mod2 ;

2.' on affiche b2 = 3mod2, etc.

C'est le programme qui nous a épargné la peine de nous rappeler nous-mêmes dans quel ordre nous devions faire les choses. On aurait pu par exemple les réaliser avec un tableau qui stockerait les bi avant de les afficher. Nous avons laissé à la pile de récursivité cette gestion.

6.2  Un piège subtil : les nombres de Fibonacci

Supposons que nous voulions écrire une fonction qui calcule le n-ième terme de la suite de Fibonacci, définie par F0 = 0, F1 = 1 et
n≥ 2, Fn = Fn-1 + Fn-2.
Le programme naturellement récursif est simplement :
    static int fib(int n){
        if(n <= 1) return n; // cas de base
        else return fib(n-1)+fib(n-2);
    }
On peut tracer l'arbre des appels pour cette fonction, qui généralise la pile des appels :

Le programme marche, il termine. Le problème se situe dans le nombre d'appels à la fonction. Si on note A(n) le nombre d'appels nécessaires au calcul de Fn, il est facile de voir que ce nombre vérifie la récurrence :
A(n) = A(n-1) + A(n-2)
qui est la même que celle de Fn. Rappelons le résultat suivant :
Proposition 3   Avec φ = (1+√ )/2 ≈ 1.618… (nombre d'or), φ' = (1-√ )/2 ≈ -0.618…:


On fait donc un nombre exponentiel d'appels à la fonction.

Une façon de calculer Fn qui ne coûte que n appels est la suivante. On calcule de proche en proche les valeurs du couple (Fi, Fi+1). Voici le programme :
    static int fib(int n){
        int i, u, v, w;

        // u = F(0); v = F(1)
        u = 0; v = 1;
        for(i = 2; i <= n; i++){
            // u = F(i-2); v = F(i-1)
            w = u+v;
            u = v;
            v = w;
        }
        return v;
    }

De meilleures solutions pour calculer Fn vous seront données en TD.

6.3  Fonctions mutuellement récursives

Rien n'empêche d'utiliser des fonctions qui s'appellent les unes les autres, du moment que le programme termine. Nous allons en donner maintenant des exemples.

6.3.1  Pair et impair sont dans un bateau

Commençons par un exemple un peu artificiel: nous allons écrire une fonction qui teste la parité d'un entier n de la façon suivante: 0 est pair; si n > 0, alors n est pair si et seulement si n-1 est impair. De même, 0 n'est pas impair, et n>1 est impair si et seulement si n-1 est pair. Cela conduit donc à écrire les deux fonctions:
    // n est pair ssi (n-1) est impair
    static boolean estPair(int n){
        if(n == 0) return true;
        else return estImpair(n-1);
    }

    // n est impair ssi (n-1) est pair
    static boolean estImpair(int n){
        if(n == 0) return false;
        else return estPair(n-1);
    }

qui remplissent l'objectif fixé.

6.3.2  Développement du sinus et du cosinus

Supposons que nous désirions écrire la formule donnant le développement de sinn x sous forme de polynôme en sinx et cosx. On va utiliser les formules
sinn x = sinx cos(n-1) x + cosx sin(n-1) x,
cosn x = cosx cos(n-1) x - sinx sin(n-1) x
avec les deux cas d'arrêt: sin0 = 0, cos0 = 1. Cela nous conduit à écrire deux fonctions, qui retournent des chaînes de caractères écrites avec les deux variables S pour sinx et C pour cosx.
  static String DevelopperSin(int n){
      if(n == 0) return "0";
      else{
          String g = "S*(" + DevelopperCos(n-1) + ")";
          return g + "+C*(" + DevelopperSin(n-1) + ")";
      }
  }

  static String DevelopperCos(int n){
      if(n == 0) return "1";
      else{
          String g = "C*(" + DevelopperCos(n-1) + ")";
          return g + "-S*(" + DevelopperSin(n-1) + ")";
      }
  }

L'exécution de ces deux fonctions nous donne par exemple pour n=3:


sin(3*x)=S*(C*(C*(1)-S*(0))-S*(S*(1)+C*(0)))+C*(S*(C*(1)-S*(0))+C*(S*(1)+C*(0)))
Bien sûr, l'expression obtenue n'est pas celle à laquelle nous sommes habitués. En particulier, il y a trop de 0 et de 1. On peut écrire des fonctions un peu plus compliquées, qui donnent un résultat simplifié pour n=1:
    static String DevelopperSin(int n){
        if(n == 0) return "0";
        else if(n == 1) return "S";
        else{
            String g = "S*(" + DevelopperCos(n-1) + ")";
            return g + "+C*(" + DevelopperSin(n-1) + ")";
        }
    }

    static String DevelopperCos(int n){
        if(n == 0) return "1";
        else if(n == 1) return "C";
        else{
            String g = "C*(" + DevelopperCos(n-1) + ")";
            return g + "-S*(" + DevelopperSin(n-1) + ")";
        }
    }

ce qui fournit:
sin(3*x)=S*(C*(C)-S*(S))+C*(S*(C)+C*(S))
On n'est pas encore au bout de nos peines. Simplifier cette expression est une tâche complexe, qui sera traitée au cours d'Informatique fondamentale.

6.4  Diviser pour résoudre

C'est là un paradigme fondamental de l'algorithmique. Quand on ne sait pas résoudre un problème, on essaie de le couper en morceaux qui seraient plus faciles à traiter. Nous allons donner quelques exemples classiques, qui seront complétés par d'autres dans les chapitres suivants du cours.

6.4.1  Recherche d'une racine par dichotomie

On suppose que f :[a, b] → R est continue et telle que f(a) < 0, f(b) > 0 :

Il existe donc une racine x0 de f dans l'intervalle [a, b], qu'on veut déterminer de sorte que |f(x0)| ≤ ε pour ε donné. L'idée est simple : on calcule f((a+b)/2). En fonction de son signe, on explore [a, m] ou [m, b].

On commence par programmer la fonction f :
    static double f(double x){
        return x*x*x-2;
    }
puis la fonction qui cherche la racine :
    // f(a) < 0, f(b) > 0
    static double racineDicho(double a, double b, double eps){
        double m = (a+b)/2;
        double fm = f(m);

        if(Math.abs(fm) <= eps)
            return m;
        if(fm < 0) // la racine est dans [m, b]
            return racineDicho(m, b, eps);
        else // la racine est dans [a, m]
            return racineDicho(a, m, eps);
    }

6.4.2  Les tours de Hanoi

Il s'agit là d'un jeu inspiré par une fausse légende créée par le mathématicien français Édouard Lucas. Il s'agit de trois poteaux sur lesquels peuvent coulisser des rondelles de taille croissante. Au début du jeu, toutes les rondelles sont sur le même poteau, classées par ordre décroissant de taille à partir du bas. Il s'agit de faire bouger toutes les rondelles, de façon à les amener sur un autre poteau donné. On déplace une rondelle à chaque fois, et on n'a pas le droit de mettre une grande rondelle sur une petite. Par contre, on a le droit d'utiliser un troisième poteau si on le souhaite. Nous appelerons les poteaux D (départ), M (milieu), A (arrivée).

La résolution du problème avec deux rondelles se fait à la main, à l'aide des mouvements suivants. La position de départ est:



On commence par déplacer la petite rondelle sur le poteau M:



puis on met la grande en place sur le poteau A:



et enfin la petite rejoint la grande:



La solution générale s'en déduit (cf. figure 6.3). Le principe est de solidariser les n-1 premières rondelles. Pour résoudre le problème, on fait bouger ce tas de n-1 pièces du poteau D vers le poteau M (à l'aide du poteau A), puis on bouge la grande rondelle vers A, puis il ne reste plus qu'à bouger le tas de M vers A en utilisant D. Dans ce dernier mouvement, la grande rondelle sera toujours en dessous, ce qui ne créera pas de problème.


Figure 6.3 : Les tours de Hanoi.


Imaginant que les poteaux D, M, A sont de type entier, on arrive au programme suivant :
    static void Hanoi(int n, int D, int M, int A){
        if(n > 0){
            Hanoi(n-1, D, A, M);
            System.out.println("On bouge "+D+" vers "+A);
            Hanoi(n-1, M, D, A);
        }
    }

6.5  Un peu de théorie

Les fonctions récursives permettent de toucher du doigt plusieurs concepts d'informatique fondamentale.

6.5.1  La fonction d'Ackerman

On la définit de la façon suivante :



et on peut la programmer comme suit :
    static int ackerman(int m, int n){
        if(m == 0) return n+1;
        else if(n == 0)
            return ackerman(m-1, 1);
        else
            return ackerman(m-1, ackerman(m, n-1));
    }

Son intérêt réside dans le fait qu'elle prend des valeurs énormes très rapidement, alors que le programme qui la définit est court. Ainsi, on peut montrer que



nombre bien plus grand que le nombre estimé de particules dans l'univers.

6.5.2  Le problème de la terminaison

Nous avons vu combien il était facile d'écrire des programmes qui ne s'arrêtent jamais. On aurait pu rêver de trouver des algorithmes ou des programmes qui prouveraient cette terminaison à notre place. Hélas, il ne faut pas rêver.
Théorème 2  [Gödel]   Il n'existe pas de programme qui décide si un programme quelconque termine.

Expliquons pourquoi de façon informelle, en trichant avec Java. Supposons que l'on dispose d'une fonction Termine qui prend un programme écrit en Java et qui réalise la fonctionnalité demandée : Termine(fct) retourne true si fct termine et false sinon. On pourrait alors écrire le programme suivant :
  static void f(){
      while(Termine(f))
          ;
  }

C'est un programme bien curieux. En effet, termine-t-il ? Ou bien Termine(f) retourne true et alors la boucle while est activée indéfiniment, donc il ne termine pas. Ou bien Termine(f) retourne false et alors le programme ne termine pas, alors que la boucle while n'est jamais effectuée. Nous venons de rencontrer un problème indécidable, celui de l'arrêt. Classifier les problèmes qui sont ou pas décidables représente une part importante de l'informatique théorique.


Précédent Remonter Suivant