Est la récursivité jamais plus vite que la boucle?

la récursivité est toujours plus rapide qu'une boucle?

Non, Itération sera toujours plus rapide que la Récursivité. (dans une Architecture de Von Neumann)

Explication:

Si vous construisez un minimum d'opérations d'un générique de l'ordinateur à partir de zéro, "Itération" vient d'abord comme un bloc de construction et exigeant moins de ressources "récursivité", ergo est plus rapide.

La construction d'un pseudo-informatique-machine à partir de zéro:

Vous remettre en Question: de Quoi avez-vous besoin de calculer une valeur, c'est à dire de suivre un algorithme, et de parvenir à un résultat?

Nous permettra d'établir une hiérarchie de concepts, à partir de zéro et de définir en premier lieu la base, concepts de base, puis de construction de second niveau des concepts avec ceux-ci, et ainsi de suite.

1. Premier Concept: cellules de Mémoire, de stockage, de l'État. Faire quelque chose que vous devez lieux pour stocker des intermédiaires et finaux valeurs de résultat. Imaginons que nous avons un éventail infini de "integer" cellules, appelées Mémoire, M[0..Infini].

2. Instructions: faire quelque chose de transformation d'une cellule, de modifier sa valeur. modifier l'état. Chaque intéressante instruction effectue une transformation. Les instructions de base sont:

   a) Set & déplacer des cellules de mémoire

   • de stocker une valeur dans la mémoire, par exemple: magasin 5 m[4]
   • copier une valeur à une autre position: par exemple: magasin m[4] m[8]

   b) de la Logique et de l'arithmétique

   • et, ou, xor, pas
   • add, sub, mul, div. par exemple, ajouter m[7] m[8]

3. Un Agent d'Exécution: un de base dans un cadre moderne CPU. Un "agent" est quelque chose qui peut exécuter des instructions. Un Agent peut également être une personne à la suite de l'algorithme sur papier.

4. Ordre des étapes: une séquence d'instructions: c'est à dire: d'abord faire cela, faire cela après, etc. Un impératif séquence d'instructions. Une ligne expressions sont "un impératif séquence d'instructions". Si vous avez une expression avec un "ordre de l'évaluation" alors vous avez étapes. Cela signifie que même un seul composé expression implicite “étapes” et dispose également d'un local implicite variable (appelons-le “résultat”). par exemple:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   L'expression ci-dessus implique 3 étapes avec un implicite "résultat" à la variable.

   //pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   Donc même infix expressions, puisque vous avez un ordre spécifique de l'évaluation, sont un impératif séquence d'instructions. L'expression implique une séquence d'opérations à faire dans un ordre précis, et parce qu'il y a étapes, il y a aussi un implicite "résultat" variable intermédiaire.

5. Pointeur d'Instruction: Si vous avez une séquence d'étapes, vous avez également un implicite "pointeur d'instruction". Le pointeur d'instruction des marques de la prochaine instruction, et les avances après l'instruction de lecture, mais avant l'instruction est exécutée.

   Dans cette pseudo-informatique-machine, le Pointeur d'Instruction est une partie de Mémoire. (Remarque: Normalement, le Pointeur d'Instruction sera un “registre spécial” dans un cœur de PROCESSEUR, mais ici, nous allons simplifier les concepts et d'en assumer toutes les données (registres inclus) font partie de la “Mémoire”)

6. Sauter - une Fois que vous avez commandé un certain nombre d'étapes et un Pointeur d'Instruction, vous pouvez appliquer la "magasin" instruction pour modifier la valeur du Pointeur d'Instruction lui-même. Nous appellerons cette utilisation spécifique de la magasin instruction avec un nouveau nom: Sauter. Nous utilisons un nouveau nom, car il est plus facile de penser à elle comme un nouveau concept. En modifiant le pointeur d'instruction nous allons demander à l'agent de “passer à l'étape x“.

7. Infini Itération: Par sauter en arrière, maintenant, vous pouvez faire de l'agent "répéter" un certain nombre d'étapes. À ce stade, nous avons infini Itération.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  //infinite loop
   

8. Conditionnelle - Conditionnelle de l'exécution d'instructions. Avec le "conditionnel" clause, vous pouvez exécuter conditionnellement l'un de plusieurs instructions fondées sur l'état actuel (qui peut être définie avec une instruction précédente).

