Publicité
+ Répondre à la discussion
Page 1 sur 3 123 DernièreDernière
Affichage des résultats 1 à 20 sur 41
  1. #1
    Membre habitué
    Profil pro Yassine Chaouche
    Développeur informatique
    Inscrit en
    janvier 2003
    Messages
    170
    Détails du profil
    Informations personnelles :
    Nom : Yassine Chaouche
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Distribution

    Informations forums :
    Inscription : janvier 2003
    Messages : 170
    Points : 130
    Points
    130

    Par défaut Iteration VS recursivité

    Salut A tous,

    Pourquoi certains n'aiment pas utiliser la recursivite dans leur programmes ? est-ce par rapport au temps d'execution ?

    Merci,a++;

  2. #2
    Membre actif Avatar de Choupi
    Inscrit en
    janvier 2003
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : janvier 2003
    Messages : 223
    Points : 189
    Points
    189

    Par défaut

    Le choix entre recursivite ou iteration depend de la vision qu'on a du prog ...Et pas toujours de l'efficacite...
    Par exemple le parcours infixe d'un arbre binaire est à mon avis tres clair d'un point de vue recursif ... Visiter la racine le sous arbre gauche, le sous arbre droit ... C'est limpide. Par contre pour la recherche d'un element dans un arbre ... les deux se valent :

    Code :
    1
    2
    3
    RC (dans x,valeur k) si clef racine = k  alors retourner x sinon 
    si k est < clef(x) 
    alors RC(fils gauche(x),k) sinon RC(filsdroit(x),k)
    Code :
    1
    2
    3
    IT(x,k) tant que x differ de la racine et k differ de clef(x) alors
    faire si k < clef(x) alors x = FG(x) sinon x = FD(x)
    retourner x
    Je pense que l'iteration est plus eficace ... je me trompe ? mais le choix depend bien de la vision qu'on a du probleme... Ici je prend la recursivite.

    C'est existanciel comme question ! Moi perso je prefere la recursivite car ca me semble simple et toujours clair.

    Freif'

  3. #3
    Membre habitué
    Profil pro Yassine Chaouche
    Développeur informatique
    Inscrit en
    janvier 2003
    Messages
    170
    Détails du profil
    Informations personnelles :
    Nom : Yassine Chaouche
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Distribution

    Informations forums :
    Inscription : janvier 2003
    Messages : 170
    Points : 130
    Points
    130

    Par défaut

    c'est clair que la recursivite est plus limpide comme tu dis,mais si tu dois rappeler une fonction en lui passant des paramétres,je pense que ca prends plus de temps qu'en faisant un iteration.En plus,si c'est une fonction qui renvoie une valeur,tu peux aussi avoir des problèmes au niveau de l'execution.C'est a dire si tu fais
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    int fonction(parametres){
       if(che pas quoi) 
          return valeur;
       for(une boucle){
         blablabla;
         fonction(parametres_modifies);//recursivite
       }
       //gros bloc de code
       blablablabla;
    }
    Tu pense que si le test if marche,alors la fonction renvoi la valeur et puis basta,c'est censé s'arreté,en fait non,car il y a les precedents appeles a la fonction qui sont toujours en attente,et elles vont poursuivre le reste de la porcedure,le gros bloc de code qui a en bas...Il faut fair attention a ce genre de boullette.

    Salut,a++;

  4. #4
    Membre actif Avatar de Choupi
    Inscrit en
    janvier 2003
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : janvier 2003
    Messages : 223
    Points : 189
    Points
    189

    Par défaut

    Euh :

    L'efficacite c'est relatif ... Ca depend du type de calcul ...
    Dans ton exemple, dés que le test est vrai on retourne la valeur, on execute pas le blablabla ... de la fonction en cours... mais des autres...
    Pourquoi place ce blablabla dans la fonction si on en a pas besoin ?
    Citation Envoyé par freifelder
    Le choix entre recursivite ou iteration depend de la vision qu'on a du prog ....
    En fait j'ai pas trop compris ton probleme ...
    Et ca s'applique a quoi ?

    Freif'

  5. #5
    Membre habitué
    Profil pro Yassine Chaouche
    Développeur informatique
    Inscrit en
    janvier 2003
    Messages
    170
    Détails du profil
    Informations personnelles :
    Nom : Yassine Chaouche
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Distribution

    Informations forums :
    Inscription : janvier 2003
    Messages : 170
    Points : 130
    Points
    130

    Par défaut

    Salut,

    Si si,on fait le blabla a tous les coups,puisque le if ne contient qu'une seul instruction(c'est pourquoi je n'ai pas mis d'accolades).en fait c'est le test d'arret.tout comme le gors bloc de code qui est tout en bas,il sera execute par l'appele courant.

    La question n'est pas posé pour un programme precis,c'est just une question de methodologie et de choix algorithmique.Mais si tu veux savoir,j'ai posé cette question parceque je veux gagner en temps d'execution.

    Salut,a++:

  6. #6
    Membre confirmé

    Inscrit en
    juin 2002
    Messages
    97
    Détails du profil
    Informations forums :
    Inscription : juin 2002
    Messages : 97
    Points : 271
    Points
    271

    Par défaut

    La récursivité...
    -Plus dur à appréhender si l'appel récursif n'est pas simplement en début/fin de fonction.
    -Plus lent. Le mécansime d'appel de fonction est lourd.
    -Plus encombrant. Une forte imbrication peut saturer la pile.
    -Plus puissant. Peut imbriquer un nombre indéterminé de boucles par exemple.
    "J'ai toujours rêvé d'un ordinateur qui soit aussi facile à utiliser qu'un téléphone. Mon rêve s'est réalisé : je ne sais plus comment utiliser mon téléphone."-Bjarne Stroustrup
    www.stroustrup.com

  7. #7
    vic
    vic est déconnecté
    Membre éprouvé
    Inscrit en
    août 2002
    Messages
    430
    Détails du profil
    Informations forums :
    Inscription : août 2002
    Messages : 430
    Points : 415
    Points
    415

    Par défaut

    C'est parfois la facilité qui conduit à utiliser la récursivité alors qu'un peu de réflexion permet de trouver une solution plus simple.
    Exemple le suite de fibonacci : méthode récursive lourde et lente ou bien formule directe très rapide (une dizaine d'opérations) qui fait intervenir le nombre d'or.
    C'est juste un exemple :)

  8. #8
    Membre du Club
    Inscrit en
    mars 2002
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 92
    Points : 65
    Points
    65

    Par défaut

    On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??

    Et est-ce vraiment utile de supprimer la recursité pour parcourir un arbre dont la profondeur est en génrale égale à 20??
    Zero
    My site : http://blog.lecacheur.com
    GWhere project : http://www.gwhere.org
    Debian Addict site : http://www.debianaddict.org

  9. #9
    Membre habitué
    Profil pro Yassine Chaouche
    Développeur informatique
    Inscrit en
    janvier 2003
    Messages
    170
    Détails du profil
    Informations personnelles :
    Nom : Yassine Chaouche
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Distribution

    Informations forums :
    Inscription : janvier 2003
    Messages : 170
    Points : 130
    Points
    130

    Par défaut

    Tu fais comment pour le fibonachi sans recursivite si ce n'est d'une maniere iterative ?

  10. #10
    vic
    vic est déconnecté
    Membre éprouvé
    Inscrit en
    août 2002
    Messages
    430
    Détails du profil
    Informations forums :
    Inscription : août 2002
    Messages : 430
    Points : 415
    Points
    415

    Par défaut

    Je pose le nombre d'or Phi = ( 1+sqrt(5) ) / 2

    Alors F(n) = ( Phi^n - (-Phi)^-n ) / sqrt(5)
    Qu'on peut simplifier en F(n) = round( Phi^n / sqrt(5) )

    Comme on pouvait s'en douter ca se démontre facilement par récurence en remarquant que Phi est racine de x^2=x+1 et donc Phi^n = Phi^(n-1) + Phi^(n-2) ce qui revient à la définition de la suite de Fibonacci.

    vic

  11. #11
    Membre confirmé

    Inscrit en
    juin 2002
    Messages
    97
    Détails du profil
    Informations forums :
    Inscription : juin 2002
    Messages : 97
    Points : 271
    Points
    271

    Par défaut

    Citation Envoyé par Zero
    On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??
    Peut-être...
    -Un tableau pour contenir tous les futurs pointeurs de noeud, ainsi qu'un indice du traitement en cours pour celui-ci.
    -Une boucle infinie pour parcourir le tableau, dans laquelle:
    --Faire les traitements dans l'ordre, avec un switch pour les séparer.
    --Avancer l'indice en descendant dans l'arbre, le reculer en remontant.
    --Sortir si le bon noeud est atteint/tous les noeuds sont traités.

    Donc, il serait possible de reconstituer le fonctionnement d'un nombre indéterminé de boucles imbriquées...
    Le tableau devrait être dynamique, ou d'une taille arbitrairement suffisante.

    Exemple (non testé ):
    La structure
    Code :
    1
    2
    3
    4
    5
    6
    #define NAry 3
     
    struct node{
    	struct node* sub[NAry]; //noeuds descendants
    };
    typedef struct node node;
    Le parcours récursif
    Code :
    1
    2
    3
    4
    5
    void WalkTree(node* root){
    	printf("%p\n",root);
    	for(int i=0 ; i!=NAry ; ++i)
    		WalkTree(root->sub[i]);
    }
    Le parcours itératif
    Code :
    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
    //permet de donner des noms aux étapes de traitement.
    //trucage: le n° d'étape est aussi l'indice du pointeur à suivre.
    enum steps {first=-1, display=first, /*n°s 0 à NAry-1 réservés*/ back=NAry+1};
    typedef enum steps steps;
     
    struct NodeAndStep{
    	node* nd; //noeud à opérer
    	int step; //étape de l'opération
    };
    typedef struct NodeAndStep NodeAndStep;
     
    void WalkTree(node* root){
    	int depth=0; //profondeur atteinte dans l'arbre (et le tableau)
    	struct NodeAndStep nas[512]; //arbitrairement suffisant
    	nas[0].nd  = root ; //noeud de départ
    	nas[0].step= first; //étape de départ
     
    	do{
    		node       * currnode=  nas[depth  ].nd  ;
    		steps      * pstep   = &nas[depth  ].step;
    		NodeAndStep* nextnas = &nas[depth+1]     ;
     
    		switch(*pstep)
    		{
    		case display:
    			++(*pstep); //passer à l'étape suivante
    			printf("%p\n",currnode);
    			continue; //repartir de do
     
    		default: //descendre le sous-noeud de même n°: 0,1 et 2 dans cet exemple
    			++(*pstep);
    			nextnas->nd  = currnode->sub[*pstep]; //node à 'suivre'
    			nextnas->step= -1; //à traiter depuis le début
    			++depth; //descendre dans l'arbre
     
    			continue;
    		case back: //tous les sous-noeuds parcourus, remonter
    			if(depth==0) //si rien à remonter
    				break; //quitter le switch, et la boucle
    			else{
    				--depth; //remonter
    				continue;
    			}
    		}// switch
    	}while(0);
    }
    Je vous laisse juge de l'intérêt...
    "J'ai toujours rêvé d'un ordinateur qui soit aussi facile à utiliser qu'un téléphone. Mon rêve s'est réalisé : je ne sais plus comment utiliser mon téléphone."-Bjarne Stroustrup
    www.stroustrup.com

  12. #12
    Membre à l'essai
    Profil pro
    Inscrit en
    octobre 2002
    Messages
    20
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : Luxembourg

    Informations forums :
    Inscription : octobre 2002
    Messages : 20
    Points : 21
    Points
    21

    Par défaut

    Salut,

    La récursivité est bien pour de petits exemples (ex : calculer la factorielle d'un nombre plus ou moins petit).
    De même pour de petits arbres ça va bien

    Si vous avez un arbre de 20000 noeuds et que celui-ci n'est pas équilibré (cf : arbre AVL), dans le pire des cas, vous pourriez avoir une "liste". Pour faire une recherche, insertion ou suppression ca risque de prendre du temps...

    En plus avec la récursivité, il faut bien concevoir l'algo pour être certain qu'il s'arrête. Avec des boucles du type : for, while() {...} ou do { ... }while(); il est assez facile de vérifier !

    De plus, il est évident que tout ce que l'on peut faire en récursivité est possible sous forme itérative (sauf si les profs interdisent l'itération )...

    Donc voilà, à vous de trancher !

    ++

    Ken

  13. #13
    gl
    gl est déconnecté
    Rédacteur/Modérateur

    Homme Profil pro
    Inscrit en
    juin 2002
    Messages
    2 095
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Isère (Rhône Alpes)

    Informations forums :
    Inscription : juin 2002
    Messages : 2 095
    Points : 3 953
    Points
    3 953

    Par défaut

    Je ne vois pas l'interet d'un debat recursivite contre iterativte.
    A part les problemes deja evoque de saturation de pile et de temps d'execution, la recursivite ne pose de gros probleme et peut donc etre employe dans tout les autres cas.
    Apres le choix est fait au cas par cas en fonction de la facilite, de l'aisance du developpeur, etc.
    En bref il n'y a pas de regle generale pour l'utilisation ou non de la recursivite

  14. #14
    Membre habitué
    Profil pro Yassine Chaouche
    Développeur informatique
    Inscrit en
    janvier 2003
    Messages
    170
    Détails du profil
    Informations personnelles :
    Nom : Yassine Chaouche
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Distribution

    Informations forums :
    Inscription : janvier 2003
    Messages : 170
    Points : 130
    Points
    130

    Par défaut

    Salut,

    Merci a tous pour vos precieuses interventions.

    Connaissez vous le langage LISP ?(Emacs est fait avec lisp).C'est un langage ou la majortié des alogorithmes(je crois) sont recursifs,c'est un langage qui introduit la programmation fonctionelle(humm...je crois ).Pensez vous que certains langages soient plus appropriés à l'utilisation de la recursivité que d'autres ? genre le traitement se fait differament ou je ne sais pas moi...



    salut,a++;

  15. #15
    gl
    gl est déconnecté
    Rédacteur/Modérateur

    Homme Profil pro
    Inscrit en
    juin 2002
    Messages
    2 095
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Isère (Rhône Alpes)

    Informations forums :
    Inscription : juin 2002
    Messages : 2 095
    Points : 3 953
    Points
    3 953

    Par défaut

    Effectivement le LISP emploie beaucoup la recursivite, ca vient en grande partie de la structure et de l'esprit du langage ou on travaille essentiellement sur les listes (LISP pour LISt Processing), du coup l'emploi de la recursivite est plus nturel.

  16. #16
    Membre du Club
    Inscrit en
    mars 2002
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 92
    Points : 65
    Points
    65

    Par défaut

    Citation Envoyé par Musaran
    Citation Envoyé par Zero
    On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??
    Peut-être...
    [...]
    Je vous laisse juge de l'intérêt...
    Merci, c'est vrai que dans mon cas ça ne sert peut-être pas, vu que le niveau de recursivité est rarement important. Mais il doit pouvoir être très adapté à d'autres modèles de données.
    Zero
    My site : http://blog.lecacheur.com
    GWhere project : http://www.gwhere.org
    Debian Addict site : http://www.debianaddict.org

  17. #17
    Candidat au titre de Membre du Club
    Inscrit en
    mai 2002
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : mai 2002
    Messages : 11
    Points : 12
    Points
    12

    Par défaut

    Citation Envoyé par Zero
    On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??

    Et est-ce vraiment utile de supprimer la recursité pour parcourir un arbre dont la profondeur est en génrale égale à 20??
    je pense qu'on peut utilser la récursivité mais indirectement
    en faite en n'utilse que la partie interessant de la recusrsivité c'est ça pile
    alors on va pas faire des sauvgarde de contaxte, ni des jmp!ni des apelles recursive

    mais une petite pile (très inferieurs a la pile originale), ou on arrangera les adresses des noues restant a parcourer ;-)

    d'une façon générale, je pense que n'importe quelle fonction récursive simple (non double ou autre chose ) peut ce ramener a une foction itérative avec une pile

  18. #18
    Membre confirmé

    Inscrit en
    juin 2002
    Messages
    97
    Détails du profil
    Informations forums :
    Inscription : juin 2002
    Messages : 97
    Points : 271
    Points
    271

    Par défaut

    Ce que fait mon exemple (sauf que je gère pas sa taille dynamiquement).

    Pour une fonction récursive double, il faudrait simplement y créer une étape supplémentaire et éventuellement un tableau supplémentaire pour stocker une valeur intermédiaire.

    C'est un problème se langage très intéressant.
    "J'ai toujours rêvé d'un ordinateur qui soit aussi facile à utiliser qu'un téléphone. Mon rêve s'est réalisé : je ne sais plus comment utiliser mon téléphone."-Bjarne Stroustrup
    www.stroustrup.com

  19. #19
    Futur Membre du Club
    Inscrit en
    juillet 2005
    Messages
    24
    Détails du profil
    Informations forums :
    Inscription : juillet 2005
    Messages : 24
    Points : 15
    Points
    15

    Par défaut

    slt
    Pour repondre au pseudo dilem entre itération vs récursivité, je dirais que cela dépend de ton programme, enfin ton algorithme. Si tu calcules sa complexité, tu verras ce qu'il convient de choisir, mais cela dépend aussi de la représentation de tes données.

    Et n'oublies pas Java bien et C tant mieux

  20. #20
    Inactif
    Inscrit en
    décembre 2002
    Messages
    534
    Détails du profil
    Informations forums :
    Inscription : décembre 2002
    Messages : 534
    Points : 317
    Points
    317

    Par défaut

    Bonsoir,

    Je pense que le problème de la récursivité dans le domaine de l' algorithmique, ne sait vraimment posé, qu' à l' époque du MS-DOS.

    La programmation 32 bits permet l' usage d' une "pile" ou encore "stack", à de nombreuses applications, de tourner selon les principes de la récursivité.

    Le véritable problème reste "comment convertir un algorithme récursif en algorithme itératif" , et comment convertir "un algorithme itératif en algorithme récursif".

    Mais il ne s' agit là que d' un problème théorique, dont la plupart des développeurs se moquent.

    Cordialement.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •