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

**blackbird1** · 04/04/2015, 03h11

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 :

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
 
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 :

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

nAryTree.trouverUnNoeud(2);

**LandReagan** · 04/04/2015, 08h19

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 :

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
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);
}

**Iradrille** · 04/04/2015, 10h54

Hello,

Envoyé par LandReagan

Code :

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

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 ?

**blackbird1** · 04/04/2015, 18h34

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
 
//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 :

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
 
#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 :

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
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 :

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
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;
}

**darkman19320** · 05/04/2015, 12h05

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 :

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
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.

**LandReagan** · 05/04/2015, 16h13

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.

**bacelar** · 07/04/2015, 11h22

Aucune bonne action ne restera impunie, LandReagan.

**stendhal666** · 07/04/2015, 13h15

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 :

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

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;
}

**foetus** · 07/04/2015, 14h20

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

Je pense notamment au tri par tas itératif

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