Récursivité: Hanoi [Résolu]

Re,

En bref, ça donne le principe suivant :

Un disque arrive sur la tour d'arrivé en passant par la tour intermediaire

Premier passe
Depuis la tour départ on passe par la tour intermediaire pour arrivée à la tour d'arrivée

Deuxième passe
Ayant besoin de faire plusieurs mouvements la tour intermediaire est considerée la tour départ, la tour d'arrivée est considerée la tour intermediaire et la tour départ est considerée la tour d'arrivée.

et ainsi de suite.

Je pense que ton problème vient de l'ordre dans lequel s'effectue les affichages.
En effet les imbrications de récursivité rende peu lisible le phénomène.
Essaye d'analyser le programme avec un affichage qui t'informe plus sur la position dans la récursivité, que sur l'effet sur la tour en lui même, par exemple comme ceci :

int cpt=0;

void Hanoi(int n, char depart, char arrivee, char libre)
{
    if (n>0)
    {
         printf("---------------------------\n");
         
         printf("%d : %d - 1\n", ++cpt, n );
         Hanoi(n-1,depart,libre,arrivee);
         printf("%d : %d - 2\n", ++cpt, n );

         printf("\n%d : Bouger disque de %c a %c\n\n", ++cpt, depart, arrivee);

         printf("%d : %d - 3\n", ++cpt, n );
         Hanoi(n-1,libre,arrivee,depart);
         printf("%d : %d - 4\n", ++cpt, n );
         
         printf("---------------------------\n");
    }
    else if (n==0) printf("\n%d : ------> n==0\n\n",++cpt);
}

Les affichages de catégorie 1 sont lancés

Re,

Un exemple tu avais ici http://www.commentcamarche.net/...
Le nombre de déplacements est aussi compté.

je ne vois vraiment pas pourquoi il "remonte" dans le programme, sans boucles, rien...
Un peu plus tard je vais t'expliquer un peu ce qui se passe sous le capot ;-)

Parce qu'à l'intérieur de la fonction n=2, tu appelles la fonction n=1, mais à ce moment là tu n'as pas finie la fonction n=2 pour autant.
Du coup lorsque la fonction n=1 est terminée, il reste des instructions à effectuer de la fonction n=2, et c'est pour ça que l'on y "remonte" pour terminer.

Plus précisément, à l'étape 11 ce n'est pas le début de la fonction n=2, mais la suite, la preuve : c'est un 2-2 qui s'affiche et non un 2-1 !

Re,

La manière dont les fonctions sont exécutées en C est utile pour comprendre la récursivité.
Pour cela il faut comprendre comme est est organisé un programme C en mémoire.

