Y a-t-il quelque chose qui peut être fait avec la récursion qui ne peut pas être fait avec les boucles?

126

Il arrive que l’utilisation de la récursivité soit meilleure que celle d’une boucle et que l’utilisation d’une boucle est meilleure que l’utilisation de la récursivité. Choisir le «bon» choix peut économiser des ressources et / ou réduire le nombre de lignes de code.

Existe-t-il des cas où une tâche ne peut être effectuée qu’en utilisant la récursion plutôt qu’une boucle?

Pikamander2
la source
13
J'en doute sérieusement. La récursion est une boucle glorifiée.
Courses de légèreté en orbite
6
En voyant les directions divergentes dans lesquelles les réponses vont (et après avoir moi-même échoué à en fournir une meilleure), vous pourriez faire plaisir à quiconque essayant de répondre à une faveur si vous fournissez un peu plus de fond et quel genre de réponse vous recherchez. Voulez-vous une preuve théorique pour des machines hypothétiques (avec un stockage et une durée d'exécution illimités)? Ou des exemples pratiques? (Où «serait ridiculement compliqué» pourrait être qualifié de «ne peut être fait».) Ou quelque chose de différent?
5gon12eder
8
@LightnessRacesinOrbit Pour mon oreille non anglophone, "La récursivité est une boucle glorifiée" signifie "Vous pouvez aussi bien utiliser une construction en boucle au lieu d'un appel récursif n'importe où, et le concept ne mérite pas vraiment son propre nom" . Peut-être que j'interprète le faux "quelque chose glorifié", alors.
Hyde
13
Qu'en est-il de la fonction Ackermann? en.wikipedia.org/wiki/Ackermann_function , pas particulièrement utile mais impossible à faire en boucle. (Vous pouvez également vérifier cette vidéo youtube.com/watch?v=i7sm9dzFtEI de Computerphile)
WizardOfMenlo
8
@WizardOfMenlo le code befunge est une implémentation de la solution ERRE (qui est aussi une solution interactive ... avec une pile). Une approche itérative avec une pile peut émuler un appel récursif. Dans toute programmation suffisamment puissante, une construction en boucle peut être utilisée pour en émuler une autre. La machine de registre avec les instructions INC (r), JZDEC (r, z)peut mettre en œuvre une machine de Turing. Il n'y a pas de 'récursivité' - c'est un saut si zéro sinon DECrement. Si la fonction Ackermann est calculable (elle l’est), cette machine enregistreuse peut le faire.

Réponses:

164

Oui et non. En fin de compte, rien ne permet de calculer la récursivité comme le ferait une boucle, mais la boucle prend beaucoup plus de place. Par conséquent, la seule chose que la récursion puisse faire est que les boucles ne peuvent pas rendre certaines tâches super faciles.

Promenez-vous dans un arbre. Marcher dans un arbre avec la récursion est stupide-facile. C'est la chose la plus naturelle du monde. Marcher dans un arbre avec des boucles est beaucoup moins simple. Vous devez conserver une pile ou une autre structure de données pour garder une trace de ce que vous avez fait.

Souvent, la solution récursive à un problème est plus jolie. C'est un terme technique, et c'est important.

Scant Roger
la source
120
Fondamentalement, faire des boucles au lieu de récursivité signifie gérer manuellement la pile.
Silviu Burcea
15
... la pile (s) . La situation suivante peut fortement préférer avoir plus d'une pile. Prenons une fonction récursive Aqui trouve quelque chose dans un arbre. Chaque Afois qu'il rencontre cette chose, il lance une autre fonction récursive Bqui trouve une chose liée dans le sous-arbre à la position où elle a été lancée A. Une fois Bla récursion terminée, celle-ci revient Aet cette dernière poursuit sa propre récursivité. On peut déclarer une pile pour Aet une pour B, ou la placer Bdans la Aboucle. Si l'on insiste pour utiliser une seule pile, les choses deviennent vraiment compliquées.
Rwong
35
Therefore, the one thing recursion can do that loops can't is make some tasks super easy. Et la seule chose que les boucles peuvent faire que la récursivité ne peut pas faire, c'est de rendre certaines tâches super faciles. Avez-vous vu les choses laides et non intuitives que vous devez faire pour transformer les problèmes les plus naturels en itération d'une récurrence naïve en récurrence de la queue afin qu'ils ne fassent pas exploser?
Mason Wheeler
10
@MasonWheeler 99% du temps, ces "choses" peuvent être mieux encapsulées dans un opérateur de récursivité tel que mapou fold(en fait, si vous choisissez de les considérer comme des primitives, je pense que vous pouvez utiliser fold/ en unfoldtant que troisième alternative aux boucles ou à la récursivité). Sauf si vous écrivez du code de bibliothèque, les cas où vous devriez vous inquiéter de la mise en œuvre de l'itération sont rares, plutôt que la tâche qu'elle est censée accomplir - dans la pratique, cela signifie que les boucles explicites et la récursivité explicite sont également médiocres. des abstractions à éviter au plus haut niveau.
Leushenko
7
Vous pouvez comparer deux chaînes en comparant de manière récursive des sous-chaînes, mais en comparant chaque caractère, un par un, jusqu'à ce que vous obteniez une discordance, vous obtiendrez de meilleures performances et serez plus clair pour le lecteur.
Steven Burnap
78

Non.

Raffinons les mêmes bases des minimums nécessaires pour calculer, il suffit d'être en mesure de boucler (cela seul ne suffit pas, mais est un élément nécessaire). Peu importe comment .

Tout langage de programmation pouvant implémenter une machine de Turing s'appelle Turing complete . Et il y a beaucoup de langues qui sont très complètes.

Ma langue préférée dans la voie en bas de "cela fonctionne réellement?" La complétude est celle de FRACTRAN , qui est complète . Il a une structure en boucle et vous pouvez y implémenter une machine de Turing. Ainsi, tout ce qui est calculable peut être implémenté dans un langage sans récursivité. Par conséquent, il n'y a rien que la récursivité puisse vous apporter en termes de calculabilité, ce qu'un simple bouclage ne peut pas.

Cela se résume vraiment à quelques points:

  • Tout ce qui est calculable est calculable sur une machine de Turing
  • Toute langue pouvant implémenter une machine de Turing (appelée Turing complete), peut calculer tout ce que toute autre langue peut
  • Comme il y a des machines de Turing dans les langues qui manquent récursion (et il y a d' autres qui n'ont récursion quand vous entrez dans quelques - uns des autres esolangs), il est nécessairement vrai qu'il n'y a rien que vous pouvez faire avec récursion que vous ne pouvez pas faire avec boucle (et rien que vous ne puissiez faire avec une boucle que vous ne pouvez pas faire avec la récursion).

Cela ne veut pas dire qu'il existe certaines classes problématiques qu'il est plus facile de penser à la récursion plutôt qu'à la boucle, ou à la boucle plutôt qu'à la récursion. Cependant, ces outils sont également puissants.

Et bien que je porte cela à l'extrême «esolang» (principalement parce que vous pouvez trouver des éléments complets et implémentés de Turing de manière plutôt étrange), cela ne signifie pas pour autant que les esolangs sont facultatifs. Il existe toute une liste de choses qui sont accidentellement terminées par Turing, y compris Magic the Gathering, Sendmail, les modèles MediaWiki et le système de types Scala. Beaucoup d'entre eux sont loin d'être optimaux lorsqu'il s'agit de faire quelque chose de concret, c'est juste que vous pouvez calculer tout ce qui est calculable en utilisant ces outils.


Cette équivalence peut devenir particulièrement intéressante lorsque vous entrez dans un type particulier de récursivité appelé appel final .

Si vous avez, disons, une méthode factorielle écrite comme suit:

int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

Ce type de récursivité sera réécrit sous forme de boucle - aucune pile utilisée. Ces approches sont en effet souvent plus élégantes et plus faciles à comprendre que la boucle équivalente écrite, mais encore une fois, pour chaque appel récursif, il peut exister une boucle équivalente et pour chaque boucle, un appel récursif est écrit.

Il arrive aussi que la conversion de la boucle simple en appel final soit récursive et plus difficile à comprendre.


Si vous voulez entrer dans la théorie, consultez la thèse de Church Turing . Vous pouvez également trouver utile la thèse de l' église-turing sur CS.SE.

Communauté
la source
29
La complétude turing est jetée autour trop comme il importe. Beaucoup de choses sont Turing Complete ( comme Magic the Gathering ), mais cela ne signifie pas que c'est la même chose que quelque chose d'autre qui s'appelle Turing Complete. Du moins pas à un niveau qui compte. Je ne veux pas marcher dans un arbre avec Magic the Gathering.
Scant Roger
7
Une fois que vous pouvez réduire un problème à "cela a la même puissance qu'une machine de Turing", il suffit de le résoudre. Les machines de Turing sont un obstacle assez bas, mais c'est tout ce qui est nécessaire. Il n'y a rien qu'une boucle puisse faire que la récursivité ne puisse faire, ni l'inverse.
4
La déclaration faite dans cette réponse est bien sûr correcte, mais j'ose dire que l'argument n'est pas vraiment convaincant. Les machines Turing n'ont pas de concept direct de récursivité. Par conséquent, dire «vous pouvez simuler une machine de Turing sans récursivité» ne prouve vraiment rien. Pour prouver cette affirmation, vous devez montrer que les machines de Turing peuvent simuler la récursivité. Si vous ne le montrez pas, vous devez présumer fidèlement que l'hypothèse Church-Turing est également valable pour la récursion (ce qui est le cas), mais le PO l'a mis en doute.
5gon12eder
10
La question du PO est "peut", pas "meilleur", "le plus efficacement possible" ou un autre qualificatif. "Turing Complete" signifie que tout ce qui peut être fait avec la récursion peut également être fait avec une boucle. Que ce soit la meilleure façon de le faire dans une mise en œuvre linguistique donnée est une question totalement différente.
Steven Burnap
7
"Can" n’est vraiment pas la même chose que "meilleur". Lorsque vous confondez "pas mieux" avec "ne peut pas", vous devenez paralysé, car peu importe la façon dont vous faites quelque chose, il y a presque toujours un meilleur moyen.
Steven Burnap
31

Existe-t-il des cas où une tâche ne peut être effectuée qu’en utilisant la récursion plutôt qu’une boucle?

Vous pouvez toujours transformer un algorithme récursif en une boucle, qui utilise une structure de données Last-In-First-Out (pile AKA) pour stocker un état temporaire, car l'appel récursif est exactement ce qu'il est, stocker l'état actuel dans une pile puis plus tard restaurer l'état. La réponse est si courte: non, il n’ya pas de tels cas .

Cependant, un argument peut être avancé pour "oui". Prenons un exemple concret et simple: le tri par fusion. Vous devez diviser les données en deux parties, fusionner, trier les parties, puis les combiner. Même si vous ne faites pas un appel de fonction de langage de programmation pour fusionner le tri afin de le faire sur les pièces, vous devez implémenter une fonctionnalité identique à celle utilisée pour effectuer un appel de fonction (envoi de l'état à votre propre pile, saut vers début de boucle avec différents paramètres de départ, puis enlevez plus tard l’état de votre pile).

S'agit-il d'une récursion, si vous implémentez l'appel vous-même, en tant qu'étapes séparées "push state" et "jump to begin" et "pop state"? Et la réponse à cette question est la suivante: non, ce n’est toujours pas appelé récursivité, c’est une itération avec pile explicite (si vous souhaitez utiliser la terminologie établie).


Notez que cela dépend aussi de la définition de "tâche". Si la tâche est à trier, vous pouvez le faire avec de nombreux algorithmes, dont beaucoup n’ont pas besoin de récursion. Si tâche consiste à implémenter un algorithme spécifique, tel que le tri par fusion, l'ambiguïté ci-dessus s'applique.

Examinons donc la question: existe-t-il des tâches générales pour lesquelles il n’existe que des algorithmes de type récursivité? De commentaire de @WizardOfMenlo sous la question, la fonction Ackermann est un exemple simple de cela. Ainsi, le concept de récursivité est autonome, même s'il peut être implémenté avec une construction de programme informatique différente (itération avec pile explicite).

Hyde
la source
2
Lorsqu'il s'agit d'un assemblage pour un processeur sans pile, ces deux techniques ne font plus qu'un.
Josué
@ Josué En effet! C'est une question de niveau d'abstraction. Si vous montez un niveau ou deux plus bas, ce ne sont que des portes logiques.
Hyde
2
Ce n'est pas tout à fait correct. Pour émuler la récursivité avec itération, vous avez besoin d'une pile où un accès aléatoire est possible. Une seule pile sans accès aléatoire plus une quantité finie de mémoire directement accessible serait un PDA, qui n'est pas complet.
Gilles
@Gilles Old Post, mais pourquoi une pile d'accès aléatoire est-elle nécessaire? En outre, tous les ordinateurs réels ne sont-ils pas encore plus petits que les PDA, car ils ne disposent que d'une quantité limitée de mémoire directement accessible, et d'aucune pile (sauf en utilisant cette mémoire)? Cela ne semble pas une abstraction très pratique, si on dit "nous ne pouvons pas faire de récursion dans la réalité".
Hyde
20

Cela dépend de la rigueur avec laquelle vous définissez "récursivité".

Si nous exigeons strictement que la pile d'appels soit impliquée (ou quel que soit le mécanisme utilisé pour maintenir l'état du programme), nous pouvons toujours le remplacer par quelque chose qui ne le fait pas. En effet, les langages qui conduisent naturellement à un usage intensif de la récursivité ont tendance à avoir des compilateurs qui font un usage intensif de l'optimisation de l'appel final, de sorte que ce que vous écrivez est récursif mais que vous exécutez est itératif.

Mais prenons le cas où nous effectuons un appel récursif et utilisons le résultat d'un appel récursif pour cet appel récursif.

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Rendre le premier appel récursif itératif est facile:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Nous pouvons ensuite nettoyer enlever le gotopour éviter les vélociraptors et l'ombre de Dijkstra:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

Mais pour supprimer les autres appels récursifs, nous allons devoir stocker les valeurs de certains appels dans une pile:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

Maintenant, quand nous considérons le code source, nous avons certainement transformé notre méthode récursive en une méthode itérative.

Compte tenu de ce qui a été compilé, nous avons transformé le code qui utilise la pile d'appels pour implémenter la récursivité dans le code qui ne fonctionne pas (et ce faisant, nous avons transformé le code qui lève une exception de débordement de pile pour des valeurs même très petites dans un code qui se contente de prendre un temps pour revenir longtemps atrocement [voir Comment puis - je empêcher ma fonction Ackerman de déborder la pile? quelques autres qui font optimisations le retourner en fait pour beaucoup plus entrées possibles]).

Considérant la manière dont la récursivité est généralement implémentée, nous avons transformé le code qui utilise la pile d'appels en code utilisant une pile différente pour contenir les opérations en attente. Nous pourrions donc affirmer qu'il est toujours récursif, à ce niveau bas.

Et à ce niveau, il n'y a en effet pas d'autre moyen de le contourner. Donc, si vous considérez que cette méthode est récursive, il y a en effet des choses que nous ne pouvons pas faire sans. Généralement, nous n'indiquons pas ce code récursif. Le terme récursion est utile car il recouvre un certain ensemble d’approches et nous permet d’en parler, et nous n’utilisons plus l’une d’elles.

Bien sûr, tout cela suppose que vous avez le choix. Il existe des langues interdisant les appels récursifs et des langues dépourvues des structures de boucle nécessaires à l'itération.

Jon Hanna
la source
Il est uniquement possible de remplacer la pile d'appels par quelque chose d'équivalent si la pile d'appels est liée ou si on a accès à une mémoire illimitée en dehors de la pile d'appels. Il existe une classe importante de problèmes qui peuvent être résolus par des automates à pile enfoncée qui ont une pile d'appels illimitée mais ne peuvent avoir qu'un nombre fini d'états autrement.
Supercat
C'est la meilleure réponse, peut-être la seule réponse correcte. Même le deuxième exemple est toujours récursif et, à ce niveau, la réponse à la question initiale est non . Avec une définition plus large de la récursivité, la récursivité pour la fonction Ackermann est impossible à éviter.
gerrit
@ gerrit et avec un plus étroit, il l’évite. En fin de compte, tout ce que nous faisons ou ne appliquons pas cette étiquette utile que nous utilisons pour certains codes est étroitement lié.
Jon Hanna
1
J'ai rejoint le site pour voter. La fonction Ackermann / est / récursive par nature. L'implémentation d'une structure récursive avec une boucle et une pile n'en fait pas une solution itérative, vous venez de déplacer la récursivité dans l'espace utilisateur.
Aaron McMillin
9

La réponse classique est "non", mais permettez-moi d'expliquer pourquoi je pense que "oui" est une meilleure réponse.


Avant de continuer, passons à autre chose: du point de vue de la calculabilité et de la complexité:

  • La réponse est "non" si vous êtes autorisé à avoir une pile auxiliaire lors de la mise en boucle.
  • La réponse est "oui" si aucune donnée supplémentaire ne vous est autorisée lors de la mise en boucle.

Ok, maintenant, mettons un pied dans la pratique, gardons l'autre pied dans la théorie.


La pile d'appels est une structure de contrôle , tandis qu'une pile manuelle est une structure de données . Contrôle et données ne sont pas des concepts égaux, mais ils sont équivalents en ce sens qu'ils peuvent être réduits l'un à l'autre (ou "émulés" l'un par l'autre) du point de vue de la calculabilité ou de la complexité.

Quand cette distinction pourrait-elle avoir de l'importance? Lorsque vous travaillez avec des outils du monde réel. Voici un exemple:

Supposons que vous implémentez N-way mergesort. Vous pouvez avoir une forboucle qui parcourt chacun des Nsegments, les appelle mergesortséparément, puis fusionne les résultats.

Comment pourriez-vous paralléliser cela avec OpenMP?

Dans le domaine récursif, c'est extrêmement simple: il suffit de placer #pragma omp parallel forvotre boucle qui va de 1 à N et vous avez terminé. Dans le domaine itératif, vous ne pouvez pas faire cela. Vous devez créer manuellement des threads et leur transmettre manuellement les données appropriées afin qu'ils sachent quoi faire.

D'autre part, il existe d'autres outils (tels que les vectoriseurs automatiques, par exemple #pragma vector) qui fonctionnent avec des boucles mais qui sont totalement inutiles avec une récursion.

Le fait que les deux paradigmes soient équivalents sur le plan mathématique ne signifie pas qu’ils soient égaux dans la pratique. Un problème qui pourrait être banal à automatiser dans un paradigme (disons, la parallélisation de boucle) pourrait être beaucoup plus difficile à résoudre dans l'autre paradigme.

C'est-à-dire que les outils d'un paradigme ne se traduisent pas automatiquement par d'autres paradigmes.

Par conséquent, si vous avez besoin d'un outil pour résoudre un problème, il est probable qu'il ne fonctionnera qu'avec un type d'approche particulier. Par conséquent, vous ne pourrez pas résoudre le problème avec une approche différente, même si vous pouvez prouver mathématiquement que le problème peut être résolu de toute façon.

Mehrdad
la source
Même au-delà, considérons que l’ensemble des problèmes pouvant être résolus avec un automate à pile est plus grand que celui qui peut être résolu avec un automate fini (qu’il soit déterministe ou non) mais plus petit que celui qui peut être résolu avec un automate fini. Machine de turing.
Supercat
8

Laissant de côté le raisonnement théorique, examinons la récursivité et les boucles du point de vue de la machine (matérielle ou virtuelle). La récursivité est une combinaison de flux de contrôle qui permet de démarrer l’exécution de certains codes et de revenir à l’achèvement (dans une vue simpliste lorsque les signaux et les exceptions sont ignorés) et de données transmises à cet autre code (arguments) et renvoyées par le (résultat). Habituellement, aucune gestion de mémoire explicite n’est impliquée. Cependant, il existe une allocation implicite de mémoire de pile pour enregistrer les adresses de retour, les arguments, les résultats et les données locales intermédiaires.

Une boucle est une combinaison de flux de contrôle et de données locales. En comparant cela à la récursivité, nous pouvons constater que la quantité de données dans ce cas est fixe. Le seul moyen de dépasser cette limitation consiste à utiliser une mémoire dynamique (également appelée tas ) pouvant être allouée (et libérée) à tout moment.

Résumer:

  • Cas de récursivité = flux de contrôle + pile (+ tas)
  • Boucle de cas = flux de contrôle + tas

En supposant que la partie flux de contrôle soit raisonnablement puissante, la seule différence réside dans les types de mémoire disponibles. Il nous reste donc 4 cas (le pouvoir d’expressivité est indiqué entre parenthèses):

  1. Pas de pile, pas de tas: la récurrence et les structures dynamiques sont impossibles. (récursivité = boucle)
  2. Stack, no heap: la récursion est correcte, les structures dynamiques sont impossibles. (récursivité> boucle)
  3. Pas de pile, tas: la récursion est impossible, les structures dynamiques sont OK. (récursivité = boucle)
  4. Stack, heap: la récursivité et les structures dynamiques sont acceptables. (récursivité = boucle)

Si les règles du jeu sont un peu plus strictes et que l'implémentation récursive n'est pas autorisée à utiliser des boucles, nous obtenons plutôt ceci:

  1. Pas de pile, pas de tas: la récurrence et les structures dynamiques sont impossibles. (récursivité <boucle)
  2. Stack, no heap: la récursion est correcte, les structures dynamiques sont impossibles. (récursivité> boucle)
  3. Pas de pile, tas: la récursion est impossible, les structures dynamiques sont OK. (récursivité <boucle)
  4. Stack, heap: la récursivité et les structures dynamiques sont acceptables. (récursivité = boucle)

La principale différence avec le scénario précédent est que le manque de mémoire de pile ne permet pas à la récursivité sans boucles de faire plus d’étapes lors de l’exécution qu’il n’ya de lignes de code.

Alexander Kogtenkov
la source
2

Oui. Il existe plusieurs tâches courantes faciles à accomplir à l'aide de la récursivité, mais impossibles avec de simples boucles:

  • Causer des débordements de pile.
  • Programmeurs débutants totalement déroutants.
  • Créer des fonctions rapides qui sont réellement O (n ^ n).
jpa
la source
3
S'il vous plaît, ce sont vraiment faciles avec des boucles, je les vois tout le temps. Heck, avec un peu d'effort, vous n'avez même pas besoin de boucles. Même si la récursion est plus facile.
AviD
1
en réalité, A (0, n) = n + 1; A (m, 0) = A (m-1,1) si m> 0; A (m, n) = A (m-1, A (m, n-1)) si m> 0, n> 0 croît même un peu plus vite que O (n ^ n) (pour m = n) :)
John Donn
1
@JohnDonn Plus qu'un peu, c'est super exponentiel. pour n = 3 n ^ n ^ n pour n = 4 n ^ n ^ n ^ n ^ n et ainsi de suite. n à n puissance n fois.
Aaron McMillin
1

Il y a une différence entre les fonctions récursives et les fonctions récursives primitives. Les fonctions récursives primitives sont celles qui sont calculées à l'aide de boucles, où le nombre maximal d'itérations de chaque boucle est calculé avant le début de l'exécution de la boucle. (Et "récursif" ici n'a rien à voir avec l'utilisation de la récursivité).

Les fonctions récursives primitives sont strictement moins puissantes que les fonctions récursives. Vous obtiendriez le même résultat si vous utilisiez des fonctions qui utilisent la récursivité, pour lesquelles la profondeur maximale de la récursivité doit être calculée à l’avance.

gnasher729
la source
3
Je ne suis pas sûr de savoir comment cela s'applique à la question ci-dessus? Pouvez-vous s'il vous plaît rendre ce lien plus clair?
Yakk
1
Remplacement de la « boucle » imprécise avec la distinction importante entre « boucle avec nombre d'itérations limitée » et « boucle avec nombre d'itérations illimité », que je pensais que tout le monde sache de CS 101.
gnasher729
bien sûr, mais cela ne s'applique toujours pas à la question. La question concerne les boucles et la récursivité, et non les récursions et primitives primitives. Imaginez que quelqu'un pose des questions sur les différences C / C ++ et que vous répondiez sur la différence entre K & R C et Ansi C. Bien sûr, cela clarifie les choses, mais cela ne répond pas à la question.
Yakk
1

Si vous programmez en c ++ et utilisez c ++ 11, il y a une chose à faire à l'aide des récurrences: les fonctions constexpr. Mais la norme limite cela à 512, comme expliqué dans cette réponse . L'utilisation de boucles dans ce cas n'est pas possible, car dans ce cas, la fonction ne peut pas être constexpr, mais elle est modifiée dans c ++ 14.

BЈовић
la source
0
  • Si l'appel récursif est la toute première ou la dernière déclaration (à l'exclusion de la vérification de condition) d'une fonction récursive, il est assez facile de le traduire en une structure en boucle.
  • Mais si la fonction effectue d'autres opérations avant et après l'appel récursif , il serait alors fastidieux de la convertir en boucles.
  • Si la fonction a plusieurs appels récursifs, la conversion en code utilisant uniquement des boucles sera quasiment impossible. Un peu de pile sera nécessaire pour suivre les données. En récursion, la pile d'appels elle-même fonctionnera comme la pile de données.
