Convertir une fonction récursive non terminale en une fonction récursive terminale ?

Version imprimable

Salut,
J'essaye de réaliser une fonction qui cherche un noeud dans une arbre n-aire. Pour cela j'ai fait cette fonction récursive non terminale :

Code:

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
 
void nAry::trouverUnNoeud(int val)
{
  noeud* nt = NULL;
  noeud* noeudRecherche = trouverUnNoeudPrivate(val,pRacine,nt);
  if (noeudRecherche == NULL) cout<<"Noeud non trouvé.\n";
  else	cout<<"Trouvé..."<<noeudRecherche->val<<"\n";
}
 
nAry::noeud* nAry::trouverUnNoeudPrivate(int val,noeud* pNoeud, noeud* nt)
{
 if(pNoeud == NULL) return NULL;
  cout << pNoeud->val <<" "<<val<<"\n";
 //Si le noeud est trouvé :
  if (pNoeud->val == val) 
  {
    cout<<"+++"<<pNoeud->val<<"\n";
    nt = pNoeud;
    return pNoeud;//elle retourne le noeud.
 
  }
   if (!pNoeud->fils.empty())
    for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
        //appel récursif.
       nt = trouverUnNoeudPrivate(val,*it,nt);
   return nt;
}

Mais cette fonction est non terminal, parce que même si elle trouve le noeud, elle dépile la pile des appels récursifs.

dans le main, j'appelle avec :

Code:

nAryTree.trouverUnNoeud(2);

Salut,

A quoi sert nt? Comme on n'a pas tous les détails de ton code, j'ai pris la liberté de réécrire ta fonction en l'enlevant.
Comme tu peux voir, trouverUnNoeudPrivate() se termine par l'appel récursif (dans le return), la fonction est donc bien récursive terminale.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void nAry::trouverUnNoeud(int val)
{
  noeud* noeudRecherche = trouverUnNoeudPrivate(val,pRacine);
  if (noeudRecherche == NULL) cout<<"Noeud non trouvé.\n";
  else	cout<<"Trouvé..."<<noeudRecherche->val<<"\n";
}
 
nAry::noeud* nAry::trouverUnNoeudPrivate(int val,noeud* pNoeud)
{
 if(pNoeud == NULL) return NULL;
  cout << pNoeud->val <<" "<<val<<"\n";
 //Si le noeud est trouvé :
  if (pNoeud->val == val)
  {
    cout<<"+++"<<pNoeud->val<<"\n";
    return pNoeud;//elle retourne le noeud.
 
  }
   if (!pNoeud->fils.empty())
    for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
        //appel récursif.
   return trouverUnNoeudPrivate(val,*it);
}

Hello,
Citation:
Envoyé par LandReagan
Code:

1 2 3 4 5 if (!pNoeud->fils.empty()) for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it) //appel récursif. return trouverUnNoeudPrivate(val,*it); }
Ce code me dérange : si pNoeud->fils est vide alors la fonction n'a pas de return.

A quoi sert le for ? A priori il fait juste la même chose que le if ?

Code:

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
 
//Effectivement avec ce code, quant la liste est vide, il quitte étrangement totalement la fonction !
if (!pNoeud->fils.empty())
    for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
        //appel récursif.
   return trouverUnNoeudPrivate(val,*it);
}
 
//j'ai utilisé la variable "nt" pour sauvegarder le nœud trouvé sans faire du "return" :
nAry::noeud* nAry::trouverUnNoeudPrivate(int val,noeud* pNoeud, noeud* nt)
{
 if(pNoeud == NULL) return NULL;
  cout << pNoeud->val <<" "<<val<<"\n";
 //Si le noeud est trouvé :
  if (pNoeud->val == val) 
  {
    cout<<"+++"<<pNoeud->val<<"\n";
    nt = pNoeud;
    return pNoeud;//elle retourne le noeud.
 
  }
   if (!pNoeud->fils.empty())
    for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
        //appel récursif.
       nt = trouverUnNoeudPrivate(val,*it,nt);
   return nt;
}

voilà le code complet :
nAry.h :

Code:

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
 
#include <list>
#include <map>
using namespace std;
class nAry
{
 private:
  //Les attributs privés
  struct noeud
  {
    int val;
    noeud* pPere;
    list <noeud*> fils;
  };
 
  noeud* pRacine;
 
  //Les fonctions privées
  void ajouterPrivate(int val , noeud* pNoeud);
  noeud* trouverUnNoeudPrivate(int val , noeud* pNoeud , noeud* nt);
  void affichePrivate (noeud* pNoeud);
  void supprimerArbre(noeud* pNoeud);
 
 public:
  //Les fonctions publiques
  nAry();
  ~nAry();
  noeud* init(int val);
  void genererMap(int pere , int fils);
  void ajouter(int val);
  void affiche ();
  bool estVide();
  void trouverUnNoeud(int val);
 
 
  //Les attributs publiques
  map<int, list<int> > pereFilsMap;
};

nAry.cpp :

Code:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
#include <iostream>
#include <cstdlib>
#include <map>
#include<iterator>
 
#include "nAry.h"
 
using namespace std;
nAry::nAry()
{
  pRacine = NULL;
}
 
nAry::noeud* nAry::init(int val)
{
  noeud* n = new noeud;
  n->val = val;
  n->pPere = NULL;
  return n;
}
 
nAry::~nAry()
{
  cout<<"\nDestruction de l'arbre :\n";
  supprimerArbre(pRacine);
}
 
void nAry::supprimerArbre(noeud* pNoeud)
{
  if (pNoeud != NULL)
  {
    for(list<noeud*>::iterator noeudsFilsIter = pNoeud->fils.begin() ; noeudsFilsIter != pNoeud->fils.end() ; ++noeudsFilsIter)
      	supprimerArbre(*noeudsFilsIter);
    cout<<"Suppression du noeud contenant la valeur "<<pNoeud->val<<"\n";
    delete pNoeud; 
  }
}
 
bool nAry::estVide()
{
  return pRacine == NULL;
}
 
void nAry::genererMap(int pere , int fils)
{
   pereFilsMap[pere].push_back(fils);
}
 
void nAry::ajouter(int val)
{
  ajouterPrivate(val , pRacine);
}
 
void nAry::ajouterPrivate(int val  , noeud* pNoeud)
{
  if (estVide())
    {
      pRacine = init(val);
      for(list<int>::iterator filsIter = pereFilsMap[val].begin() ; filsIter != pereFilsMap[val].end() ; ++filsIter)
      {
	noeud* noeudFils = init(*filsIter);
	pRacine->fils.push_back(noeudFils);
	noeudFils->pPere = pRacine;
	ajouterPrivate(*filsIter,noeudFils);
      }
    }
    else
    {
    if (pNoeud == NULL) pNoeud = init(val);
    if (pereFilsMap[val].empty()) return;
    for(list<int>::iterator filsIter = pereFilsMap[val].begin() ; filsIter != pereFilsMap[val].end() ; ++filsIter)
      {
	noeud* noeudFils = init(*filsIter);
	pNoeud->fils.push_back(noeudFils);
	noeudFils->pPere = pNoeud;
	ajouterPrivate(*filsIter,noeudFils);
      }
    }
}
 
void nAry::affiche ()
{
  affichePrivate(pRacine);
}
 
void nAry::affichePrivate (noeud* pNoeud)
{
  if (estVide())
  {
    cout<<"L'arbre est vide.\n";
    return;
  }
  cout << pNoeud->val <<" ";
  if (!pNoeud->fils.empty())
    for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
      affichePrivate(*it);
}
 
void nAry::trouverUnNoeud(int val)
{
  noeud* nt = NULL;
  noeud* noeudRecherche = trouverUnNoeudPrivate(val,pRacine,nt);
  if (noeudRecherche == NULL) cout<<"Noeud non trouvé.\n";
  else	cout<<"Trouvé..."<<noeudRecherche->val<<"\n";
}
 
nAry::noeud* nAry::trouverUnNoeudPrivate(int val,noeud* pNoeud, noeud* nt)
{
 if(pNoeud == NULL) return NULL;
  cout << pNoeud->val <<" "<<val<<"\n";
 //Si le noeud est trouvé :
  if (pNoeud->val == val) 
  {
    cout<<"+++"<<pNoeud->val<<"\n";
    nt = pNoeud;
    return pNoeud;//elle retourne le noeud.
 
  }
   if (!pNoeud->fils.empty())
    for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
       nt = trouverUnNoeudPrivate(val,*it,nt);
   return nt;
}

main.cpp :

Code:

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
45
46
47
48
49
 
#include <iostream>
#include <cstdlib>
#include <limits>
 
 
 
