Pourquoi les boucles sont-elles plus rapides que la récursivité?

En pratique, je comprends que toute récursivité peut être écrite comme une boucle (et vice versa (?)) Et si nous mesurons avec des ordinateurs réels, nous constatons que les boucles sont plus rapides que la récursivité pour le même problème. Mais y a-t-il une théorie qui fait cette différence ou est-ce principalement emprisonné?

La raison pour laquelle les boucles sont plus rapides que la récursivité est facile.
Une boucle ressemble à ceci dans l'assemblage.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Un seul saut conditionnel et une comptabilité pour le compteur de boucles.

La récursivité (lorsqu'elle n'est pas ou ne peut pas être optimisée par le compilateur) ressemble à ceci:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

C'est beaucoup plus complexe et vous obtenez au moins 3 sauts (1 test pour voir si cela a été fait, un appel et un retour).
De plus, en récursivité, les paramètres doivent être configurés et récupérés.
Rien de tout cela n'est nécessaire dans une boucle car tous les paramètres sont déjà configurés.

Théoriquement, les paramètres pourraient également rester en place avec la récursivité, mais aucun compilateur à ma connaissance ne va aussi loin dans leur optimisation.

Différences entre un appel et un jmp
Une paire appel-retour n'est pas beaucoup plus chère que le jmp. La paire prend 2 cycles et le jmp en prend 1; à peine perceptible.
Dans les conventions d'appel qui prennent en charge les paramètres de registre, la surcharge des paramètres est minimale, mais même les paramètres de pile sont bon marché tant que les tampons du processeur ne débordent pas .
C'est la surcharge de l'établissement d'appel dictée par la convention d'appel et la gestion des paramètres utilisée qui ralentit la récursivité.
Cela dépend beaucoup de l'implémentation.

Exemple de mauvaise gestion de la récursivité Par exemple, si un paramètre est passé qui est compté par référence (par exemple un paramètre de type géré non const), il ajoutera 100 cycles faisant un ajustement verrouillé du compte de référence, tuant totalement les performances par rapport à une boucle.
Dans les langues qui sont réglées sur la récursivité, ce mauvais comportement ne se produit pas.

Optimisation du processeur
L'autre raison pour laquelle la récursivité est plus lente est qu'elle fonctionne contre les mécanismes d'optimisation des processeurs.
Les retours ne peuvent être prédits correctement que s'ils ne sont pas trop nombreux dans une rangée. Le processeur dispose d'un tampon de pile de retour avec (quelques) poignées d'entrées. Une fois ceux-ci épuisés, chaque retour supplémentaire sera mal prédit, entraînant d'énormes retards.
Sur tout processeur qui utilise une récursion basée sur un appel de tampon de retour de pile qui dépasse la taille du tampon, il est préférable d'éviter.

À propos d'exemples de code triviaux utilisant la récursivité
Si vous utilisez un exemple trivial de récursivité comme la génération de nombres de Fibonacci, alors ces effets ne se produisent pas, car tout compilateur qui «connaît» la récursivité le transformera en boucle, tout comme n'importe quel programmeur digne de ce nom voudrais.
Si vous exécutez ces exemples triviaux dans un environnement qui ne s'optimise pas correctement, la pile d'appels se développera (inutilement) hors des limites.

À propos de la récursivité de la queue
Notez que parfois le compilateur optimise la récursivité de la queue en la transformant en boucle. Il est préférable de se fier uniquement à ce comportement dans les langues qui ont un bon historique connu à cet égard.
De nombreuses langues insèrent du code de nettoyage caché avant le retour final empêchant l'optimisation de la récursivité de la queue.

Confusion entre vraie et pseudo récursivité
Si votre environnement de programmation transforme votre code source récursif en boucle, alors ce n'est sans doute pas la vraie récursivité qui est en cours d'exécution.
La véritable récursivité nécessite un magasin de fil d'Ariane, afin que la routine récursive puisse retracer ses étapes après sa sortie.
C'est la gestion de ce chemin qui rend la récursion plus lente que l'utilisation d'une boucle. Cet effet est amplifié par les implémentations CPU actuelles, comme indiqué ci-dessus.

Effet de l'environnement de programmation
Si votre langage est réglé sur l'optimisation de la récursivité, allez-y et utilisez la récursivité à chaque occasion. Dans la plupart des cas, la langue transformera votre récursivité en une sorte de boucle.
Dans les cas où il ne le peut pas, le programmeur aurait également du mal à le faire. Si votre langage de programmation n'est pas réglé sur la récursivité, il doit être évité, sauf si le domaine est adapté à la récursivité.
Malheureusement, de nombreuses langues ne gèrent pas bien la récursivité.

Utilisation abusive de la récursivité
Il n'est pas nécessaire de calculer la séquence de Fibonacci en utilisant la récursivité, en fait c'est un exemple pathologique.
La récursivité est mieux utilisée dans les langues qui la prennent en charge explicitement ou dans les domaines où la récursivité brille, comme la gestion des données stockées dans une arborescence.

