La récursion est-elle toujours plus rapide que le bouclage ?

Question

Je sais que la récursion est parfois beaucoup plus propre que le bouclage, et je ne demande rien sur le moment où je devrais utiliser la récursion plutôt que l'itération, je sais qu'il y a déjà beaucoup de questions à ce sujet.

Ce que je demande est, est-ce que la récursion jamais plus vite qu'une boucle ? Pour moi, il me semble qu'il serait toujours possible d'affiner une boucle et de la faire fonctionner plus rapidement qu'une fonction récursive parce que la boucle n'est pas constamment en train de créer de nouveaux cadres de pile.

Je cherche spécifiquement à savoir si la récursion est plus rapide dans les applications où la récursion est la bonne façon de traiter les données, comme dans certaines fonctions de tri, dans les arbres binaires, etc.

Answer 1

Cela dépend de la langue utilisée. Vous avez écrit "language-agnostic", je vais donc vous donner quelques exemples.

En Java, C et Python, la récursion est assez coûteuse par rapport à l'itération (en général) car elle nécessite l'allocation d'un nouveau cadre de pile. Dans certains compilateurs C, on peut utiliser un drapeau de compilation pour éliminer cette surcharge, ce qui transforme certains types de récursion (en fait, certains types d'appels de queue) en sauts au lieu d'appels de fonction.

Dans les implémentations des langages de programmation fonctionnelle, l'itération peut parfois être très coûteuse et la récursion très bon marché. Dans beaucoup, la récursion est transformée en un simple saut, mais en changeant la variable de la boucle (qui est mutable) parfois nécessite des opérations relativement lourdes, en particulier sur les implémentations qui prennent en charge plusieurs threads d'exécution. La mutation est coûteuse dans certains de ces environnements en raison de l'interaction entre le mutateur et le ramasseur de déchets, si les deux peuvent être exécutés en même temps.

Je sais que dans certaines implémentations de Scheme, la récursion est généralement plus rapide que le bouclage.

En bref, la réponse dépend du code et de l'implémentation. Utilisez le style que vous préférez. Si vous utilisez un langage fonctionnel, la récursion pourrait être plus rapide. Si vous utilisez un langage impératif, l'itération est probablement plus rapide. Dans certains environnements, les deux méthodes aboutiront à la génération du même assemblage (mettez cela dans votre pipe et fumez-le).

Addendum : Dans certains environnements, la meilleure alternative n'est ni la récursion ni l'itération, mais plutôt les fonctions d'ordre supérieur. Il s'agit notamment de "map", "filter" et "reduce" (qui est également appelé "fold"). Non seulement ces fonctions sont le style préféré, non seulement elles sont souvent plus propres, mais dans certains environnements, ces fonctions sont les premières (ou les seules) à bénéficier de la parallélisation automatique - elles peuvent donc être nettement plus rapides que l'itération ou la récursion. Data Parallel Haskell est un exemple d'un tel environnement.

Les compréhensions de listes sont une autre alternative, mais elles ne sont généralement que du sucre syntaxique pour l'itération, la récursion ou les fonctions d'ordre supérieur.

Answer 2

La récursion peut être plus rapide lorsque l'alternative consiste à gérer explicitement une pile, comme dans les algorithmes de tri ou d'arbre binaire que vous mentionnez.

Il m'est arrivé que la réécriture d'un algorithme récursif en Java le rende plus lent.

La bonne approche consiste donc à l'écrire d'abord de la manière la plus naturelle, à ne l'optimiser que si le profilage montre qu'elle est critique, puis à mesurer l'amélioration supposée.

Answer 3

Récursion de la queue est aussi rapide que le bouclage. De nombreux langages fonctionnels intègrent la récursion de queue.

Answer 4

Considérez ce qui doit absolument être fait pour chacun, l'itération et la récursion.

• itération : un saut au début de la boucle
• récursion : un saut au début de la fonction appelée

Vous voyez qu'il n'y a pas beaucoup de place pour les différences ici.

(Je suppose que la récursion est un appel de queue et que le compilateur est conscient de cette optimisation).

Answer 5

Dans tout système réaliste, non, la création d'un cadre de pile sera toujours plus coûteuse qu'un INC et un JMP. C'est pourquoi les très bons compilateurs transforment automatiquement la récursion de queue en un appel au même cadre, c'est-à-dire sans la surcharge, de sorte que vous obtenez la version source plus lisible et la version compilée plus efficace. A vraiment, vraiment Un bon compilateur devrait même être capable de transformer la récursion normale en récursion de queue lorsque cela est possible.