Algorithmes récursifs et itératifs

Question

J'applique l'algorithme euclidien pour trouver le GCD (Greatest Common Divisor) de deux entiers.

Deux exemples d'implémentations sont donnés: récursif et itératif. http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations

Ma question:

À l'école je me souviens de mes professeurs parler de fonctions récursives comme ils faisaient fureur, mais je doute un. Par rapport à une version itérative, les algorithmes récursifs ne prennent-ils pas plus d'espace de pile et donc beaucoup plus de mémoire? De plus, parce que l'appel d'une fonction nécessite une surcharge pour l'initialisation, les algorithmes récursifs ne sont-ils pas plus lents que leur homologue itératif?

Answer 1

Cela dépend entièrement de la langue. Si votre langue a le support de récursion de queue-appel (beaucoup font maintenant des jours) alors ils iront à une vitesse égale. Si ce n'est pas le cas, la version récursive sera plus lente et prendra plus d'espace de pile (précieux).

Answer 2

Tout dépend de la langue et du compilateur. Les ordinateurs actuels ne sont pas vraiment orientés vers une récursion efficace, mais certains compilateurs peuvent optimiser certains cas de récursion pour qu'ils fonctionnent aussi efficacement qu'une boucle (essentiellement, cela devient une boucle dans le code machine). Là encore, certains compilateurs ne peuvent pas.

La récursivité est peut-être plus belle au sens mathématique, mais si vous vous sentez plus à l'aise avec l'itération, utilisez-la.