[PHP] apprendre la récursivité (jeu des tours de hanoi)

[JadnX]

Salut à tous,
Je vous partage un cours que j'ai eu sur la programmation, l'objectif est d'apprendre la récursivité, grâce à un jeu qui s'appel " Les Tours d'Hanoï ".

Je vais vous décrire, ou plutôt wiki, brièvement le principe du jeu:

Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de «départ» à une tour d'«arrivée» en passant par une tour «intermédiaire», et ceci en un minimum de coups, tout en respectant les règles suivantes :
- on ne peut déplacer plus d'un disque à la fois,
- on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

Merci Wikipedia ! :p

C'est bien beau, mais la récursivité quésaco..!?
La récursivité pour une fonction c'est le fait de faire appel à elle même, c'est un espèce d'empilage de la même fonction !

Prenez par exemple le film INCEPTION avec Leonardo DiCaprio , ils descendent à travers plusieurs niveaux de rêves (des rêves imbriqués les un dans les autres) pour pouvoir arriver à un résultat qui est d'introduire une idée dans l'esprit d'un bouffon. (mes excuses aux fans !)

Dans notre cas :
Le résultat est de trouver les déplacements à faire pour pouvoir déplacer la pile de disques.
La fonction, n'est pas le rêve mais, c'est le mouvement à répéter pour pouvoir arriver au résultat.

Problème, comment trouver le mouvement !?
On va donner des nom à nos trois tours ! Celle la plus à gauche sera la tour de départ ($td) la tour du milieu intermédiaire ($ti) et celle de droite la tour d'arrivé ($ta).

Résolvons le jeu avec 3 disques et relevons les mouvements. (simple non ? ) Vous pouvez testé ICI:
td -> ta
td -> ti
ta -> ti
td -> ta
ti -> td
ti -> ta
td -> ta

Bien maintenant interprétons :
1) on part du départ pour tous stocker sur l'intermédiaire !
td -> ta
td -> ti
ta -> ti
on résume => td devient ti et ti devient td

2) on fait le but du jeu on va du départ à l’arrivé !
td -> ta

3) on prend ce qu'on a stocker sur l'intermédiaire pour le mettre sur l'arrivé !
ti -> td
ti -> ta
td -> ta
on résume => ti devient ta et ta devient ti

Application PHP:
On va donc crée la fonction principale hanoi qui va nous permettre d'arrivé au résultat (déplacement du 2 ci dessus):

Code PHP :

hanoi($td, $ti, $ta){} //on met en paramètres le départ l'intermédiaire et l'arrivé. 


On fait la fonction pour le 1er déplacement (déplacement du 3 ci dessus):

Code PHP :

hanoi($td,$ta,$ti); //ti devient ta et ta devient ti. 


On fait la fonction pour le 2eme déplacement (déplacement du 1 ci dessus):

Code PHP :

hanoi($ti, $td, $ta); //td devient ti et ti devient td. 


Si vous m'avez suivis jusque là c'est bien, le plus gros est fait !

On construit la fonction pour 3 disques :

Code PHP :

function hanoi($td,$ti,$ta){           // pour aller au résultat 
         hanoi($td,$ta,$ti);           // on fait un déplacement 
         hanoi($ti,$td,$ta);           // puis le second
    } 


On y ajoute le nombre de disque pour pouvoir faire les déplacement,
ainsi qu'une vérification inutile de faire les déplacement si il n'y a qu'un disque :

Code PHP :

function hanoi($nb, $td, $ti, $ta) {
        if ($nb == '1') {
            echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
        } else {
            hanoi($nb - 1, $td, $ta, $ti);
            echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
            hanoi($nb - 1, $ti, $td, $ta);
        }
    } 


Pour finir on y ajoute un formulaire pour demander le nombre de disques à l'utilisateur :

Code PHP :

header('Content-type: text/html; charset=utf-8');
$formulaire = '<form method="post" action="">          
                                <label for="var1">Nombre de disques :</label>
                                <input type="text" name="var1" id="var1" />
                                <br />
                                <input type="submit" name="submit" value="Envoyer" />
                </form>';



if (isset($_POST['submit'])) {
    $n = $_POST['var1'];

    function hanoi($nb, $td, $ti, $ta) {
        if ($nb == '1') {
            echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
        } else {
            hanoi($nb - 1, $td, $ta, $ti);
            echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
            hanoi($nb - 1, $ti, $td, $ta);
        }
    }

    hanoi($n, 'td', 'ti', 'ta');
} else {
    echo $formulaire;
} 


Voila pour la récursivité on utilise la fonction hanoi dans la fonction hanoi...
Un rêve dans un rêve dans un rêve...

N’hésitez pas à m’envoyer un message pour corriger d’éventuelles erreurs ou fautes d’orthographes.
Un merci fait toujours plaisir !
En espèrent vous aider autant que vous le faites pour moi,
Cordialement,
JadnX