Une boucle while est-elle intrinsèquement une récursivité?

Je me suis demandé si une boucle while est intrinsèquement une récursivité?

Je pense que c’est parce qu’une boucle while peut être vue comme une fonction qui s’appelle à la fin. Si ce n'est pas la récursivité, alors quelle est la différence?

Les boucles ne sont vraiment pas récursives. En fait, ils sont le meilleur exemple du mécanisme opposé : l' itération .

L'intérêt de la récursivité est qu'un élément du traitement appelle une autre instance d'elle-même. Le mécanisme de contrôle de boucle simple saute jusqu'au point où il a commencé.

Sauter dans le code et appeler un autre bloc de code sont des opérations différentes. Par exemple, lorsque vous sautez au début de la boucle, la variable de contrôle de la boucle a toujours la même valeur qu’avant le saut. Mais si vous appelez une autre instance de la routine dans laquelle vous vous trouvez, la nouvelle instance dispose de nouvelles copies non liées de toutes ses variables. Effectivement, une variable peut avoir une valeur au premier niveau de traitement et une autre valeur à un niveau inférieur.

Cette fonctionnalité est cruciale pour le fonctionnement de nombreux algorithmes récursifs. C'est pourquoi vous ne pouvez pas émuler la récursivité par itération sans gérer également une pile de trames appelées qui garde toutes ces valeurs.

Dire que X est intrinsèquement Y n'a de sens que si vous avez un système (formel) à l'esprit que vous exprimez X en. Si vous définissez la sémantique de whilelambda calcul, vous pouvez mentionner récursion *; si vous le définissez en termes de machine à enregistrer, vous ne le ferez probablement pas.

Dans les deux cas, les gens ne vous comprendront probablement pas si vous appelez une fonction récursive simplement parce qu'elle contient une boucle while.

* Bien que peut-être seulement indirectement, par exemple si vous le définissez en termes de fold.

Cela dépend de votre point de vue.

Si vous examinez la théorie de la calculabilité , l'itération et la récursivité sont également expressives . Cela signifie que vous pouvez écrire une fonction qui calcule quelque chose, et que vous le fassiez de manière récursive ou itérative, vous pourrez choisir les deux approches. Il n'y a rien que vous puissiez calculer récursivement qui ne puisse être calculé de manière itérative et inversement (bien que le fonctionnement interne du programme puisse être différent).

De nombreux langages de programmation ne traitent pas la récursivité et l'itération de la même manière et pour une bonne raison. En règle générale , la récursivité signifie que le langage / le compilateur gère la pile d'appels et l'itération signifie que vous devrez peut-être gérer vous-même la pile.

Cependant, il existe des langages - en particulier des langages fonctionnels - dans lesquels des choses comme les boucles (pour, tandis que) ne sont en effet que du sucre syntaxique pour la récursion et sont implémentées en coulisse de cette façon. C'est souvent souhaitable dans les langages fonctionnels, car ils n'ont généralement pas le concept de bouclage, et l'ajouter rendrait leur calcul plus complexe, pour une raison peu pratique.

Donc non, ils ne sont pas intrinsèquement les mêmes . Ils sont également expressifs , ce qui signifie que vous ne pouvez pas calculer quelque chose de manière itérative, ni de manière récursive ni inversement, mais c'est à peu près tout, dans le cas général (selon la thèse de Church-Turing).

Notez que nous parlons ici de programmes récursifs . Il existe d'autres formes de récursivité, par exemple dans les structures de données (par exemple, les arbres).

Si vous le regardez du point de vue de la mise en œuvre , récursivité et itération ne sont pratiquement plus les mêmes. La récursivité crée un nouveau cadre de pile pour chaque appel. Chaque étape de la récursivité est autonome, les arguments du calcul étant obtenus par l'appelé (lui-même).

Les boucles d’autre part ne créent pas de cadres d’appel. Pour eux, le contexte n'est pas préservé à chaque étape. Pour la boucle, le programme revient simplement au début de la boucle jusqu'à ce que la condition de la boucle échoue.

