récursivité, itération
Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

récursivité, itération



  1. #1
    invite1acecc80

    récursivité, itération


    ------

    Bonjour,

    Je me pose la question suivante:

    Peut-on tranformer tout programme récursif en programme itératif?
    Si oui, comment faire pour le problème des tours de Hanoï?

    Voilà.

    Merci de vos réponses.

    A plus,
    Astérion.

    -----

  2. #2
    lawliet yagami

    Re : récurcivité, itération

    salut,

    d'après wikipédia il y a une moyen
    http://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

  3. #3
    Jack
    Modérateur

    Re : récurcivité, itération

    Je n'ai jamais suivi ce genre de cours, mais je sais qu'il existe des techniques pour dérécursiver des alogorithmes récursifs.

    Fais une recherche sur le net.

    Pour la tour de Hanoi, on t'a donné une réponse.

    A+

  4. #4
    invite1acecc80

    Re : récurcivité, itération

    Re,

    Citation Envoyé par Jack Voir le message
    Je n'ai jamais suivi ce genre de cours, mais je sais qu'il existe des techniques pour dérécursiver des alogorithmes récursifs.

    Fais une recherche sur le net.

    Pour la tour de Hanoi, on t'a donné une réponse.

    A+
    Oui, mais mon problème est en fait un peu plus sioux que la tour de Hanoï:
    Peut-on montrer que tout tout programme récursif est strictement équivalent à tout programme itératif?
    En fait existe-t-il pour un algo. type itératif un algo. type récursif de même complexité?

    j'ai également un problème d'un point de vue compilateur gcc.
    Exemple: algorithme pour réaliser une factorielle:
    l'un en itératif
    2 autres en récursif: l'un simple et l'autre "tail-rec".

    J'essaie de comparer le temps de calcul...
    Je trouve que le "tail-rec" est moins performant que celui simple (en récursif)...
    Je me demande si le compilateur n'optimise pas lui même le code de récursif simple pour le faire genre"tail-rec" mais en mieux

    Même avec une option style -00 ça ne change rien...

    A plus.

    NB: j'ai vu pour les tours de Hanoï.

  5. A voir en vidéo sur Futura
  6. #5
    invite1acecc80

    Re : récurcivité, itération

    Re,

    Bon comme je le disais en pas clair j'essaie des méthodes itérative et récursive de factorielle en C:

    code source de mes factorielles (je n'ai pas indenté désolé):

    Code:
    unsigned long facto_iter(int n) /* itératif */
    {
     int i=0;
     int p=1;
     if (n==0)
     {
      return 1;
     }
     else
     {
     for(i=0;i<n;i++)
     {
      p=p*(i+1);
     }
     return p;
     }
    }
    
    unsigned long facto_rec1(int n) /* récursive non tail-rec */
    {
    if(n==0)
    {
    return 1;
    }
    else
    {
    return n*facto_rec1(n-1);
    }
    } 	 
    
    unsigned long facto_rec2(unsigned long acc, int n) /* récursive tail-rec */
    {
    if (n==0)
    {
    return acc;
    }
    else
    {
    return facto_rec2(n*acc,n-1);
    }
    }
    
    unsigned long facto_rec3(int n) /* fonction avec acc non-redondante */ 
    {
    	return facto_rec2(1,n);
    }
    Je compile avec gcc et je change juste les paramètres d'optimisation du code:

    Code:
    gcc -W -Wall -pedantic -00 ...
    Je trouve que l'algo. itératif est vraiment bien plus perfomant que ceux récursifs...

    Code:
    gcc -W -Wall -pedantic -02 ...
    Là, j'ai: la fonction factorielle récursive simple (1) est dans les choux (normal..) par rapport à l'itérative...par contre la méthode récursive type tail-rec...est bien mieux que celle itérative...

    RQ: dans mon main je réalise une boucle for entre chaque fonction factorielle afin de mesurer un temps bien supérieur à la seconde...

    Voilà, où j'en suis et je ne comprends pas pourquoi le compilo me donne ce genre de résultat (j'aurais cru l'itératif soit disant plus "performant" suivant les dires de cetains...)

    A plus.

  7. #6
    whoami

    Re : récurcivité, itération

    Bonjour,

    Il faut aller voir le code généré.

    GCC en particulier est fort pour optimiser ce genre de code.

  8. #7
    invite1acecc80

    Re : récursivité, itération

    Re,

    Citation Envoyé par whoami Voir le message
    Bonjour,

    Il faut aller voir le code généré.

    GCC en particulier est fort pour optimiser ce genre de code.
    Tu demande "de décompiler" l'executable (ou de lire le code assembleur) c'est ça?
    Mon problème, c'est que je ne lis pas le langage assembleur... Je vais avoir des problèmes à comprendre...

    A plus.
    Dernière modification par JPL ; 03/02/2010 à 16h34.

Discussions similaires

  1. Itération
    Par ombeni dans le forum Physique
    Réponses: 2
    Dernier message: 20/11/2008, 12h12
  2. Comment python gère-t-il la récursivité ?
    Par martini_bird dans le forum Logiciel - Software - Open Source
    Réponses: 26
    Dernier message: 14/11/2006, 02h00
  3. calculer par itération ...???
    Par SpintroniK dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 16/04/2006, 10h59
  4. Intégrale et recursivité
    Par Olorin dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 17/01/2005, 12h22
Découvrez nos comparatifs produits sur l'informatique et les technologies.