Pourquoi devrait-on préférer la récursion à l'itération?

Question

L'itération est plus performante que la récursion, non? Alors pourquoi certaines personnes pensent-elles que la récursion est meilleure (plus élégante, selon leurs mots) que la répétition? Je ne vois vraiment pas pourquoi certaines langues comme Haskell ne permettent pas l'itération et encouragent la récursion? N’est-il pas absurde d’encourager des performances médiocres (et cela aussi lorsque l’option la plus performante, c’est-à-dire la récursivité, est disponible)? S'il vous plaît faire la lumière sur cela. Merci.

Answer 1

L'itération est plus performant que la récursivité, droit?

Pas nécessairement. Cette conception provient de nombreuses C comme les langues, où l'appel d'une fonction récursive ou non, a un grand frais généraux et créé une nouvelle structure de pile pour chaque appel.

Pour de nombreuses langues, ce n'est pas le cas, et la récursivité est tout aussi ou plus performantes qu'une version itérative. Ces jours-ci, même certains compilateurs C réécrire certains récursive des constructions à un processus itératif de version, ou de réutiliser le cadre de pile pour une queue appel récursif.

Answer 2

Essayez de mettre en œuvre de manière récursive et itérative la recherche en profondeur d'abord et dites-moi lequel vous a facilité la tâche. Ou fusionner le genre. Pour beaucoup de problèmes, il s’agit de maintenir explicitement votre propre pile au lieu de laisser vos données sur la pile de fonctions.

Je ne peux pas parler à Haskell car je ne l'ai jamais utilisé, mais c'est pour répondre à la partie plus générale de la question posée dans votre titre.

Answer 3

Haskell n'autorise pas l'itération car l'itération implique un état mutable (l'index).

Answer 4

Comme d'autres l'ont dit, il n'y a rien d'intrinsèquement moins performant sur la récursivité. Il y a des langues où il sera plus lent, mais ce n'est pas une règle universelle.

Cela étant dit, pour moi, la récursivité est un outil, pour être utilisé lorsque cela a du sens. Il y a quelques algorithmes qui sont mieux représentés que la récursivité (tout comme certains sont mieux par itération).

Affaire au point:

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

Je ne peux pas imaginer une solution itérative qui pourrait éventuellement l'intention plus claire que ça.

Answer 5

Voici quelques informations sur les avantages et les inconvénients de la récursivité et de l’itération dans c:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

Principalement pour moi, la récursion est parfois plus facile à comprendre que les itérations.