La récursion est l'un des piliers fondamentaux de l'algorithmique. Bien que le concept puisse paraître intimidant au premier abord, il devient entuitif dès que l'on développe une certaine "mémoire musculaire" à travers la résolution de problèmes classiques. L'un des exemples les plus emblématiques pour illustrer ce concept est le puzzle des Tours de Hanoï.

Le défi des Tours de Hanoï

Le problème se compose de trois tiges — appelons-les Gauche, Milieu et Droite — et de n disques de tailles différentes. L'objectif est de déplacer tous les disques de la tige source vers une tige destination en respectant deux règles strictes :

1. On ne peut déplacer qu'un seul disque à la fois.
2. Un disque ne peut jamais être placé sur un disque plus petit que lui.

Pour déplacer trois disques de la gauche vers la droite, la séquence logique est la suivante :

1. Petit disque : Gauche → Droite
2. Disque moyen : Gauche → Milieu
3. Petit disque : Droite → Milieu
4. Grand disque : Gauche → Droite
5. Petit disque : Milieu → Gauche
6. Disque moyen : Milieu → Droite
7. Petit disque : Gauche → Droite

Implémentation par décomposition explicite

Au lieu de chercher immédiatement une solution générique, nous pouvons modéliser les déplacements entre des tiges spécifiques. Voici comment nous pourrions définir une fonction de transfert de la gauche vers la droite :

public static void deplacerGaucheVersDroite(int k) {
    // Cas de base : s'il n'y a qu'un disque, le mouvement est direct
    if (k == 1) {
        System.out.println("Disque 1 : Gauche -> Droite");
        return;
    }
    
    // Pour déplacer k disques de Gauche vers Droite :
    // 1. Déplacer k-1 disques de Gauche vers Milieu
    deplacerGaucheVersMilieu(k - 1);
    
    // 2. Déplacer le disque k (le plus grand) vers Droite
    System.out.println("Disque " + k + " : Gauche -> Droite");
    
    // 3. Déplacer les k-1 disques de Milieu vers Droite
    deplacerMilieuVersDroite(k - 1);
}

Cette approche, bien que pédagogique, nécessite d'écrire une fonction pour chaque combinaison possible de tiges (Gauche vers Milieu, Milieu vers Droite, etc.), ce qui est redondant.

Généralisation et abstraction du problème

Pour optimiser notre code, nous utilisons l'abstraction. Nous ne raisonnons plus en termes de "gauche" ou "droite", mais en termes de rôles : une tige source, une tige destination et une tige auxiliaire (ou tampon).

public static void resoudreHanoi(int n, String depart, String arrivee, String aide) {
    // Condition d'arrêt (Base Case)
    if (n == 1) {
        System.out.println("Déplacer disque 1 de " + depart + " vers " + arrivee);
        return;
    }

    // Étape A : Déplacer n-1 disques vers la tige d'aide pour libérer le plus grand
    resoudreHanoi(n - 1, depart, aide, arrivee);

    // Étape B : Déplacer le disque n vers la destination finale
    System.out.println("Déplacer disque " + n + " de " + depart + " vers " + arrivee);

    // Étape C : Déplacer les n-1 disques de la tige d'aide vers la destination
    resoudreHanoi(n - 1, aide, arrivee, depart);
}

public static void main(String[] args) {
    int nombreDeDisques = 3;
    resoudreHanoi(nombreDeDisques, "Source", "Destination", "Auxiliaire");
}

La pensée "Boîte Noire"

L'une des clés pour maîtriser la récursion est d'adopter une pensée boîte noire. Au lieu de tenter de suivre mentalement chaque empilement de la pile d'exécution (ce qui devient impossible pour n > 5), il faut faire confiance à la définitoin de la fonction.

Si votre fonction est capable de déplacer n-1 disques correctement, vous n'avez qu'à vouss soucier de la logique pour le n-ième disque. Cette abstraction permet de transformer un problème complexe en une suite de décisions simples. En ajoutant des paramètres à votre fonction (comme les noms des tiges), vous augmentez la capacité de votre algorithme à gérer différents états sans multiplier les lignes de code.