Recursivité help

Discussion dans 'Web, design' créé par Tekura, 12 Décembre 2007.

Statut de la discussion:
Fermée.
  1. Offline
    Tekura Elite
    Salut, j'ai un gros problème. J'ai beau me démerder en java et algo. Dès qu'il y a du recursif je suis perdu Oo

    Y a rien à faire, j'arrive pas à penser de manière récursive (8 mois que j'essai).

    Avez-vous un truc ?, des techniques, des conseils pour m'aider à comprendre :-(

    Si vous connaissez des bons sites( ou livres ) qui expliquent vraiment bien les étapes pour résoudre un problème récursif, je suis preneur.

    Merci d'avance ;)
    Tekura, 12 Décembre 2007
    #1
  2. Offline
    Froggy fake geek
    en fait le truc ... c'est de pas essayer de comprendre. :)

    tu résouds le problème pour le cas initial (en t'asssurant que si on sait résoudre un cas, on peut résoudre le cas"+1") et tu réappel ta fonction pour le cas suivant ;)

    le fait de suivre chaque itération devient très vite un gros gros casse tête donc vaut mieux pas essayer de comprendre (au début du moins).
    Froggy, 12 Décembre 2007
    #2
  3. Offline
    Tekura Elite
    le cas initial, j'ai pas trop de soucis, mais c'est précisément là où le problème se situe "s'assurer le cas +1".

    (pourrais-tu illustrer par un exemple stp)

    le cas basic du factorielle je l'ai piger, mais dès qu'il s'agit de faire une recherche ou une methode ds un arbre binaire... je bloque totallement :-(
    Tekura, 12 Décembre 2007
    #3
  4. Offline
    ozilrit Touriste
    D'un autre côté, quel est l'utilité de cet arbre ? Est-ce un cas unique ?
    ozilrit, 12 Décembre 2007
    #4
  5. Offline
    Tekura Elite
    C'est surtout pédagoque:p.

    En gros c'était des methode du genre, ajouter quelque chose a la bonne place ds un arbre, supprimer, etc

    Faire des lecture In-Ordre, Pré-ordre, etc

    Mais les arbres sont juste des exemples, c'est ds 90% des cas, quand y a du recursif a faire, suis completement paumer :-(
    Tekura, 12 Décembre 2007
    #5
  6. Offline
    ozilrit Touriste
    Sous quel forme se présente ton arbre ?
    ozilrit, 12 Décembre 2007
    #6
  7. Offline
    La Poubelle Elite
    Une fonction récursive doit s'adapter à un cas précis. D'où l'importatnce de l'analyse.

    Avec une question aussi vaguer, il est
    impossible de ne pas te dire d'aneries
    La Poubelle, 12 Décembre 2007
    #7
  8. Offline
    Tekura Elite
    ce sont des arbre binaire de recherche (String).

    l'arbre est composer d'un noeud pour la racine et de sous arbres gauche et droit. (Je suis en premier a l'IPL, si tu connais le programme).

    et les methode demander sont, getProfondeur(), getNombreDelément(), plusieur toString (inOrdre, préOrdre, postOrdre), estFeuille(), estEquilibré(), etc...
    Tekura, 12 Décembre 2007
    #8
  9. Offline
    Tekura Elite
    C'est pour cela que j'aimerais avoir une "technique d'approche" parce que c'est vraiment mon point noir :'(
    Tekura, 12 Décembre 2007
    #9
  10. Offline
    Ahava Revenant
    Essaie de voir les choses ainsi :


    T'as un arbre, sur lequel tu veux faire des choses. Dis-toi que le cas "initial", c'est "ce que je fais comme traitement quand je rencontre un noeud".

    Donc si tu veux compter le nombre de noeuds contenant une chaine, ca serait, imaginons : "cpt++ ;".

    Ensuite tu te dis que chaque noeud peut avoir des enfants, donc tu vas tester chacun d'entre eux aussi !

    Donc en gros ca donne, si je me trompe pas (il est tard), dans la classe de ton arbre par exemple :
    Code:
    private int getNbElems(Noeud n){
        int cpt = 0 ;
        if ( n.getElement() != null ) cpt++ ; // je compte la chaine courante
        if ( n.getFilsGauche() != null ) cpt = cpt + getNbElems(n.getFilsGauche()); // j'appelle la méthode sur le fils gauche
        if ( n.getFilsDroit() != null ) cpt = cpt + getNbElems(n.getFilsDroit()); // pareil mais sur le fils droit
        return cpt ; 
    
    Et tu fais une autre méthode, publique cette fois, qui va etre appellée quand tu instanciera ta classe Arbre, par ex :
    Code:
    public int getNbChaines (){
    
        return this.getNbElems( this.racine ); // si tu as un attribut racine hein :p
    }
    
    Si tu procede ainsi je pense que tu peux arriver à tout faire :) Donc décompose chaque étape pour un élément, et ses enfants s'il en as, et le tour est joué :)

    Bien sur ce code, je viens de le taper donc ca compilera surement pas, et faut adapter ca, évidemment...

    Perso j'adore la récusivité, je trouve ca archi-puissant si bien utilisé ! Donc tu es bien tombé là :p


    ps : pre-ordre, c'est quoi ? C'est pas l'ordre dans lequel lire l'arbre ? genre gauche-courant-droit par ex ? Bah dans ton traitement tu fais d'abord le comptage du fils gauche au lieu de faire d'abord l'élément courant, etc. !

    J'espere que ca t'as aidé :)
    Ahava, 12 Décembre 2007
    #10
  11. Offline
    ozilrit Touriste
    Alors je ne peux aider mais voici un peu de lecture.
    ozilrit, 12 Décembre 2007
    #11
  12. Offline
    Tekura Elite
    merci, je vois un peu plus clair, vais essayer de bosser un peu tout ca :)

    Je connais un gars qui est pareil :p perso je trouve qu'il faut etre taré pour aimer ca :D
    Tekura, 13 Décembre 2007
    #12
  13. Offline
    La Poubelle Elite
    Mouais, tout dépend les besoins et les applications.

    Cette méthode de programmation ne doit pas être utilisé à tort et à travers.
    La Poubelle, 13 Décembre 2007
    #13
  14. Offline
    Ahava Revenant
    C'est certain ça ! Perso à part à l'école, j'ai pas encore eu l'occasion de faire de la récursivité depuis :p
    Ahava, 13 Décembre 2007
    #14
  15. Offline
    kawash Touriste
    La récursivité je trouve ça avantageux au niveau lisibilité/simplification du code, mais mon dieu qu'es ce que ça bouffe en ressources :p
    kawash, 16 Décembre 2007
    #15
  16. Offline
    La Poubelle Elite
    De temps en temps :p

    La dernière fois, c'etait une procédure stocké qui appelait des fonctions sql de façon recursive :p
    La Poubelle, 16 Décembre 2007
    #16
Statut de la discussion:
Fermée.