9. Bon Itération: Maintenant, avec la conditionnelle clause, nous pouvons échapper à la boucle infinie de la revenir instruction. Nous avons maintenant un conditionnelle boucle et puis bon Itération

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  //jump only if the previous 
                           //sub instruction did not result in 0
   
   //this loop will be repeated 1000 times
   //here we have proper ***iteration***, a conditional loop.
   

10. De nommage: donner des noms à un emplacement de mémoire contenant des données ou la tenue d'une étape. C'est juste une "commodité" pour avoir. Nous n'avons pas ajouter de nouvelles instructions en ayant la capacité de définir des “noms” pour les emplacements de mémoire. “Naming” n'est pas une instruction de l'agent, c'est juste un confort pour nous. De nommage rend le code (à ce point) plus facile à lire et plus facile à modifier.

       #define counter m[30]   //name a memory location
       mov 1000 counter
    loop:                      //name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    

11. Un niveau de sous-routine: Supposons qu'il y a une série d'étapes que vous devez exécuter fréquemment. Vous pouvez stocker les étapes dans un nom de position en mémoire, puis saut à cette position lorsque vous avez besoin de les exécuter (appel). À la fin de la séquence, vous aurez besoin de retour au point de appel pour poursuivre l'exécution. Avec ce mécanisme, vous êtes la création de nouvelles instructions (sous-programmes) par la composition de base des instructions.

    Mise en œuvre: (pas de nouveaux concepts requis)

    • Stocker le Pointeur d'Instruction en cours dans un prédéfinie position de mémoire
    • sauter à la sous-routine
    • à la fin de la sous-routine, vous pouvez récupérer le Pointeur d'Instruction de la prédéfinies de l'emplacement de mémoire, effectivement saut de retour à la suite de l'instruction de l'original appel

    Problème avec le un niveau mise en œuvre: Vous ne pouvez pas appeler un autre sous-routine à partir d'un sous-programme. Si vous le faites, vous allez écraser l'adresse de retour (variable globale), de sorte que vous ne pouvez pas imbriquer des appels.

    D'avoir un une meilleure mise en Œuvre pour les sous-routines: Vous avez besoin d'une PILE

12. Pile: Vous définissez un espace de mémoire pour fonctionner comme une "pile", vous pouvez “pousser” des valeurs sur la pile, et aussi “pop” le dernier “poussé” de la valeur. Pour mettre en œuvre une pile, vous aurez besoin d'un Pointeur de Pile (similaire au Pointeur d'Instruction), ce qui souligne la “tête” de la pile. Lorsque vous “pousser” une valeur, le pointeur de pile décrémente et vous stocker la valeur. Lorsque vous “pop”, vous obtenez la valeur au Pointeur de Pile, puis le Pointeur de Pile est incrémenté.

13. Sous-routines Maintenant que nous avons un pile nous pouvons mettre en œuvre correcte des sous-routines permettant les appels imbriqués. La mise en œuvre est similaire, mais au lieu de stocker le Pointeur d'Instruction dans un prédéfinie position de mémoire, nous "pousser" la valeur de la propriété intellectuelle dans le pile. À la fin de la sous-routine, nous venons de “pop”, la valeur de la pile, de manière efficace saut de retour à l'instruction après l'original appel. Cette mise en œuvre, d'avoir une “pile” permet d'appeler un sous-programme à partir d'un autre sous-programme. Avec cette application, nous pouvons créer plusieurs niveaux d'abstraction lors de la définition de de nouvelles instructions comme des sous-programmes, en utilisant la base des instructions ou des autres sous-programmes, comme les blocs de construction.

14. La récursivité: Ce qui se passe quand un sous-programme s'appelle elle-même?. Ceci est appelé la "récursivité".

    Problème: d'Écraser les locaux de résultats intermédiaires d'un sous-programme peut être stocker dans la mémoire. Depuis que vous appelez de réutiliser les mêmes étapes, si les résultats intermédiaires sont stockées dans prédéfinis emplacements de mémoire (variables globales), ils seront remplacés sur les appels imbriqués.

    Solution: Pour permettre la récursivité, les sous-programmes doivent magasin local de résultats intermédiaires dans la pile, par conséquent, sur chaque appel récursif (directe ou indirecte), les résultats intermédiaires sont stockés dans différents emplacements de mémoire.