C'est très important à savoir, car cela peut faire des différences assez radicales dans le monde réel. Pour la récursivité, le contexte entier doit être sauvegardé à chaque appel. Pour l'itération, vous avez un contrôle précis sur les variables en mémoire et sur ce qui est enregistré.

Si vous le regardez ainsi, vous voyez rapidement que pour la plupart des langues, l'itération et la récursivité sont fondamentalement différentes et ont des propriétés différentes. Selon la situation, certaines propriétés sont plus souhaitables que d’autres.

Récursivité peut rendre les programmes plus simples et plus faciles à tester et la preuve . La conversion d'une récursion en itération rend généralement le code plus complexe, ce qui augmente les risques d'échec. D'autre part, la conversion en itération et la réduction du nombre de trames de la pile d'appels peuvent économiser beaucoup de mémoire.

La différence réside dans la pile implicite et la sémantique.

Une boucle while qui "s'appelle elle-même à la fin" n'a pas de pile à explorer lorsque c'est fait. C'est la dernière itération qui définit l'état final.

La récursivité ne peut cependant pas être réalisée sans cette pile implicite qui se souvient de l’état du travail effectué auparavant.

Il est vrai que vous pouvez résoudre tout problème de récursion par itération si vous lui donnez explicitement accès à une pile. Mais le faire de cette façon n'est pas la même.

La différence sémantique tient au fait que regarder du code récursif transmet une idée de manière complètement différente du code itératif. Le code itératif fait les choses une étape à la fois. Il accepte n'importe quel état d'avant et ne travaille que pour créer l'état suivant.

Le code récursif divise un problème en fractales. Cette petite partie ressemble à cette grosse partie pour que nous puissions en faire un peu et le faire de la même manière. C'est une façon différente de penser aux problèmes. C'est très puissant et il faut s'y habituer. On peut dire beaucoup de choses en quelques lignes. Vous ne pouvez tout simplement pas sortir de cette boucle, même s'il a accès à une pile.

Tout dépend de votre utilisation du terme intrinsèquement . Au niveau du langage de programmation, ils sont syntaxiquement et sémantiquement différents, et leurs performances et leur utilisation de la mémoire sont très différentes. Mais si vous creusez suffisamment dans la théorie, ils peuvent être définis en termes les uns des autres, et sont donc "les mêmes" dans un sens théorique.

La vraie question est la suivante: quand faut-il faire la distinction entre itération (boucles) et récursion, et quand est-il utile de penser que c'est la même chose? La réponse est que lors de la programmation (par opposition à l'écriture d'épreuves mathématiques), il est important de faire la distinction entre itération et récursivité.

La récursivité crée un nouveau cadre de pile, c'est-à-dire un nouvel ensemble de variables locales pour chaque appel. Cela entraîne une surcharge et prend de la place sur la pile, ce qui signifie qu'une récursion suffisamment profonde peut déborder de la pile, ce qui provoque le blocage du programme. D'autre part, l'itération ne modifie que les variables existantes, elle est donc généralement plus rapide et ne nécessite qu'une quantité de mémoire constante. C'est donc une distinction très importante pour un développeur!

Dans les langues avec récursivité d'appels (généralement des langages fonctionnels), le compilateur peut optimiser les appels récursifs de manière à ne prendre qu'une quantité de mémoire constante. Dans ces langues, la distinction importante n’est pas l’itération contre la récursivité, mais bien la version non-tail-call-récursive-call-récursion.

En bout de ligne: Vous devez être capable de faire la différence, sinon votre programme plantera.

whileles boucles sont une forme de récursivité, voir par exemple la réponse acceptée à cette question . Ils correspondent à l'opérateur μ dans la théorie de la calculabilité (voir par exemple ici ).

Toutes les variantes de forboucles qui itèrent sur une plage de nombres, une collection finie, un tableau, etc., correspondent à une récursion primitive, voir par exemple ici et ici . Notez que les forboucles de C, C ++, Java, etc. constituent en réalité un sucre syntaxique pour une whileboucle et que, par conséquent, elles ne correspondent pas à la récursion primitive. La forboucle Pascal est un exemple de récursion primitive.

Une différence importante est que la récursion primitive se termine toujours, alors que la récursion généralisée ( whileboucles) peut ne pas se terminer.

MODIFIER

Quelques clarifications concernant les commentaires et autres réponses. "La récursivité se produit lorsqu'une chose est définie en termes d'elle-même ou de son type." (voir wikipedia ). Alors,

Une boucle while est-elle intrinsèquement une récursivité?

Puisque vous pouvez définir une whileboucle en tant que telle

while p do c := if p then (c; while p do c))

alors, oui , une whileboucle est une forme de récursion. Les fonctions récursives sont une autre forme de récursivité (un autre exemple de définition récursive). Les listes et les arbres sont d'autres formes de récursivité.

Une autre question implicitement supposée par de nombreuses réponses et commentaires est

Les boucles while et les fonctions récursives sont-elles équivalentes?

La réponse à cette question est non : une whileboucle correspond à une fonction queue récursive, où les variables auxquelles la boucle a accès correspondent aux arguments de la fonction récursive implicite, mais, comme d'autres l'ont souligné, des fonctions non récursives ne peut pas être modélisé par une whileboucle sans utiliser une pile supplémentaire.

Ainsi, le fait "qu'une whileboucle soit une forme de récursion" ne contredit pas le fait que "certaines fonctions récursives ne peuvent pas être exprimées par une whileboucle".

Un appel final (ou appel récursif) est implémenté exactement comme un "goto avec arguments" (sans pousser de trame d'appel supplémentaire sur la pile d'appels ) et dans certains langages fonctionnels (notamment Ocaml) est la méthode habituelle de bouclage.

Ainsi, une boucle while (dans les langues qui les ont) peut être vue comme se terminant par un appel de queue à son corps (ou à son test de la tête).

De même, les appels récursifs ordinaires (sans appel final) peuvent être simulés par des boucles (en utilisant une pile).

Lisez aussi sur les continuations et le style de continuation-passant .

Donc, "récursion" et "itération" sont profondément équivalents.

Il est vrai que la récursion et la boucle while sans bornes sont équivalentes en termes d’expressivité de calcul. Autrement dit, tout programme écrit de manière récursive peut être réécrit en un programme équivalent en utilisant des boucles, et inversement. Les deux approches sont complètes , c'est-à-dire qu'elles peuvent être utilisées pour calculer toute fonction calculable.

La différence fondamentale en termes de programmation est que la récursivité vous permet d'utiliser les données stockées dans la pile d'appels. Pour illustrer cela, supposons que vous souhaitiez imprimer les éléments d'une liste à lien unique en utilisant une boucle ou une récursivité. Je vais utiliser C pour l'exemple de code:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Simple, non? Faisons maintenant une légère modification: Imprimez la liste dans l’ordre inverse.

Pour la variante récursive, il s’agit d’une modification presque triviale de la fonction originale:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Pour la fonction de boucle cependant, nous avons un problème. Notre liste est liée individuellement et ne peut donc être parcourue que vers l’avant. Mais comme nous imprimons en sens inverse, nous devons commencer à imprimer le dernier élément. Une fois que nous avons atteint le dernier élément, nous ne pouvons plus revenir à l’avant-dernier élément.

Nous devons donc soit procéder à de nombreuses ré-traverses, soit créer une structure de données auxiliaire qui assure le suivi des éléments visités et à partir de laquelle nous pouvons ensuite imprimer efficacement.

Pourquoi n'avons-nous pas ce problème de récursivité? Parce que dans la récursivité, nous avons déjà une structure de données auxiliaire en place: la pile d'appels de fonction.

Comme la récursivité nous permet de revenir à l'appel précédent de l'appel récursif, toutes les variables locales et l'état de cet appel restant intacts, nous bénéficions d'une certaine souplesse qu'il serait fastidieux de modéliser dans le cas itératif.