#include "nAry.cpp"
using namespace std;
int main()
{
  nAry nAryTree;
 
  cout<<"Donnez les éléments de la l'arbre n-aire \n";
  int pere;
  cin>>pere;
  int fils = 1;
  while (!cin.fail())
  {
   nAryTree.genererMap(pere,fils);
    fils++;
    cin>>pere;
  }
 
  /*Vide le flux entrant*/
  cin.clear();
  cin.ignore(numeric_limits<streamsize>::max(), '\n' );
 
  if (!nAryTree.pereFilsMap.empty()) 
  {
    map<int, list<int> >::iterator pereIter = nAryTree.pereFilsMap.begin();
    nAryTree.ajouter((*pereIter).first);
  }
 
  /* for(map<int, list<int> >::iterator pereIter = nAryTree.pereFilsMap.begin()  ; pereIter != nAryTree.pereFilsMap.end();++pereIter)
  {
    cout<<(*pereIter).first<<" => ";
    for(list<int>::iterator filsIter = nAryTree.pereFilsMap[(*pereIter).first].begin() ; filsIter != nAryTree.pereFilsMap[(*pereIter).first].end() ; ++filsIter)
      cout<<(*filsIter)<<" ";
    cout<<"\n";*/
 
  //}
  cout<<"\nAffichage en profondeur de l'arbre : \n";
  nAryTree.affiche();
  cout<<"\n";
 
  nAryTree.trouverUnNoeud(6);
  return 0;
}

Salut,

Il manque quelque chose de primordial: tu ne testes jamais la valeur de nt.
Du coup, même si tu as trouvé ton noeud, tu ne t'arrêtes pas et tu peux potentiellement (même sûrement) écraser la valeur de nt.

Code:

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
nAry::noeud* nAry::trouverUnNoeudPrivate(int val,noeud* pNoeud, noeud* nt)
{
 if(pNoeud == NULL)
 {
   return NULL;
 }
  cout << pNoeud->val <<" "<<val<<"\n";
 //Si le noeud est trouvé :
  if (pNoeud->val == val) 
  {
    cout<<"+++"<<pNoeud->val<<"\n";
    nt = pNoeud;
    return pNoeud;//elle retourne le noeud.
 
  }
   if (!pNoeud->fils.empty())
   {
      for (list<noeud*>::iterator it = pNoeud->fils.begin() ; it != pNoeud->fils.end() ; ++it)
      {  //appel récursif.
          nt = trouverUnNoeudPrivate(val,*it,nt);
          //Le petit test qui change tout: si un noeud est trouvé, on peut s'arrêter de bosser
          if (nt != NULL)
          {
               break;
          }
      }
   return nt;
}

De plus, je ne sais pas si c'est pour un exercice mais tu risques d'avoir des problèmes de piles avec les fonctions récursives si ton arbre est assez volumineux.

05/04/2015, 16h13
LandReagan

Citation:

Envoyé par Iradrille

Hello,

Ce code me dérange : si pNoeud->fils est vide alors la fonction n'a pas de return.

A quoi sert le for ? A priori il fait juste la même chose que le if ?

Salut,

Je ne sais pas, ce n'est pas mon code! J'ai juste enlevé noeud* nt de la fonction trouverUnNoeudPrivate() parce que ça ne me semblait pas utile comme paramètre, et changé un peu la fin pour que cette fonction réponde à la qualification de récursive finale.
Du coup j'ai récolté un "pouce à l'envers"... :?

Bon, tant pis... J'essayais juste d'aider.
07/04/2015, 11h22
bacelar

Aucune bonne action ne restera impunie, LandReagan. :aie::kiss:

On peut toujours faire de la récursion terminale mais c'est parfois hardcore...

La solution est pour un arbre est d'empiler dans une pile les enfants, puis de dépiler pour les examiner, qqc comme ça:
Code:

1 2 3 4 5 6 7 8 9 10 noeud* find(noeud* curr, int val, stack<noeud*>& stack) { if (curr == null) return null // pourquoi pas mais juste pour tester la racine, hein? if (curr->val == val) return curr; for (parcoursTaListeDesEnfants) stack.push(tesEnfants); if (!stack.empty()) { noeud* next = stack.pop(); return find(next, val, stack); } return null; }

07/04/2015, 14h20
foetus

Citation:

Envoyé par stendhal666

La solution est pour un arbre est d'empiler dans une pile les enfants, puis de dépiler pour les examiner, qqc comme ça

Effectivement, pour dérécursifier une fonction, on est parfois obligé d'utiliser une pile :mrgreen:

Je pense notamment au tri par tas itératif :D, où a chaque tour de boucle on empile deux morceaux (start, pivot -1) et (pivot + 1, end) ... évidemment on empile un morceau s'il a au moins 3 éléments (principe du tri par tas: on ne sait classer que 2 éléments)
07/04/2015, 14h45
stendhal666

Et au fait n'oublie pas de demander un bon niveau d'optimisation lors de la compilation, hein? sinon ton travail (et le mien) n'auront servi à rien :mrgreen:
08/04/2015, 18h59
LandReagan

Citation:

Envoyé par bacelar

Aucune bonne action ne restera impunie, LandReagan. :aie::kiss:

Merci, ça fait chaud au coeur! :mrgreen: