Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1462 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  recursion, je ne comprend pas cet algo

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

recursion, je ne comprend pas cet algo

n°667267
xiluoc
un pc pour les unirs ....
Posté le 08-03-2004 à 14:12:37  profilanswer
 

:hello: ,
il nexisterai pas sous linux une appli qui permettent de decomposer les actions d une fonction recursive en " retracant " le chemin ?
par ce que j ai dut mal avec ca :/
 
exemple pour 2^i
 

Code :
  1. //O(log n)
  2. long raised2 (int i)
  3. {
  4. if (i==0) return 1;
  5. if (i<0) return 1/raised2(-i);
  6. int tmp = raised2(i/2);
  7. if (i%2==0) return tmp * tmp;
  8. else return 2*tmp*tmp;
  9. }


 
voila comment je m y prend :
 
prenons 2^6
tmp = raised2 (6/2)
 la on passe a une nouvelle couche de la pile
  tmp = raised2(3/2)
    idem
      tmp = raised2 (1/2)
        idem
          i==0 retrun 1
c est apres que je suis perdu, il en fait quoi du  1 ? il ne passe pas directement a  
 if (i%2==0) return tmp * tmp;
else return 2*tmp*tmp;
 
 :sweat:

mood
Publicité
Posté le 08-03-2004 à 14:12:37  profilanswer
 

n°667312
xiluoc
un pc pour les unirs ....
Posté le 08-03-2004 à 14:29:37  profilanswer
 

ps : le code est bon, mais je le comprend pas (je dis ca au cas ou
)

n°667391
therier
heu...coucou!
Posté le 08-03-2004 à 15:43:38  profilanswer
 

Par curiosité, raised2(3), ça marche? :D

n°667903
Tentacle
Posté le 08-03-2004 à 22:23:08  profilanswer
 

[citation=667267,1]
voila comment je m y prend :
 
prenons 2^6
tmp = raised2 (6/2)
 la on passe a une nouvelle couche de la pile
  tmp = raised2(3/2)
    idem
      tmp = raised2 (1/2)
        idem
          i==0 retrun 1
c est apres que je suis perdu, il en fait quoi du  1 ? il ne passe pas directement a  
 if (i%2==0) return tmp * tmp;
else return 2*tmp*tmp;
 
 :sweat:  
[/citation]
 
bah il renvoie donc 1 et on se trouve au niveau du test  
if (i%2==0) return tmp * tmp;
else return 2*tmp*tmp;
 
à ce moment là, i = 1 donc i%2 = 1 et la fonction renvoie donc 2*1*1 = 2.
On remonte donc d'un niveau et on se retrouve encore une fois devant le test mais avec cette fois ci i = 3. 3 est impair et la fonction renvoie donc 2*2*2 = 8;
On remonte encore d'un niveau et on fait le test : 8 est pair et donc finalement la fonction renvoie 8*8=64=2^6.
 
De toute façon, ce n'est pas magique, à chaque appel récursif, tu mémorises l'état de l'appel en cours et tu passes à un nouvel appel. Quand tu as le résultat, tu reprends l'appel en cours. C'est pas toujours facile à voir mais le papier/crayon est ton ami :)
 

n°667914
xiluoc
un pc pour les unirs ....
Posté le 08-03-2004 à 22:28:03  profilanswer
 

ok merci je comprend mieux.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  recursion, je ne comprend pas cet algo

 

Sujets relatifs
je coince sur algo recursif :/Algo de compression bmp
[ALGO] Logiciel qui permet de cre des algos ?où trouver des cours pour les algo?
[algo] rendu planetaire[Algo] Est-ce que mon algo de tri marche?
exercice d'algo noté : help me please !!algo de regulation
[php]une erreur que je ne comprend pas[reglé]algo schematique
Plus de sujets relatifs à : recursion, je ne comprend pas cet algo


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR