Récursivité

Une fonction ou plus généralement un algorithme qui contient un appel à elle-même est dite récursive. Deux fonctions peuvent s'appeler l'une l'autre, on parle alors de récursivité croisée.

Exemples :

• tapis de Sierpinski (exécuter)
• fonction d'Ackermann
• l'effet de Droste

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

Condition d'arrêt

Attention : considérons la fonction suivante :

public static int f(int i) {
  return i * f(i - 1);
}

Quelle est la valeur de l'appel f(3) ?

Un problème !
Exception in thread "main" java.lang.StackOverflowError

Que se passe-t-il ?

Des milions d'appels, chacun ayant besoin d'un espace mémoire pour les valeurs des paramètres de la fonction et de possibles variables locales (cet espace est appelé la pile d'exécution).

Remède : similairement aux boucles, on doit avoir une condition d'arrêt pour éviter les appels récursifs infinis.

Empilement des appels récursifs

Récursivité ou itération ?

La fonction factorielle présentée de manière récursive, peut être codée sous forme d'une itération :

final int N = 5;
int fact = 1;
for (int i=2; i<=N; i++)
  fact *= i;

• une méthode codée de manière récursive peut être implémentée de manière itérative
• l'itération utilise des boucles (while, for, do/while); la récursivité utilise des appels et l'instruction if
• dans les deux cas, nous avons une répetition et un test d'arrêt
• dans les deux cas, nous pouvons avoir une exécution infinie
• la récursivité peut s'avérer coûteuse en termes de temps de processeur et d'espace de mémoire
• une solution récursive est choisie lorsqu'elle refléte mieux la nature du problème et facilite la compréhension du programme
• en général, l'approche itérative demande une plus grande quantité du code

Exemple : tours de Hanoi (inventé par Édouard Lucas)

Le problème

Il y a 3 tours; la première porte n disques de tailles toutes différentes, empilés du plus grand (en bas) au plus petit (en haut). Le problème consiste à faire passer tous ces disques à la tour 2, en s'aidant de la troisième tour, en respectant les règles suivantes :

• on ne déplace qu'un disque à la fois
• aucun disque ne doit être empilé sur un disque de diamètre inférieur

Plusieurs visualisations sur le Web :

• wikipédia
• javaboy

Une solution

un algorithme récursif :

Soit :
  nombre : nombre de disques utilisés
  de : emplacement de départ
  à : emplacement de destination
  par : emplacement intermédiaire

déplacer (nombre, de, à, par)
   si nombre > 0 alors
     déplacer nombre - 1, de, par, à;
     bouger-un-disque de, à;
     déplacer nombre - 1, par, à, de;

Exercice

Codez ce programme en Java. Les appels de "bouger-un-disque" seront affichés sous la forme suivante (pour nombre = 3) :

  1 --> 3
  1 --> 2
  3 --> 2
  1 --> 3
  2 --> 1
  2 --> 3
  1 --> 3

Modifiez votre programme pourqu'il compte le nombre de déplacements de disque.