Discussion :

[tamerla]

Salut !
j'ai un probleme avec le principe de la récursion, ca me parait pas du tout naturel dans ma tete mais il se trouve que j'en ai besoin, j'aimerai donc que vous m'aidiez a comprendre ! J'implémente un arbre binaire de recherche et je cherche a compter le nombre de noeuds :

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
 
public class ArbreBinRech {
   private int val;
   private ArbreBinRech p;
   private ArbreBinRech g;
 
  public ArbreBinRech(int val) {
      this.val = val;
   }
 
   public void ajout(int e) {
      if(this == null) return;
      if(e < this.val && this.p != null) {
         this.p.ajout(e);
      }
      ArbreBinRech a = new ArbreBinRech(e);
      this.setP(a);
      if(e > this.val && this.g != null) {
         this.g.ajout(e);
      }
      this.setG(a);
   }
 
   public int nbNoeuds() {
      if(this == null) return 0;
      else if(this.p == null) return 1;
      else if(this.g == null) return 1;
      return this.p.nbNoeuds() + this.g.nbNoeuds() + 1;
   }

il y a ci dessus ce que j'ai fait: j'ai d'abord une fonction ajout en récursif qui je crois , marche, mais nbNoeuds() ne fonctionnent pas très bien, je n'ai pas toujoursle bon résultat. J'avoue que je l'ai fait un peu au pif car je ne comprends pas completement le principe de la récursion !
merci de votre aide

[tchize_]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
   public void ajout(int e) {
      if(this == null) return;
      if(e < this.val && this.p != null) {
         this.p.ajout(e);
      }
      ArbreBinRech a = new ArbreBinRech(e);
      this.setP(a);
      if(e > this.val && this.g != null) {
         this.g.ajout(e);
      }
      this.setG(a);
   }

Cette méthode m'a l'air suspecte.
1) D'abord, tu regarde si ça doit aller a gauche (p) et qu'il y a un arbre à gauche (p!=null). Si oui, tu ajoute ensuite à gauche (p.ajout).
2) Ensuite, d'office, tu remplace l'arbre gauche par e (this.setP(a))
3) Ensuite tu test si ça doit aller à droite et si la droite est non nulle (g!=null). Si oui, tu fais de la récursivité
4) Ensuite, d'office, tu ajoute le même arbre à droite.

Conclusion? Après chaque ajout, tes arbre a gauche et droite seront identique. De plus, parfois, en supplément, tu fera une récursivité.

Revois ta logique, elle est incorrecte. 2 et 4 ne devraient pas systématiquement arriver. Tu n'a rien prévu pour les cas:
à gauche mais l'arbre gauche n'existe pas encore
à droite mais l'arbre droite n'existe pas encore
valeur identique.

[tamerla]

Merci de ta réponse ,en effet je ne comprends rien a la récursivité, je sais que ces deux méthodes sont approximatives voire fausses , c'est pour ça que je demande quelques explications ici à ce sujet afin de comprendre enfin l'idée !
et j'ai pas compris ce que tu m'as dit car quand je teste la méthode (meme si elle est fausse) je n'ai pas des arbres identiques a gauche et a droite.
merci de votre aide ~

[-Dici-]

En fait la récursivité est assez naturelle (pas toujours, mais souvent) mais il faut penser différemment que quand on code en itératif. En itératif, on doit se demander exactement comment on fait la chose, étape par étape. En récursif, il est souvent très difficile d'imaginer de tête le résultat d'un appel récursif, par contre le code est souvent très court.

Pour écrire un algo récursif, il faut se demander comment on peut réduire le problème à un ou plusieurs problèmes strictement plus petits, et comment déduire de la solution de ces problèmes celle du problème initial. Il faut aussi définir un cas d'arrêt ou plusieurs, c'est-à-dire des cas où le problème n'est plus décomposable et peut être résolu sans appel récursif. C'est un peu comme une relation de récurrence en maths, avec terme initial ("cas d'arrêt").

Par exemple pour ton comptage de noeuds c'est très simple : le nombre de noeuds d'un arbre binaire et égal à la somme du nombre de noeuds du sous-arbre gauche et du sous-arbre droit plus un (pour la racine). Ca donne le code suivant :

Code :

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

1
2
3
4
5
6
 
public int countNodes() {
      int ng = this.g == null ? 0 : this.g.countNodes();
      int nd = this.d == null ? 0 : this.d.countNodes();
      return ng + nd + 1;
}

Applique cette méthodologie à ton autre méthode. PS : this == null est impossible puisque si c'était le cas on n'aurait pas pu exécuter la méthode (NullPointerException)...

[tchize_]

Merci de ta réponse ,en effet je ne comprends rien a la récursivité, je sais que ces deux méthodes sont approximatives voire fausses , c'est pour ça que je demande quelques explications ici à ce sujet afin de comprendre enfin l'idée !
et j'ai pas compris ce que tu m'as dit car quand je teste la méthode (meme si elle est fausse) je n'ai pas des arbres identiques a gauche et a droite.
merci de votre aide ~

pour répondre à ton problème, il faut penser logique dans ta méthode. Quels sont les cas possibles pour ajouter? Traiter tous les cas dans des ifs séparés.
en pseudo code ça donne

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
 
 
si e < noeud actuel
   // il faut ajouter à gauche
   si un noeud existe à gauche
     faire gauche.ajout(e)
   sinon
     faire gauche = nouveau noeud(e)
sinon, si e > noeud actuel
   // il faut ajouter à droite
   si un noeud existe à droite 
      faire droite.ajout(e)
   sinon
      faire droite = nouveau noeud(e)
sinon
   // cas restant: e = noeud actuel
   // que faire? Quelle stratégie veux-tu
   // ton arbre dois-t-il supporter les doublon
   // lancer un erreur?
   // ignorer?

[tamerla]

OK merci beaucoup pour vos réponses je comprends un peu mieux le principe. J'ai jamais vraiment fait de récursion avant donc c'est un peu nouveau !
-dici- : merci pour ta méthode ! (j'étais pas loin ) mais c'est la premiere fois que je vois cette facon d'écrire un code, qu'est ce que ca veut dire avec des if et des else ?
tchize_ : ok j'ai bien compris je pense, ma méthode était donc pas si mal sauf que j'avais oublié des cas.

Merci de votre aide !

[-Dici-]

L'instruction

Code :

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

int a = test ? value0 : value1;

équivaut à

Code :

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

1
2
3
4
5
int a;
if (test)
    a = value0;
else
    a = value1;