probleme fonction recursive

bonjour tous,
je veut savoir comment un compilateur traite cette fonction:

Code:

---

1 2 3 4 5 6 7 8 9

//juste un exemple int f(n) int n; { if (n<0)return 1;   y=3*n; f(n-1); f(n-3); }

---

la question est:
quand on arive a l'instruction "f(n-1);" en va reprendre f avec le parametre n-1;
mais apres est qu'il va passer au instruction suivant "f(n-2);" ou il va appeler de nouveau f((n-1)-1)?

Citation:

---

Envoyé par radouane_as

bonjour tous,
je veut savoir comment un compilateur traite cette fonction:

Code:

---

1 2 3 4 5 6 7 8 9

//juste un exemple int f(n) int n; { if (n<0)return 1;   y=3*n; f(n-1); f(n-3); }

---

la question est:
quand on arive a l'instruction "f(n-1);" en va reprendre f avec le parametre n-1;
mais apres est qu'il va passer au instruction suivant "f(n-2);" ou il va appeler de nouveau f((n-1)-1)?

---

Non je ne pense pas, surtout qu'une fois la condition de sortie effectuée, il remonte dans la pile des appels, d'ailleurs ta tonction n'est pas bien écrite, du moins au début même pour un code d'exemple... et en plus tu n'as même pas déclaré la variable y ! En plus cette variable ici ne sert strictement à rien du tout !

Code:

---

1 2 3 4 5 6 7 8 9 10 11

//juste un exemple int f (int n) { int y = 0;   if (n<0) return 1;   y=3*n; f(n-1); f(n-3); }

---

Tu peux lire un des mes tutoriels sur la récursivité: Récursivité en Langage C, en espérant que ca t'aidera à comprendre les mécanismes de bases de la récursivité ;)

mon probleme c'est que je veut parcourir un arbre binaire copletemet:
le code est le suivant:

Code:

---

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

node n; node parcours (node n) {     if (n==null) return null; //je veut chercher un noeud particulier switch(n.type) {case a://a est un entier return n; default: parcours(droit(n));//fils droite de n aussi c'est un noeud parcours(gauche(n));//fils gauche de n aussi c'est un noeud return; } }

---

est ce que ca permet de parcourer tout l'arbre.

Arf les arbres je suis pas encore un grand spécialiste(je suis justement en train de les étudier)... mais ce que je peut te dire c'est que tu fait en ce moment même du C année 70 :lol:

Cette forme de fonction n'existe carrément plus, m'étonne qu'un compilateur l'accepte encore:

Code:

---

1 2	node n; node parcours (node n)

---

Une version plus à jour et dans l'air du temps serait:

Code:

---

node parcours (node n)

---

En tout cas, ce que je sais, c'est que l'algorithme change suivant le type de parcours que tu veux... un parcours en profondeur ? Si en profondeur, quel type: préfixe, infixe, suffixe? Un parcours en largeur ?

moi je veut faire un parcours en profendeur.

"pour la declaration de n au dessus c'est un oublit merci"

Citation:

---

Envoyé par radouane_as

moi je veut faire un parcours en profendeur.

"pour la declaration de n au dessus c'est un oublit merci"

---

Mais quel type de parcours en profondeur très exactement ? Il en existe trois si tu veux tout savoir !

• Préfixe
• Infixe
• Suffixe

Il faut choisir car l'ordre de parcours change !

Citation:

---

Envoyé par Franck.H

Mais quel type de parcours en profondeur très exactement ? Il en existe trois si tu veux tout savoir !

• Préfixe
• Infixe
• Suffixe

Il faut choisir car l'ordre de parcours change !

---

un parcours prefixe en profondeur.

Citation:

---

Envoyé par radouane_as

un parcours prefixe en profondeur.

---

Ok donc voici un algorithme possible:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Parcours (Abre N) { Tester (N)   Si Gauche_non_vide Alors Parcours (gauche (N)) FinSi   Si Droite_non_vide Alors Parcours (droite (N)) FinSi }

---

En espérant avoir pû t'aider ;)

merci bien de ton aide.:lol:

Citation:

---

Envoyé par radouane_as

merci bien de ton aide.:lol:

---

De rien, y'a juste ma première réponse qui n'était pas vraiment juste, j'avais oublié le fait que les appels sont faits entièrement, donc le premier puis une fois celui-ci terminé, le second qui est fait ... manque d'inattention ;)

Il y quand même un gros problème dans ce code :

Code:

---

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

node parcours (node n) { if (n==null) return null; //je veut chercher un noeud particulier switch(n.type) { case a://a est un entier return n; default: parcours(droit(n));//fils droite de n aussi c'est un noeud parcours(gauche(n));//fils gauche de n aussi c'est un noeud return; } }

---

Celà ne devrait jamais compiler : parcours doit retourner un noeud, dans le default il ne retourne rien.
D'autre part, la valeur de retour n'est pas récupérée après parcours (droit(n)) et parcours(gauche(n)), alors, pourquoi retourner une valeur si elle ne sert à rien ?

Citation:

---

Envoyé par Trap D

Celà ne devrait jamais compiler : parcours doit retourner un noeud, dans le default il ne retourne rien.
D'autre part, la valeur de retour n'est pas récupérée après parcours (droit(n)) et parcours(gauche(n)), alors, pourquoi retourner une valeur si elle ne sert à rien ?

---

Tout à fait :mouarf: