Discussion :

[radouane_as]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)?

[Franck.H]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é

[radouane_as]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Franck.H]

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
node n;
node parcours (node n)

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[radouane_as]

moi je veut faire un parcours en profendeur.

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

[Franck.H]

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 !

[radouane_as]

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.

[Franck.H]

un parcours prefixe en profondeur.

Ok donc voici un algorithme possible:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[radouane_as]

merci bien de ton aide.

[Franck.H]

merci bien de ton aide.

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

[Trap D]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[Franck.H]

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