Je comprends que toute récursivité peut être écrite comme une boucle

Oui, si vous souhaitez placer la charrue avant le cheval.
Toutes les instances de récursivité peuvent être écrites en boucle, certaines de ces instances nécessitent que vous utilisiez une pile explicite comme le stockage.
Si vous avez besoin de rouler votre propre pile juste pour transformer du code récursif en une boucle, vous pouvez tout aussi bien utiliser la récursivité ordinaire.
À moins bien sûr que vous ayez des besoins spéciaux comme l'utilisation d'énumérateurs dans une structure arborescente et que vous ne disposiez pas d'une prise en charge linguistique appropriée.

Ces autres réponses sont quelque peu trompeuses. Je suis d'accord qu'ils indiquent les détails de mise en œuvre qui peuvent expliquer cette disparité, mais ils surestiment le cas. Comme correctement suggéré par jmite, ils sont orientés vers l' implémentation vers des implémentations cassées d'appels de fonction / récursivité. De nombreuses langues implémentent des boucles via la récursivité, de sorte que les boucles ne seront clairement pas plus rapides dans ces langues. La récursivité n'est en rien moins efficace que le bouclage (lorsque les deux sont applicables) en théorie. Permettez-moi de citer le résumé du document de 1977 de Guy Steele, Démystifiant le mythe de "l'appel de procédure coûteux" ou, les implémentations de procédures considérées comme nuisibles ou, Lambda: l'ultime GOTO

Le folklore déclare que les instructions GOTO sont "bon marché", tandis que les appels de procédure sont "chers". Ce mythe est en grande partie le résultat d'implémentations de langage mal conçues. La croissance historique de ce mythe est considérée. Des idées théoriques et une implémentation existante sont discutées, ce qui démystifie ce mythe. Il est démontré que l'utilisation sans restriction des appels de procédure permet une grande liberté stylistique. En particulier, tout organigramme peut être écrit comme un programme "structuré" sans introduire de variables supplémentaires. La difficulté avec l'instruction GOTO et l'appel de procédure est caractérisée comme un conflit entre les concepts de programmation abstraits et les constructions de langage concrètes.

Le «conflit entre les concepts de programmation abstraits et les constructions de langage concrètes» peut être vu du fait que la plupart des modèles théoriques, par exemple, du calcul lambda non typé , n'ont pas de pile . Bien sûr, ce conflit n'est pas nécessaire comme l'illustre l'article ci-dessus et comme le démontrent également les langages qui n'ont pas de mécanisme d'itération autre que la récursivité comme Haskell.

Laissez-moi vous démontrer. Pour simplifier, je vais utiliser un calcul lambda « appliqué » avec des chiffres et booléens et, et je suppose que nous avons un combinateur point fixe , fixqui satisfait fix f x = f (fix f) x. Tout cela peut être réduit au simple calcul lambda sans type sans changer mon argument. La manière archétypale de comprendre l'évaluation du calcul lambda consiste à réécrire les termes avec la règle de réécriture centrale de la réduction bêta, à savoir où signifie "remplacer tout libre occurrences de dans avec "et[ N / x ] x $(\lambda x.M)N \leadsto M[N/x]$$[N/x]$$x$$M$$N$$\leadsto$signifie "réécrit dans". Il s'agit simplement de la formalisation de la substitution des arguments d'un appel de fonction dans le corps des fonctions.

Maintenant, pour un exemple. Définir factcomme

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Voici l'évaluation de fact 3, où, pour la compacité, je vais utiliser gcomme synonyme de fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), c'est-à-dire fact = g 1. Cela n'affecte pas mon argument.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Vous pouvez voir sur la forme sans même regarder les détails qu'il n'y a pas de croissance et que chaque itération a besoin de la même quantité d'espace. (Techniquement, le résultat numérique augmente, ce qui est inévitable et tout aussi vrai pour une whileboucle.) Je vous mets au défi de souligner ici la "pile" sans cesse croissante.

Il semble que la sémantique archétypale du calcul lambda fasse déjà ce qu'on appelle communément "l'optimisation des appels de queue". Bien sûr, aucune "optimisation" ne se produit ici. Il n'y a pas de règles spéciales ici pour les appels "de queue" par opposition aux appels "normaux". Pour cette raison, il est difficile de donner une caractérisation "abstraite" de ce que fait "l'optimisation" d'appel de queue, comme dans de nombreuses caractérisations abstraites de la sémantique des appels de fonction, il n'y a rien à faire pour "l'optimisation" d'appel de queue!