...

avoir atteint la récursivité nous arrêter ici.

Conclusion:

Dans une Architecture de Von Neumann, clairement "Itération" est plus simple/le concept de base de “Récursivité". Nous avons une forme de "Itération" au niveau 7, tandis que "Récursivité" est au niveau 14 de la hiérarchie de concepts.

Itération sera toujours plus rapide en code machine, car elle implique moins d'instructions, par conséquent, moins de cycles de PROCESSEUR.

Lequel est le "mieux"?

• Vous devez utiliser "itération" lors du traitement de données simple, séquentielle des structures de données, et partout une “simple boucle” on va le faire.

• Vous devez utiliser "récursivité" quand vous en avez besoin pour traiter une structure de données récursive (j'aime à les appeler “Fractal de Structures de Données”), ou lorsque la solution récursive est clairement plus “élégant”.

Conseils: utiliser le meilleur outil pour le travail, mais de comprendre le fonctionnement interne de chaque outil afin de choisir judicieusement.

Enfin, notez que vous avez beaucoup de possibilités d'utiliser la récursivité. Vous avez Récursive des Structures de Données partout, vous êtes à la recherche à la une aujourd'hui: les parties du DOM d'appuyer ce que vous lisez sont un RDS, un JSON expression est un RDS, le système de fichiers hiérarchique dans votre ordinateur est un RDS, j'.e: vous avez un répertoire racine, contenant des fichiers et des répertoires, chaque répertoire contenant des fichiers et des répertoires, chacun de ces répertoires contenant des fichiers et des répertoires...

OriginalL'auteur Lucio M. Tato

La queue de la récursivité est aussi rapide que de faire la boucle. De nombreux langages fonctionnels ont la queue de la récursivité mis en œuvre en eux.

OriginalL'auteur mkorpela

Plus de réponses ici, oubliez le coupable évident pourquoi la récursivité est souvent plus lent que itératif des solutions. C'est lié à l'accumulation et à la déchirure en bas de la pile des images, mais n'est pas exactement cela. C'est généralement une grande différence dans le stockage de l'auto variable pour chaque récursion. Dans un algorithme itératif avec une boucle, les variables sont souvent détenus dans des registres, et même si on déborde, ils se trouvent dans le cache de Niveau 1. Dans un algorithme récursif, tous les états intermédiaires de la variable sont stockées sur la pile, ce qui signifie qu'ils engendrent beaucoup plus de déversements de mémoire. Cela signifie que même si elle fait la même quantité d'opérations, elle aura beaucoup les accès à la mémoire dans la chaleur de la boucle et ce qui est pire, ces opérations de mémoire ont un mauvais taux de réutilisation faire les caches moins efficace.

TL;DR algorithmes récursifs ont généralement un plus mauvais comportement de cache que itératif.

OriginalL'auteur Patrick Schlüter

Réaliste du système, non, la création d'un cadre de pile sera toujours plus cher qu'un INC et un JMP. C'est pourquoi, vraiment bon, les compilateurs de transformer automatiquement la queue de la récursivité en appel à la même image, c'est à dire sans les frais généraux, de sorte que vous obtenez le plus lisible de la source de la version et la plus efficace de la version compilée. Un vraiment, vraiment bon compilateur devrait même être en mesure de transformer la normale de la récursivité dans la queue de la récursivité où c'est possible.

OriginalL'auteur Kilian Foth

C'est une supposition. Généralement la récursivité n'a probablement pas battre en boucle souvent ou jamais sur des problèmes de taille décente, si les deux utilisent vraiment bon algorithmes(en ne comptant pas la mise en œuvre de la difficulté) , il peut être différent si elle est utilisée avec une langue w/queue appelons récursivité(et une queue algorithme récursif et avec des noeuds dans le cadre de la langue)-qui aurait probablement très similaire et peut-être même préférer la récursivité de temps en temps.

OriginalL'auteur Roman A. Taycher

Selon la théorie c'est la même choses.
La récursivité et d'une boucle avec le même O() la complexité du travail avec la même vitesse théorique, mais bien sûr de la vitesse réelle dépend de langage, le compilateur et le processeur.
Exemple avec la puissance d'un nombre peut être codée dans l'itération de façon à O(ln(n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }

OriginalL'auteur Hydrophis Spiralis