Pourquoi ma fonction récursive retourne true?

helloworld -  
Reivax962 Messages postés 3672 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour,
Japprend les arbres et les méthodes récursive et j'essaye de comprendre pourquoi ma méthode racineSommeEnfant() retourne vrai et non faux comme cela dois etre?

Pourtant il détecte bien que le noeud 6 n'est pas la somme des noeud 3 et 5.
Merci


import java.util.Arrays;
import java.util.Iterator;

public class Tree implements Iterable<Tree> {

	private int value;

	private Tree parent;

	private Tree[] children;

	// *******************************************************
	// CONSTRUCTEURS
	// *******************************************************
	public Tree(int v, Tree[] chd) {
		value = v;
		children = chd;

		for (Tree child : chd) {
			child.parent = this;
		}
	}

	public Tree(int v) {
		this(v, new Tree[0]);
	}

	// *******************************************************
	// GETTERS
	// *******************************************************
	public int getValue(){
		return value;
	}

	public Tree getParent(){
		return parent;
	}

	public Tree[] getChildren(){
		return children;
	}

	// *******************************************************
	// ITERATEUR
	// *******************************************************
	public Iterator<Tree> iterator(){
		return Arrays.asList(children).iterator();
	}

	public int nbrChildren(){
		return children.length;
	}

	public boolean isLeaf(){
		return children.length == 0;
	}

	// *******************************************************
	// QUESTIONS
	// *******************************************************

	public boolean racineSommeEnfant(){
		return racineSommeEnfant(this);
	}

	// verifier que la valeur de chaque noeud interne est la somme des valeurs de
	// ses enfants
	public boolean racineSommeEnfant(Tree t) {
		int somme = 0;
		for (Tree child : t.getChildren()) {
			somme += child.getValue();
		}
		for (Tree child2 : t) {
			if (somme == child2.getParent().getValue()) {
				racineSommeEnfant(child2);
			} else {
				System.out.println("here false");
				return false;
			}
		}
		System.out.println("here final");
		return true;
	}


	public static void main(String[] args) {
		Tree l5 = new Tree(1);
		Tree l6 = new Tree(6);
		Tree l7 = new Tree(3); // change from 1 to 3
		Tree l8 = new Tree(5);

		Tree t2 = new Tree(7, new Tree[] { l5, l6 });
		Tree l3 = new Tree(12);
		Tree t4 = new Tree(6, new Tree[] { l7, l8 });

		Tree t1 = new Tree(25, new Tree[] { t2, l3, t4 });
		System.out.println(t1.racineSommeEnfant());
	}
}
A voir également:

1 réponse

Reivax962 Messages postés 3672 Date d'inscription   Statut Membre Dernière intervention   1 011
 
Bonjour,

Le problème, c'est que tu n'utilises jamais la valeur de retour de l'appel récursif à ta fonction racineSommeEnfant. Le
return
ne se propage pas tout seul dans la pile d'appels.
Du coup, ta fonction peut bien renvoyer False, l'exécution de l'appelant continue comme si de rien n'était...
Pour aller au plus simple, je modifierais ta boucle for comme suit :
for (Tree child2 : t) {
    if (somme != child2.getParent().getValue() || !racineSommeEnfant(child2))
    {
        System.out.println("here false");
        return false;
    }
}

Xavier
0
helloworld
 
Cela fonctionne merci ! mais j'ai du mal à saisir le problème...
0
Reivax962 Messages postés 3672 Date d'inscription   Statut Membre Dernière intervention   1 011 > helloworld
 
Peut-être que si j'avais écrit mon code comme ça tu comprendrais mieux :
for (Tree child2 : t) {
    if (somme == child2.getParent().getValue()) {
        boolean resultatEnfants = racineSommeEnfant(child2);
        if (!resultatEnfants) {
            return false;
        }
    } else {
        System.out.println("here false");
        return false;
    }
}

Ça fait exactement la même chose que mon code, mais en se rapprochant plus du tien comme ça tu peux voir la différence.
0