Récursion Vs boucles

Question

Je suis en train de travailler avec des exemples sur les arbres comme indiqué ici: http: // cslibrary. stanford.edu/110/BinaryTrees.html Tous ces exemples résoudre les problèmes par la récursivité, je me demande si nous pouvons fournir une solution itérative pour chacun d'eux, ce qui signifie, peut-on être sûr qu'il ya un problème qui peut être résolu toujours par récursion aura également une solution itérative, en général. Sinon, quel exemple nous pouvons donner pour montrer un problème qui peut être résolu que par récursion / Iteration?

-

Answer 1

La seule différence entre l'itération et la récursivité sur un ordinateur est de savoir si vous utilisez le haut-pile ou une pile définie par l'utilisateur. Donc, ils sont équivalents.

Answer 2

Dans mon expérience, la solution la plus récursive peut en effet être résolu de manière itérative.

Il est également une bonne technique d'avoir, en tant que solutions récursives peuvent avoir une trop grande surcharge de consommation de mémoire et CPU.

Answer 3

Depuis récursion utilise une pile implicite sur lequel il stocke des informations sur chaque appel, vous pouvez toujours mettre en œuvre cette pile vous-même et éviter les appels récursifs. Alors oui, chaque solution récursive peut être transformé en un processus itératif.

Lire cette question une preuve.

Answer 4

récursivité et itération sont deux outils qui, à un niveau très fondamental, font la même chose: exécuter une opération répétée sur un ensemble défini de valeurs. Ils sont interchangeables dans qu'il n'y a pas de problème qui ne peut pas, dans certains façon, être résolus par un seul d'entre eux. Cela ne signifie pas, cependant, que l'on ne peut pas être plus adapté que l'autre.

Answer 5

Recursion a l'avantage où elle continuera sans fin connue. Un parfait exemple de cela est réglé et un filetage rapide Trier.

Vous ne pouvez pas spawn boucles supplémentaires, mais vous pouvez faire naître de nouvelles discussions via récursivité.

Answer 6

En tant que « vieux gars, » Je revenir à ma mémoire d'apprentissage qui parseurs récursifs descente sont plus faciles à écrire, mais à base de pile, parseurs itératives de meilleurs résultats. Voici un article qui semble soutenir cette idée avec des mesures:

http : //www.texttoolkit.com/index.php option = com_content & view = article & catid = 35% 3Atechnology & id = 60% 3Abeyond-descente récursive & Itemid = 55

Une chose à noter est la mention de l'auteur de la pile de dépassement appel avec descente récursive. Une itérative, la mise en œuvre basée sur la pile peut être beaucoup plus efficace des ressources.