Fibonacci : 2 appels Récursifs

Bonjour ,

Lors d' un appel du méthode récursif , on a besoin d' un cas qui permet d'arreter la méthode récursif et c' est a ce moment que se réalise le désempilement.

Mais dans le cas du calcul de la suite de Fibonacci , il y a 2 appels recursif:

[CODE]public static int Finorec(int n ){

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int resultat;     System.out.println ("Entrée 1 , n = " + n ); if (n ==0 || n== 1) { resultat = 1;   }else {   System.out.println ("Entrée 2 , n = " + n ); resultat = Finorec (n-1) + Finorec (n-2);     System.out.println ("Sortie 2 , n = " + n + " resultat = " + resultat);     } System.out.println ("Sortie 1, n = " + n + " resultat = " + resultat );   return resultat;

---

Autant avec factorielle en récursif , j' avais compris le fonctionnement , mais ici comment cela se passe t il?J' ai mis des traces pour essayer d' en comprendre le cheminement.
Une fois qu il rencontre le premier appel recursif Finorec (n-1)comment fait il pour le 2 eme appel récursif?

merci

Le fait qu'il y ait 1 ou x appels récursifs ne change rien. Un moyen simple de visualiser l'empilement et le dépilement des rappels avec la suite de Fibonacci est de le voir sous forme d'arbre.

Une petite image avec n égal 3 et où j'ai mis l'ordre des appels :
http://img145.imageshack.us/img145/4716/fibrecdz3.gif

Hello,

Dans le cas de cet algo, la condition de retour est double : soit n=0, soit n=1. De cette façon quel que soit l'embranchement du calcul, l'algorithme va se terminer.

bonsoir,

notez que l'algo. de Fibonacci calculé récursivement est de complexité exponentielle et donc franchement à éviter, c'est d'ailleurs souvent par Fibonacci qu'on montre les limites de la récursivité

par contre tu peux utiliser la mémoisation, c'est la même principe mais sans appels, tu as un tableau mettons tab:

tu connais Fib(0) et Fib(1) ce sera les deux premieres cases de ton tableau, de là tu calcule la case "n" en faisant la case n-1 + la case n-2 ;)

je vous remercie ca ma aidé ,
j ai toujours des mais , la c plus dur car ca concerne hanoi (les socles ont été changées par les chiffres 1 ,2 et 3) , je suis completement noyé:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public static void hanoi(int n , int i , int j) { System.out.println ("**** Entree (1) dans hanoi **** n = " + n); if (n== 1){ System.out.println (i + "====>"+ j); }else { System.out.println ("****Entree (2) dans hanoi **** n = " + n); hanoi (n-1 , i , 6-i-j); hanoi (1,i,j); hanoi (n-1 , 6-i-j,j); System.out.println ("****Sortie (2) dans hanoi **** n = " + n); } System.out.println ("****Sortie (1) dans hanoi **** n = " + n); } public static void main (String [] args ){ Scanner lc = new Scanner (System.in); int nbdisques; System.out.println ("Saisir le nombre de disque : "); nbdisques = lc.nextInt(); hanoi (nbdisques , 1, 2 ); }

---

Imaginons je rentre 3 :
cela se produit comment vu qu ' ici quand je rappele hanoi et que n est different de 1 je rentre dans le else.

Vraiment pas tres simple a assimiler je trouve

bon le principe : on dispose de trois pieux et d'une pile de N disques de diamètre décroissant troués au centre et empilés sur le pieu de gauche. On désire reconstituer la pile sur le pieu central en transférant les disques 1 à 1 de façon telle que jamais un disque ne repose sur un disque de diamètre inférieur.

C'est évidemment possible si N = 1 en un seul mouvement.
supposons quelle le soit si n = 1, N-1 et posons H(n) le nombre de mouvements requis.
Si n = N, on peut transférer N-1 disques du pieu gauche au pieu droit sans toucher au disque le plus grand en H(N-1) opérations (hypothèse de récurrence).
Ensuite on pose le grand disque sur le pieu central et on effectue à nouveau H(N-1) opérations pour transférer les disques du pieu droit au pieu central.
Donc H(N) = H(N-1) + 1 + H(N-1) = 2H(N-1) + 1. (définition récursive)

Calculons quelques valeurs de H(N); il vient :
H(1) = 1 ; H(2) = 3 ; H(3) = 7 ; H(4) = 15 ; H(5) = 31 … ce qui suggère que H(N) = 2N-1


en gros en termes de mouvements à accomplir

On peut utiliser une procédure H à 4 paramètres entiers: H(N,O,D,I) où
• N est le nombre de disques de la pile à déplacer
• O est l'emplacement d'origine de la pile
• D est l'emplacement de destination de la pile
• I est l'emplacement intermédiaire de la pile
O, I et D sont choisis tous différents parmi les nombres 1, 2 et 3

Il vient :

Code:

---

1 2 3 4 5 6

Procedure H(N,O,D,I) ; Si N > 1 faire H(N-1,O,I,D) Ecrire ("Déplacer disque pile", O, "vers pile", D); H(N-1,I,D,O) Sinon Ecrire ("Déplacer disque pile", O, "vers pile", D);

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Exécution pour N = 3   H(3,1,3,2) H(2,1,2,3) H(1,1,3,2) Déplace 1 vers 3   Déplace 1 vers 2   H(1,3,2,1)  Déplace 3 vers 2   Déplace 1 vers 3   H(2,2,3,1) H(1,2,1,3)  Déplace 2 vers 1   Déplace 2 vers 3   H(1,1,3,2)

---

En fait l'algo des tours de Hanoï est très simple si on le formule de la façon suivante :

Pour déplacer X palets de la tour 1 à la tour 3, faire ceci :
* Déplacer X-1 palets de la tour 1 sur la tour 2
* Déplacer le plus grand palet restant sur la tour 3
* Déplacer les X-1 palets de la tour 2 sur la tour 3

On voit tout de suite où est la récursivité : pour déplacer les X-1 palets de la tour 1 à la tour 2 il suffit de faire exactement la même chose que pour X palets en permutant les tours.