récursivité, itération

[invite1acecc80]

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.
-----

[invite3ba0dddb]

salut,

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

[Jack]

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+

[invite1acecc80]

Re,

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ï.

[A voir en vidéo sur Futura]

[invite1acecc80]

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é):

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:

gcc -W -Wall -pedantic -00 ...

Je trouve que l'algo. itératif est vraiment bien plus perfomant que ceux récursifs...

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.

[invite2d7144a7]

Bonjour,

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

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

[invite1acecc80]

Re,

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.