Discussion :

[1abdou1]

Bonjour a tous,

Moi aussi j'ai trouvé des difficultés pour transformer cette fonction « recur » en une fonction itérative. Donc veuillez m'aider à la faire :

voici la fonction :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void F3_Rec (int x, int y)
{
    Inst1 ; Inst2 ;
 
    if (x>0 && y>0)
    {
        x= x/10 ; y= y/10 ;
        F3_Rec (x,y) ;  
        Inst3 ; Inst4 ;
    }
 
    Inst5 ; Inst6 ;
    F3_Rec (x,y);
}

et voici ma réponse (chui sur qu'elle n'est pas bonne ) :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Void  F3_iter (int x,int y)
{
    pile *P,*S;
 
    initpile(&P);
    initpile(&S) ;
 
    Inst1; Inst2 ;
 
    While(x>0 && y>0)
    {
        x=x/10 ; y=y/10 ;
        empiler(&P,x);
        empiler(&P,y);
 
        inst1; inst2;
    }
 
    {
        inst5; inst6;
    }
 
    while (!pilevide(P))
    {
        depiler(&P,&y);
        depiler(&P,&x);
        inst3; inst4; inst5; inst6;
        empiler(&S,&x);
        empiler(&S,&y);
    }
 
    while( !pilevide(S))
    {
        depiler(&S,&y);
        depiler(&S,&x);
        inst1 ;inst2 ;
        {inst5 ;inst6 ;}
 
        while (!pilevide(S))
        {
            depiler(&S,&y);
            depiler(&S,&x);
            inst3 ;inst4 ;inst5 ;inst6 ;
        }

[Médinoc]

Est-ce normal que ce soit du "itératif avec pile" plutôt que tu vrai itératif? Cela respecte-t-il la consigne?

Edit: Aussi, est-ce normal que cette fonction n'ait aucune condition de retour? Et a-t-on droit au goto?

[kwariz]

Est-ce normal que ce soit du "itératif avec pile" plutôt que tu vrai itératif? Cela respecte-t-il la consigne?

Edit: Aussi, est-ce normal que cette fonction n'ait aucune condition de retour? Et a-t-on droit au goto?

Hello,

quand je vois (vraiment en premier jet) des instructions comme x=x/10 (avec x un int) avant un appel récursif et dont les valeurs peuvent être utilisées par la suite je me dis que l'on ne pourra pas se passer de pile car la division entière n'est pas inversible.
Personnellement je ne trouve pas qu'il y ait du vrai itératif ou du faux itératif mais je comprends ce que tu veux dire, sans utiliser une pile qui mimerait la pile récursive :-D
En revanche je m'inquiète aussi de la condition d'arrêt car dans l'état F3_Rec est une boucle sans fin (en supposant même que les paramètres sont positifs ...), peut-être un return dans le if ????

[Metalman]

Hmmm... je plussoie kwariz : la boucle imbriquée à la fin me parait bizarre : c'est la même condition qui les fini...
Ca veut dire que tu fais un tour de la boucle principale, puis tu vides ta pile sur la boucle imbriquée....

[Sve@r]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void F3_Rec (int x, int y)
{
    Inst1 ; Inst2 ;
 
    if (x>0 && y>0)
    {
        x= x/10 ; y= y/10 ;
        F3_Rec (x,y) ;  
        Inst3 ; Inst4 ;
    }
 
    Inst5 ; Inst6 ;
    F3_Rec (x,y);
}

Bonjour

Moi je me demande déjà quand s'arrête cette fonction (et accessoirement si Inst3 et Inst4 seront même exécutés un jour)...

[1abdou1]

Est-ce normal que ce soit du "itératif avec pile" plutôt que tu vrai itératif? Cela respecte-t-il la consigne?

Edit: Aussi, est-ce normal que cette fonction n'ait aucune condition de retour? Et a-t-on droit au goto?

oui ;c'est avec une pile qu'on elimine la recursivité mais je sais pas comment
help please;

[1abdou1]

Bonjour

Moi je me demande déjà quand s'arrête cette fonction (et accessoirement si Inst3 et Inst4 seront même exécutés un jour)...

ben moi je ne sais pas quand elle va s'arrter mais si tu veut voir l'enoncé c'est le 1er exercice de ce devoir tien :
http://www.4shared.com/file/SfzdJTWK/Devoir1_2013.html?

[Médinoc]

McAfee me gueule dessus quand je tente de DL ton document sur 4shared.

[kwariz]

Bon, avec le 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
void F3_Rec (int x, int y)
{
    Inst1 ; Inst2 ;
 
    if (x>0 && y>0)
    {
        x= x/10 ; y= y/10 ;
        F3_Rec (x,y) ;  
        Inst3 ; Inst4 ;
    }
 
    Inst5 ; Inst6 ;
    F3_Rec (x,y);
}

on voit qu'on commence par un inst1;inst2; puis tant que les deux paramètres sont strictement positifs on les divise par 10, l'appel récursif nous fait exécuter inst1;inst2;. Une fois qu'un des deux n'est plus strictement positif on fait une boucle infinie sur inst5;inst6;inst1;inst2;
D'où :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
F3_iter(int x, int y)
{
  inst1;inst2;
  while ( x>0 && y>0 ) {
    x=x/10;
    y=y/10;
    inst1; inst2;
  }
  while (1) {
    inst5;inst6;
    inst1;inst2;
  }
}

Cela en supposant que inst1 à inst6 ne font rien de particulier ...

[Sve@r]

McAfee me gueule dessus quand je tente de DL ton document sur 4shared.

C'est normal, t'as dû cliquer sur "pririty download" le gros bouton bleu. Là, au lieu de te filer le document, ça te file un exécutable sensé ensuite télécharger lui-même le document et te le déposer sur ton bureau (pourquoi en effet faire simple...). Et face aux exécutables inconnus, n'importe qui d'un peu sensé a un mouvement de recul et, s'il doit l'exécuter, le fait dans une machine virtuelle elle-même située de préférence sous un bon vieux Linux des familles...

Mais si tu veux télécharger son docx de façon classique, faut cliquer sur "téléchargez" juste au dessus et ensuite te créer un compte avec email et mot de passe pour ensuite pouvoir télécharger (ai-je vraiment dit "classique" ???)

Sinon donc j'ai téléchargé son docx et je le joins ici. Et mis à part cette fonction qui (pour moi) ne peut pas fonctionner (il y en a 3 autres du même acabit), son devoir est très très banal (comment insérer, supprimer, parcourir un arbre en récursif)...

Ah oui, j'oubliais, comme c'est un devoir à rendre pour aujourd'hui je pense que le topic sera périmé dès demain...

Bon, avec le 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
void F3_Rec (int x, int y)
{
    Inst1 ; Inst2 ;
 
    if (x>0 && y>0)
    {
        x= x/10 ; y= y/10 ;
        F3_Rec (x,y) ;  
        Inst3 ; Inst4 ;
    }
 
    Inst5 ; Inst6 ;
    F3_Rec (x,y);
}

on voit qu'on commence par un inst1;inst2; puis tant que les deux paramètres sont strictement positifs on les divise par 10, l'appel récursif nous fait exécuter inst1;inst2;. Une fois qu'un des deux n'est plus strictement positif on fait une boucle infinie sur inst5;inst6;inst1;inst2;

Mais après Inst6, ça rappelle F3_Rec() sans condition ce qui introduit un nouveau contexte et non pas une boucle. Alors en effet ça exécutera de nouveau Inst1 mais ça sera dans une autre pile et etc jusqu'au plantage...

[kwariz]

[...]
Mais après Inst6, ça rappelle F3_Rec() sans condition ce qui introduit un nouveau contexte et non pas une boucle. Alors en effet ça exécutera de nouveau Inst1 mais ça sera dans une autre pile et etc jusqu'au plantage...

Une autre pile ??? Il n'y a qu'une pile à ma connaissance. Effectivement la version récursive ne peut que planter avec un stackoverflow, mais a priori la version itérative ne plantera jamais en ayant le même résultat attendu. Mais bon, il s'agit d'un pseudo code c-like, pas une vraie implémentation.

Enfin, comme tu dis ce sujet est périmé et nous répondons apparemment à une question qui n'est même pas posée.

[Sve@r]

Une autre pile ??? Il n'y a qu'une pile à ma connaissance.

Je voulais dire "un autre contexte d'exécution de la fonction" mais j'avais déjà employé le mot "contexte"...

[kwariz]

Je voulais dire "un autre contexte d'exécution de la fonction" mais j'avais déjà employé le mot "contexte"...

Mais après Inst6, ça rappelle F3_Rec() sans condition ce qui introduit un nouveau contexte et non pas une boucle.

Mais du coup au premier appel récursif après le if, on tombe sur un cas de récursivité terminale et ça se transforme bien en une boucle qui dans cet exemple n'a pas de condition d'arrêt donc un boucle infinie, non ?

[Sve@r]

Mais du coup au premier appel récursif après le if, on tombe sur un cas de récursivité terminale et ça se transforme bien en une boucle qui dans cet exemple n'a pas de condition d'arrêt donc un boucle infinie, non ?

Pour qu'il y ait récursivité "terminale", il faut qu'à un moment où un autre la fonction se "termine" (par un return d'une valeur simple ou un return tout court dans le cas d'une fonction void).

Ici, il n'y a jamais aucun retour. La fonction se rappelle elle-même à l'infini...

[Médinoc]

Pour qu'il y ait récursivité "terminale", il faut qu'à un moment où un autre la fonction se "termine" (par un return d'une valeur simple ou un return tout court dans le cas d'une fonction void).

Je crois qu'on a deux notions différentes de "récursivité terminale" (et possiblement deux contextes différents).

Pour moi et kwariz, on peut parler de récursivité terminale ("tail recursion") dès que l'appel récursif est la dernière chose effectuée par la fonction ("tail call"), indépendamment de toute notion de condition d'arrêt.

[Metalman]

Il n'y a pas que ça d'étrange dans le sujet.... cf la date de rendu...

[Oui ce post n'est pas très constructif]

[kwariz]

Je crois qu'on a deux notions différentes de "récursivité terminale" (et possiblement deux contextes différents).

Pour moi et kwariz, on peut parler de récursivité terminale ("tail recursion") dès que l'appel récursif est la dernière chose effectuée par la fonction ("tail call"), indépendamment de toute notion de condition d'arrêt.

Oui c'est ça. Une fonction récursive terminale se transforme souvent aisément en version itérative avec une simple boucle.

[Obsidian]

Ah oui, j'oubliais, comme c'est un devoir à rendre pour aujourd'hui je pense que le topic sera périmé dès demain...

Surtout quand on prend connaissance des avertissements en fin de document :

• Le travail doit être remis individuellement le samedi 07/04/2013 ;
• Les programmes écrits doivent être lisibles, bien commentés et remis sous forme de listing (imprimés) ;
• Aucun retard ne sera toléré ;
• Les cas de copiage seront sévèrement sanctionnés.