Methode recursive

Fermé
helloworld - 3 mars 2018 à 11:01
KX Messages postés 16755 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 12 février 2025 - 4 mars 2018 à 13:21
Bonjour,

J'ai du mal avec la recursivité..

J'aimerai recherche un element dans une liste chainée avec la méthode contain() mais de façon récursive.
Cependant ma méthode ne fonctionne pas.. Que n'ai-je pas compris ?

	public class Liste {

	private Node first;
	
	public Liste() {
		this.first=null;
	}
	
	
	
		public boolean contain(E element){
			if (first == null)
				return false;
			if (first.next == null)
				return false;
			if (first.next.element == element)
				return true;
			return contain(first.next.element);
	}
	
	
	

	private class Node{
		private E element;
		private Node next;

		public Node(E element, Node next){
			this.element = element;
			this.next = next;
		}

	}





1 réponse

KX Messages postés 16755 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 12 février 2025 3 020
3 mars 2018 à 12:54
Bonjour,

Tu manipules un type E, mais où est-il déclaré ? Parce que s'il est bien fait ça devrait être un paramètre de Liste et Node, or ici ce n'est pas le cas, donc c'est bizarre...

Remarque : pourquoi avoir fait Node une classe interne de Liste ? Dans ton code actuel ça ne se justifie pas.
Il vaudrait mieux soit la sortir de la classe, soit la déclarer static.

De plus, E est un objet, donc faire des comparaisons avec == est généralement faux, il faudrait plutôt utiliser la méthode equals de E, en vérifiant d'abord les cas où l'objet peut être null.

Quant à la récursivité, elle est effectivement mal utilisée car tu rappelles contains() sur le même objet, donc first reste le même d'un appel sur l'autre alors qu'il faudrait que tu te déplaces d'un Node à l'autre, donc la méthode contains serait plus pertinente sur la classe Node que sur la classe Liste.

Exemple (non testé)

public class Liste<E> {
    private Node<E> first;

    public boolean contains(E value) {
        if (first == null)
            return false;
        return first.contains(value);
    }
}

class Node<E> {
    private E element;
    private Node<E> next;

    public boolean contains(E value) {
        if (element == null)
            return value == null;
        if (element.equals(value))
            return true;
        if (next == null)
            return false;
        return next.contains(value);
    }
}
0
Merci, par contre y a t'il un moyen d'avancer d'un noeud dans la classe méthode contains tout en restant dans la classe Liste ?
0
KX Messages postés 16755 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 12 février 2025 3 020 > helloworld
4 mars 2018 à 13:21
Ça n'a pas vraiment de sens de rester dans la classe Liste. La récursivité consiste à passer d'un élément à un autre, or l'objet liste est unique donc on ne peut pas itérer dessus.
Les seuls objets multiples sur lesquels on peut appliquer la récursivité ce sont les Node.

Concrètement, la vraie liste ce sont les objets Node connectés entre eux, qui contiennent les valeurs.
La classe Liste est un raccourci (très utile) vers le premier Node mais en réalité on pourrait s'en passer et ne travailler que sur les Node.

Exemple : je supprime la classe Liste et je renomme la classe Node en Liste2 (le code est le même)

public class Liste2<E> {
    private E element;
    private Liste2<E> next;

    public boolean contains(E value) {
        if (element == null)
            return value == null;
        if (element.equals(value))
            return true;
        if (next == null)
            return false;
        return next.contains(value);
    }
}

C'est donc bien sur les Node (ou Liste2) qu'il faut mettre la récursivité.
La classe Liste est utile pour l’encapsulation des données afin d'éviter que l'utilisateur puisse modifier directement les Node, mais c'est juste une surcouche.
D'un point de vue algorithmique, tout repose sur les Node, donc c'est là que doit se trouver ton code.
0