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