Que la définition analogue de fact«débordements de pile» dans de nombreux langages est un échec de ces langages à implémenter correctement la sémantique des appels de fonction. (Certaines langues ont une excuse.) La situation est à peu près similaire à une implémentation de langue qui implémente des tableaux avec des listes liées. L'indexation dans de tels "tableaux" serait alors une opération O (n) qui ne répond pas aux attentes des tableaux. Si je faisais une implémentation distincte du langage, qui utilisait de vrais tableaux au lieu de listes liées, vous ne diriez pas que j'ai mis en œuvre "l'optimisation de l'accès aux tableaux", vous diriez que j'ai corrigé une implémentation cassée des tableaux.

Donc, répondant à la réponse de Veedrac. Les piles ne sont pas "fondamentales" à la récursivité . Dans la mesure où un comportement "semblable à une pile" se produit au cours de l'évaluation, cela ne peut se produire que dans les cas où les boucles (sans structure de données auxiliaire) ne seraient pas applicables en premier lieu! En d'autres termes, je peux implémenter des boucles avec récursivité avec exactement les mêmes caractéristiques de performance. En effet, Scheme et SML contiennent tous deux des constructions en boucle, mais les deux définissent celles-ci en termes de récursivité (et, au moins dans Scheme, doest souvent implémentée comme une macro qui se développe en appels récursifs.) De même, pour la réponse de Johan, rien ne dit un le compilateur doit émettre l'assembly Johan décrit pour la récursivité. En effet,exactement le même assemblage, que vous utilisiez des boucles ou une récursivité. La seule fois où le compilateur serait (quelque peu) obligé d'émettre un assembly comme ce que Johan décrit, c'est quand vous faites quelque chose qui n'est pas exprimable par une boucle de toute façon. Comme indiqué dans l'article de Steele et démontré par la pratique réelle de langages comme Haskell, Scheme et SML, il n'est pas "extrêmement rare" que les appels de queue puissent être "optimisés", ils peuvent toujoursêtre "optimisé". Le fait qu'une utilisation particulière de la récursivité s'exécute dans un espace constant dépend de la façon dont elle est écrite, mais les restrictions que vous devez appliquer pour rendre cela possible sont les restrictions dont vous auriez besoin pour adapter votre problème à la forme d'une boucle. (En fait, ils sont moins stricts. Il y a des problèmes, tels que l'encodage des machines à états, qui sont traités plus proprement et plus efficacement via les appels de queues, par opposition aux boucles qui nécessiteraient des variables auxiliaires.) Encore une fois, la seule récursion de temps nécessite de faire plus de travail est quand votre code n'est pas une boucle de toute façon.

Je suppose que Johan fait référence aux compilateurs C qui ont des restrictions arbitraires sur le moment où il effectuera une "optimisation" d'appel de queue. Johan fait aussi probablement référence à des langages comme C ++ et Rust lorsqu'il parle de "langages avec types gérés". L' idiome RAII de C ++ et présent dans Rust fait aussi des choses qui ressemblent superficiellement à des appels de queue, pas à des appels de queue (parce que les "destructeurs" doivent encore être appelés). Il a été proposé d'utiliser une syntaxe différente pour choisir une sémantique légèrement différente qui permettrait la récursivité de la queue (à savoir les destructeurs d'appels avantle dernier appel de queue et de toute évidence interdire l'accès aux objets "détruits"). (Le garbage collection n'a pas un tel problème, et tous les Haskell, SML et Scheme sont des langages de garbage collection.) Dans une veine assez différente, certains langages, tels que Smalltalk, exposent la "pile" comme un objet de première classe, dans ces cas, la "pile" n'est plus un détail d'implémentation, bien que cela n'empêche pas d'avoir des types d'appels séparés avec une sémantique différente. (Java dit que ce n'est pas possible en raison de la façon dont il gère certains aspects de la sécurité, mais c'est en fait faux .)

Dans la pratique, la prévalence des implémentations interrompues des appels de fonction provient de trois facteurs principaux. Tout d'abord, de nombreux langages héritent de l'implémentation rompue de leur langage d'implémentation (généralement C). Deuxièmement, la gestion déterministe des ressources est agréable et rend le problème plus compliqué, bien que seule une poignée de langues le proposent. Troisièmement, et d'après mon expérience, la raison pour laquelle la plupart des gens se soucient, c'est qu'ils veulent des traces de pile lorsque des erreurs se produisent à des fins de débogage. Seule la deuxième raison est celle qui peut être potentiellement théoriquement motivée.

Fondamentalement, la différence est que la récursivité inclut une pile, une structure de données auxiliaire dont vous ne voulez probablement pas, alors que les boucles ne le font pas automatiquement. Ce n'est que dans de rares cas qu'un compilateur typique est capable de déduire que vous n'avez pas vraiment besoin de la pile après tout.

Si vous comparez à la place des boucles fonctionnant manuellement sur une pile allouée (par exemple via un pointeur pour stocker la mémoire), vous ne les trouverez normalement pas plus rapides ni même plus lents que l'utilisation de la pile matérielle.