[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

[InstinctHack]

Merci du tuto

Autre exemple, peut-etre plus parlant, celle du parcours récursive d'un dossier, compliqué à mettre en place sans appeller une fonction par elle-meme

Et voilà un exemple de code simple à comprendre :

Code PHP :


<?php
function liste_Dirs($dir)
{
    $output = '<ul>';
    $dossier = opendir($dir);

    while($item = readdir($dossier))
    {
        $berk = array('.', '..'); // ne pas tenir compte de ses répertoires / fichiers

        if (!in_array($item, $berk))
        {
            $new_Dir = $dir.'/'.$item;

            if(is_dir($new_Dir))
            {
                $output .= '<li><strong>'.$item.'</strong></li>';
                $output .= liste_Dirs($new_Dir);
                $output .= '</li>';
            }
            else
            {
                $output .= '<li>'.$item.'</li>';
            }
        }
    }

    $output .= '</ul>';

    return $output;
}

// on appelle la fonction de cette façon :
echo liste_Dirs('./');
?>
 

source : http://www.viaphp.net/portions/fichiers-...repertoire



Et pour finir, celle de la fonction mathématiques factorielle (qui définie x multiplier par tous les entiers positifs inférieurs à lui)
en gros
4! == 4*3*2*1 == 4*3*2
(elle représente par exemple, le nombre d'ordres possible avec des élements)
avec 3 boules : [1] [2] [3]
les ordres possibles sont:
[1] [2] [3]
[1] [3] [2]
[2] [1] [3]
[2] [3] [1]
[3] [1] [2]
[3] [2] [1]

Bien que php possède des fonctions mathématiques (http://php.net/manual/fr/book.math.php), ainsi que des modules (http://www.php.net/manual/fr/ref.gmp.php) il est facile de coder soi-même cette fonction
voici donc l'équivalent de la fonction http://www.php.net/manual/fr/function.gmp-fact.php

Code PHP :


<?php
function factorielle($nbre)
{
        //Si $nbre = 0 on retourne 1 car soit 1! = 1, soit on est arrivés à la fin du calcul
        if($nbre === 0)
        {
                return 1;
        }
        else //Sinon on retourne le nombre multiplié par le reste de sa factorielle (avec $nbre décrémenté)
        {
                return $nbre*factorielle($nbre-1);
        }
}
 
//On affiche la factorielle de 6
echo factorielle(6);
 

Le code est extrait du ce tuto http://www.siteduzero.com/informatique/t...tilisation

voilà pour un petit rajout sympa