Les boucles sont une forme spéciale de récursivité permettant d’accomplir une tâche spécifique (principalement une itération). On peut implémenter une boucle dans un style récursif avec la même performance [1] dans plusieurs langues. et dans le SICP [2], vous pouvez voir que les boucles sont décrites comme "sucre syntastique". Dans la plupart des langages de programmation impératifs, les blocs for et while utilisent la même portée que leur fonction parent. Néanmoins, dans la plupart des langages de programmation fonctionnels, il n’existe pas de boucles for, ni de boucles, car elles ne sont pas nécessaires.

La raison pour laquelle les langages impératifs ont des boucles for / while est qu’ils gèrent les états en les migrant. Mais en réalité, si vous regardez sous un angle différent, si vous pensez à un bloc while comme une fonction elle-même, prenez paramètre, traitez-le et renvoyez un nouvel état - qui pourrait aussi bien être l’appel de la même fonction avec des paramètres différents -. peut penser à la boucle comme une récursion.

Le monde pourrait également être défini comme mutable ou immuable. si nous définissons le monde comme un ensemble de règles et appelons une fonction ultime qui prend toutes les règles et l’état actuel en tant que paramètres et renvoie le nouvel état en fonction de ces paramètres, qui a la même fonctionnalité (génère le suivant dans le même état) On pourrait aussi bien dire que c’est une récursion et une boucle.

dans l'exemple suivant, la vie est la fonction prend deux paramètres "règles" et "état", et nouvel état sera construit dans la prochaine tick de temps.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: L’optimisation d’appel en aval est une optimisation courante dans les langages de programmation fonctionnels consistant à utiliser la pile de fonctions existante dans des appels récursifs au lieu de créer un nouveau.

[2]: Structure et interprétation des programmes informatiques, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

Une boucle while est différente de la récursivité.

Lorsqu'une fonction est appelée, les opérations suivantes ont lieu:

1. Un cadre de pile est ajouté à la pile.

2. Le pointeur de code se déplace au début de la fonction.

Quand une boucle while est à la fin, ceci se produit:

1. Une condition demande si quelque chose est vrai.

2. Si c'est le cas, le code saute à un point.

En général, la boucle while s'apparente au pseudocode suivant:

 if (x)

 {

      Jump_to(y);

 }

Le plus important de tous, la récursivité et les boucles ont différentes représentations du code d'assemblage et des représentations du code machine. Cela signifie qu'ils ne sont pas les mêmes. Ils peuvent avoir les mêmes résultats, mais le code machine différent prouve qu'ils ne sont pas 100% identiques.

Une simple itération est insuffisante pour être généralement équivalente à une récursivité, mais une itération avec une pile est généralement équivalente. Toute fonction récursive peut être reprogrammée en tant que boucle itérative avec une pile et inversement. Cela ne signifie toutefois pas que ce soit pratique, cependant, et dans toute situation particulière, l’une ou l’autre des formes peut présenter des avantages évidents par rapport à l’autre version.

Je ne sais pas pourquoi c'est controversé. La récursivité et l'itération avec une pile sont le même processus de calcul. Ils sont le même "phénomène", pour ainsi dire.

La seule chose à laquelle je peux penser, c'est que lorsque je considère ces outils comme des "outils de programmation", je conviens que vous ne devriez pas les considérer comme la même chose. Elles sont équivalentes "mathématiquement" ou "informatiquement" (encore une fois, itération avec une pile , pas itération en général), mais cela ne signifie pas que vous devriez aborder les problèmes avec la pensée que l'une ou l'autre fera. Du point de vue de la mise en œuvre et de la résolution de problèmes, certains problèmes peuvent mieux fonctionner, et votre travail en tant que programmeur consiste à déterminer correctement celui qui convient le mieux.

Pour clarifier, la réponse à la question Est-ce qu'une boucle while est intrinsèquement une récursion? est un non définitif , ou du moins "à moins que vous n'ayez également une pile".