Gulshan
la source
L'arborescence a plusieurs appels récursifs (un pour chaque enfant), mais elle est transformée de manière triviale en une boucle utilisant une pile explicite. Les analyseurs, par contre, sont souvent agaçants à transformer.
CodesInChaos
@CodesInChaos Edité.
Gulshan
-6

Je suis d'accord avec les autres questions. Vous ne pouvez rien faire avec la récursion avec une boucle.

MAIS , à mon avis, la récursivité peut être très dangereuse. Premièrement, pour certains, il est plus difficile de comprendre ce qui se passe réellement dans le code. Deuxièmement, au moins pour C ++ (Java je ne suis pas sûr), chaque étape de la récursion a un impact sur la mémoire car chaque appel de méthode provoque une accumulation de mémoire et l'initialisation de l'en-tête de méthodes. De cette façon, vous pouvez faire exploser votre pile. Essayez simplement la récursion des nombres de Fibonacci avec une valeur d'entrée élevée.

Ben1980
la source
2
Une implémentation récursive naïve des nombres de Fibonacci avec récursion fonctionnera "hors du temps" avant de manquer d'espace dans la pile. Je suppose qu'il y a d'autres problèmes qui sont meilleurs pour cet exemple. En outre, pour de nombreux problèmes, une version de boucle a le même impact sur la mémoire qu'un modèle récursif, juste sur le tas au lieu de la pile (si votre langage de programmation les distingue).
Paŭlo Ebermann
6
La boucle peut aussi être "très dangereuse" si vous oubliez simplement d'incrémenter la variable de boucle ...
h22
2
Ainsi, produire délibérément un débordement de pile est une tâche qui devient très délicate sans recourir à la récursivité.
5gon12eder
@ 5gon12eder qui nous amène à Quelles méthodes sont là pour éviter un débordement de pile dans un algorithme récursif? - écrire pour engager TCO, ou mémo peut être utile. Les approches itérative vs récursive sont également intéressantes car elles traitent de deux approches récursives différentes pour Fibonacci.
1
La plupart du temps, si vous rencontrez un débordement de pile lors de la récursivité, vous aurez un blocage de la version itérative. Au moins le premier jette avec une trace de pile.
Jon Hanna