A l'exécution un programme C est formé de 4 zones :
- la zone pour le code (les instructions qui s'exécutent au long de programme)
- la zone pour les données statiques (contient les données disponibles tout au long du programme - variables globales et locales statiques)
- un tas (contient les emplacement attribués dynamiquement - malloc)
- une pile ( les informations sur les appels des fonctions)

Le tas progresse du bas de la mémoire du programme vers haut, et la pile en sens inverse (ce n'est qu'une convention, en réalité cela peut varier)


Quand une fonction est appelé, sur la pile un bloc mémoire est alloué pour conserver les informations.

Exemple : la fonction factoriel

      | 1  si x =0 ou x=1
F(x)= |
      |  xF(x-1) si x>1

Voyons ce qui se passe pour 3!

F(3)=3*F(2)             - phase de descente
       F(2)=2*F(1)
              F(1)=1    - condition de fin 
       F(2)=(2)*(1)     - phase de remonté
F(3)=(3)*(2)
6                       - résultat

Le 1er appel de la fonction est placé sur la pile pour x=3
La condition terminale (x=0 ou x=1) n'est pas réalisée
En ce moment la fonction F est appelé à nouveau avec x=2
La condition n'est toujours pas réalisée.
Le fonction F sera appelé à nouveau avec x=1 qui est une condition terminale.
En ce moment l'expression qui correspond à x=2 est évalué comme 2 * 1 donc elle se termine avec la valeur 2
L'expression qui correspond à x=3 est évalué comme 3 * 2 * 1 = 6 et la récursivité est terminée.

Dans le cas des tours de Hanoï

Considérons les emplacements
D - départ
B - base
I - intermédiaire

Cas 1 - déplacement d'un disque

Pour déplacer un disque de D vers B l'emplacement intermédiaire est inutile

 ------------
_|____1_____|___   ______________  ____________


                     ------------
_________________   _|____1_____|_  ____________

         D                B              I

Cas 2 - déplacement de deux disques

Dans ce cas il faut transférer le disque du sommet sur l'emplacement Intermédiaire.
Ensuite le disque qui reste sur la position Départ il faut le mettre sur l'emplacement d'arrivée Base
Il reste a ramener le disque depuis l'emplacement Intermédiaire sur l'emplacement Base

  ----------
  |   2    |
 ------------
_|____1_____|_  ____________  ______________


 ------------                   -----------
_|____1_____|_  _____________ __|____2____|__

                 -----------    -----------
______________  _|____1____|_ __|____2____|__


                  ---------
                  |   2   |
                 -----------
______________ __|____1____|__ _____________

      D               B              I

Cas 3 - déplacement de trois disques

Dans ce cas il faut déplacer 2 disques du somment du D vers I en utilisant B comme emplacement intermédiaire.
Le disque depuis D vers B.
Les deux disques de I vers B en utilisant D comme intermédiaire.
Bref, pour déplacer les 3 disques on utilise deux fois la méthode qui permet de déplacer deux disques, ce qui explique la récursivité.

   --------
   |  3   |
  ----------
  |   2    |
 ------------
_|____1_____|_  _____________  ______________


                                  --------
                                  |  3   |
 ------------                    ----------
_|____1_____|_ ______________  __|___2____|___



                                    -------
                                    |  3  |
		 ------------      ----------
______________  _|____1_____|_   __|___2____|____


                   --------
                   |  3   |
                  ----------
                  |   2    |
                 ------------
______________  _|____1_____|__ ________________

          D           B                 I

Qu'est-ce que tu ne comprends pas ?
Regarde Wikipédia

Merci pour les explications mais je ne comprends tjs pas qqchose. J'ai essayé de mettre des printf un peu partout pour voir exactement comment fonctionne le code. Ce qui donne:

#include <stdio.h>
#define N 4

void Hanoi(int n, char depart, char arrivee, char libre) {
if (n>0) {
printf("%c %c %c \n", depart, arrivee, libre);
Hanoi(n-1,depart,libre,arrivee);
printf("%c %c %c \n", depart, arrivee, libre);
printf("Bouger disque de %c à %c\n", depart, arrivee);
printf("%c %c %c \n", depart, arrivee, libre);
Hanoi(n-1,libre,arrivee,depart);
printf("%c %c %c \n", depart, arrivee, libre);
}
}

int main() {
printf("Tour avec %d disques:\n", N);
Hanoi(N,'A','C','B');
return 0;
}


j'ai ensuite compilé et exécuté et j'obtiens:

Tour avec 4 disques:
A C B
A B C
A C B
A B C
A B C
Bouger disque de A Ó B
A B C
A B C /* pourquoi ce résultat et non C B A ? Suite à quelle instruction on obtient ça? */
A C B
Bouger disque de A Ó C
A C B
B C A
B C A
Bouger disque de B Ó C
B C A
B C A
A C B
A B C
Bouger disque de A Ó B
A B C
C B A
C A B
C A B
Bouger disque de C Ó A
C A B
C A B
C B A
Bouger disque de C Ó B
C B A
A B C
A B C
Bouger disque de A Ó B
A B C
A B C
C B A
A B C
A C B
Bouger disque de A Ó C
A C B
B C A
B A C
B C A
B C A
Bouger disque de B Ó C
B C A
B C A
B A C
Bouger disque de B Ó A
B A C
C A B
C A B
Bouger disque de C Ó A
C A B
C A B
B A C
B C A
Bouger disque de B Ó C
B C A
A C B
A B C
A B C
Bouger disque de A Ó B
A B C
A B C
A C B
Bouger disque de A Ó C
A C B
B C A
B C A
Bouger disque de B Ó C
B C A
B C A
A C B
B C A
A C B

Les 5 1ères lignes je comprends (enfin je crois),
le 1er printf donne A C B (là, ça va)
ensuite, d'après ce que je comprends, on appelle la fonction Hanoi (n-1, depart, libre, arrivee); jusqu'à ce qu'on ait n-3 ce qui nous donne:
A B C
A C B
A B C
puis l'autre printf:
A B C
et ensuite: Bouger disque de A à B
le printf en-dessous donne A B C
mais ensuite je ne comprends pas pourquoi on obtient encore A B C alors que pour moi, si on appelle Hanoi(n-1,libre,arrivee,depart); , on devrait avoir C B A.


J'espère m'être fait comprendre.
Si ça se trouve c'est tout bête, mais je ne vois pas la logique...
Merci d'avance pour vos réponses.

Ton programme est vraiment pas mal. Ca m'aide à y voir plus clair. Je crois en effet que c'est l'ordre dans lequel s'effectue le programme que je n'ai pas compris.

Mais pourquoi il passe de l'étape 10 : 1 - 4 à l'étape 11 : 2 - 2 ?
Je ne vois vraiment pas pourquoi il "remonte" dans le programme, sans boucles, rien...

Désolé d'abuser de ta gentillesse, mais ça m'intrigue.

C'est la magie de la récursivité ;-)

Au départ tu appelles Hanoi(4,...) à l'étape 1
Puisque 4>0, il appelle Hanoi(3,...) à l'étape 2
Ainsi de suite jusqu'à l'appel à Hanoi(0,...) à l'étape 5
Dans ce cas on termine la fonction Hanoi(0,...)
Donc on remonte à la fonction Hanoi(1,...) qui n'était pas terminée
Et on se retrouve à faire les étapes 6, 7, et 8
L'étape 9 appelle encore la fonction Hanoi(0,...) puis en sort
Et finalement à l'étape 10, on termine la fonction Hanoi(1,...)
Et on passe dès l'étape 11, à la fin de la fonction Hanoi(2,...)

puisque n=1, je ne vois pas pourquoi on peut remonter n à 2.
Et pourquoi dès l'étape 11 on passe à la fin de la fonction Hanoi(2,...).

Merci, j'ai enfin compris comment le programme fonctionne. (Mais avant de pouvoir refaire des programmes comme celui-là par moi-même, je pense qu'il va falloir un peu de temps.)
J'ai juste une question à propos des fonctions qu'on reprend. Par exemple, quand on arrive à 1-4 (dans le programme de KX) ou plus galement à la fin d'1 fonction Hanoi et qu'on rappelle la fonction Hanoi(2,...) non finie, pourquoi ne rappelle-t-on pas la fonction Hanoi(3,...) non finie non plus, avant Hanoi(2,...)? Je pense qu'on doit prendre la dernière fonction en mémoire, mais je préfère être sûre.

Merci d'avance pour les réponses.

En fait, c'est parce que Hanoi(3,...) inclus Hanoi(2,...) qui inclus Hanoi(1,...)

On ne peux repasser à 2, qu'une fois le 1-4 atteint, de même on ne repassera au 3, qu'une fois le 2-4 atteint