La récursivité est-elle une caractéristique en soi?

… ou est-ce juste une pratique?

Je pose cette question à cause d’une dispute avec mon professeur: j’ai perdu le crédit d’avoir appelé une fonction de manière récursive, car nous ne couvrions pas la récursivité en classe et mon argument est que nous l’avons appris implicitement.

Je demande ici parce que je soupçonne que quelqu’un a une réponse définitive.

Par exemple, quelle est la différence entre les deux méthodes suivantes:

 public static void a() { return a(); } public static void b() { return a(); } 

En dehors de ” a continue forever” (dans le programme actuel, il est utilisé correctement pour inviter à nouveau un utilisateur lorsqu’il reçoit une entrée non valide), y a-t-il une différence fondamentale entre a et b ? Pour un compilateur non optimisé, comment sont-ils traités différemment?

En fin de compte, cela revient à savoir si, en apprenant à return a() de b , nous avons également appris à return a() de a . Avons-nous?

Pour répondre à votre question spécifique: Non, du sharepoint vue de l’apprentissage d’une langue, la récursivité n’est pas une caractéristique. Si votre professeur vous a vraiment arraché des points pour avoir utilisé une “fonctionnalité”, il ne l’avait pas encore enseigné, c’était faux.

En lisant entre les lignes, une possibilité est qu’en utilisant la récursivité, vous évitiez d’utiliser une fonctionnalité qui était censée être un résultat d’apprentissage pour son cours. Par exemple, vous n’avez peut-être jamais utilisé d’itération ou peut-être que vous avez utilisé for boucles au lieu d’utiliser les deux for et while . Il est fréquent qu’une mission vise à tester votre capacité à faire certaines choses, et si vous évitez de les faire, votre professeur ne peut tout simplement pas vous accorder les notes réservées pour cette fonction. Cependant, si cela était vraiment la cause de vos pertes de notes, le professeur devrait considérer cela comme une expérience d’apprentissage personnelle – si la démonstration de certains résultats d’apprentissage est l’un des critères d’une affectation, cela devrait être clairement expliqué aux étudiants. .

Cela dit, je suis d’accord avec la plupart des autres commentaires et répond que l’itération est un meilleur choix que la récursivité ici. Il y a plusieurs raisons, et alors que d’autres personnes les ont abordées dans une certaine mesure, je ne suis pas sûr qu’elles aient pleinement expliqué leur pensée.

Pile déborde

La plus évidente est que vous risquez d’obtenir une erreur de débordement de stack. En réalité, il est très peu probable que la méthode que vous avez écrite en conduise réellement à un, car un utilisateur devrait donner des entrées incorrectes plusieurs fois pour réellement déclencher un débordement de stack.

Cependant, une chose à garder à l’esprit est que non seulement la méthode elle-même, mais d’autres méthodes plus ou moins élevées dans la chaîne d’appels seront sur la stack. À cause de cela, engloutir avec désinvolture l’espace de stack disponible est une chose assez impolie pour toute méthode. Personne ne veut avoir à se soucier constamment de l’espace de stack libre à chaque fois qu’il écrit du code, car le risque que l’autre code en ait inutilement été utilisé risque d’être dépassé.

Cela fait partie d’un principe plus général de la conception de logiciels appelé abstraction. Essentiellement, lorsque vous appelez DoThing() , tout ce dont vous avez besoin, c’est que Thing soit terminé. Vous ne devriez pas avoir à vous soucier des détails d’implémentation de la façon dont cela est fait. Mais l’utilisation avide de la stack brise ce principe, car chaque bit de code doit s’inquiéter de la quantité de stack qu’il peut supposer en toute sécurité qu’il a laissé par code ailleurs dans la chaîne d’appels.

Lisibilité

L’autre raison est la lisibilité. L’idéal auquel le code devrait aspirer est d’être un document lisible par l’homme, où chaque ligne décrit simplement ce qu’elle fait. Prenez ces deux approches:

 private int getInput() { int input; do { input = promptForInput(); } while (!inputIsValid(input)) return input; } 

contre

 private int getInput() { int input = promptForInput(); if(inputIsValid(input)) { return input; } return getInput(); } 

Oui, ces deux fonctionnent, et oui, ils sont tous deux faciles à comprendre. Mais comment les deux approches pourraient-elles être décrites en anglais? Je pense que ce serait quelque chose comme:

Je vous demanderai de saisir jusqu’à ce que l’entrée soit valide, puis de la renvoyer

contre

Je vais vous demander d’entrer, puis si l’entrée est valide, je la renverrai, sinon je reçois l’entrée et renvoie le résultat à la place

Peut-être que vous pouvez penser à un libellé légèrement moins maladroit pour ce dernier, mais je pense que vous constaterez toujours que le premier sera une description plus précise, conceptuellement, de ce que vous essayez réellement de faire. Cela ne veut pas dire que la récursivité est toujours moins lisible. Pour les situations où elle brille, comme la traversée d’arbres, vous pouvez effectuer le même type d’parsing côte à côte entre la récursivité et une autre approche et vous constaterez certainement que la récursion donne un code plus clairement auto-descriptif, ligne par ligne.

En isolement, ces deux points sont petits. Il est très improbable que cela conduise à un débordement de stack, et le gain de lisibilité est minime. Mais tout programme va rassembler un grand nombre de ces petites décisions, alors même si, isolément, elles importent peu, il est important d’apprendre les principes qui sous-tendent les bonnes décisions.

Pour répondre à la question littérale, plutôt que la méta-question: la récursivité est une caractéristique, en ce sens que tous les compilateurs et / ou les langages ne le permettent pas nécessairement. En pratique, il est attendu de tous les compilateurs modernes – et certainement de tous les compilateurs Java! – mais ce n’est pas universellement vrai.

Comme exemple artificiel de la raison pour laquelle la récursivité pourrait ne pas être prise en charge, considérez un compilateur qui stocke l’adresse de retour pour une fonction dans un emplacement statique; Cela peut être le cas, par exemple, pour un compilateur pour un microprocesseur qui n’a pas de stack.

Pour un tel compilateur, lorsque vous appelez une fonction comme celle-ci

 a(); 

il est mis en œuvre comme

 move the address of label 1 to variable return_from_a jump to label function_a label 1 

et la définition d’un (),

 function a() { var1 = 5; return; } 

est mis en œuvre comme

 label function_a move 5 to variable var1 jump to the address stored in variable return_from_a 

Espérons que le problème lorsque vous essayez d’appeler a() récursivement dans un tel compilateur est évident; le compilateur ne sait plus comment renvoyer l’appel externe, car l’adresse de retour a été remplacée.

Pour le compilateur que j’ai effectivement utilisé (fin des années 70 ou début des années 80, je pense) sans support pour la récursivité, le problème était légèrement plus subtil que cela: l’adresse de retour serait stockée comme dans les compilateurs modernes, mais les variables locales ‘t. (Théoriquement, cela devrait signifier que la récursivité était possible pour les fonctions sans variables locales non statiques, mais je ne me souviens pas si le compilateur a explicitement supporté cela ou non. Il peut avoir besoin de variables locales implicites pour une raison quelconque.)

En regardant en avant, je peux imaginer des scénarios spécialisés – des systèmes fortement parallèles, peut-être – où le fait de ne pas avoir à fournir de stack pour chaque thread pourrait être avantageux et où la récursivité n’est autorisée que si le compilateur peut la transformer en boucle. (Bien sûr, les compilateurs primitifs dont je parle ci-dessus ne sont pas capables de tâches compliquées comme le code de refactorisation.)

Le professeur veut savoir si vous avez étudié ou non. Apparemment, vous n’avez pas résolu le problème de la manière dont il vous l’a appris ( la bonne façon , l’itération), et considère donc que vous ne l’avez pas fait. Je suis tout pour des solutions créatives mais dans ce cas, je suis d’accord avec votre professeur pour une raison différente:
Si l’utilisateur fournit des données non valides trop souvent (c’est-à-dire en maintenant la touche Entrée enfoncée), vous aurez une exception de dépassement de capacité de la stack et votre solution tombera en panne. De plus, la solution itérative est plus efficace et plus facile à gérer. Je pense que c’est la raison que votre professeur aurait dû vous donner.

Déduire des points parce que “nous n’avons pas couvert la récursivité en classe” est terrible. Si vous avez appris à appeler la fonction A qui appelle la fonction B qui appelle la fonction C qui retourne à B et retourne à A qui renvoie à l’appelant, le professeur ne vous a pas dit explicitement que ces fonctions doivent être différentes (ce qui ce serait le cas dans les anciennes versions de FORTRAN, par exemple), il n’ya aucune raison que A, B et C ne puissent pas tous avoir la même fonction.

D’un autre côté, il faudrait voir le code réel pour décider si, dans votre cas particulier, la récursivité est vraiment la bonne chose à faire. Il n’y a pas beaucoup de détails, mais cela ne semble pas correct.

Il y a beaucoup de points de vue à examiner en ce qui concerne la question spécifique que vous avez posée, mais ce que je peux dire, c’est que, pour l’apprentissage d’une langue, la récursivité n’est pas une caractéristique en soi. Si votre professeur vous a vraiment arraché des points pour avoir utilisé une «fonctionnalité» qu’il n’avait pas encore enseignée, c’était faux, mais comme je l’ai dit, il y a d’autres points de vue à prendre en compte.

D’après ce que je peux déduire de votre question, utiliser une fonction récursive pour demander une entrée en cas d’échec de saisie n’est pas une bonne pratique puisque l’appel de toutes les fonctions récursives est poussé vers la stack. Étant donné que cette récursivité est pilotée par une entrée utilisateur, il est possible d’avoir une fonction récursive à l’infini et donc un StackOverflow.

Il n’y a pas de différence entre ces 2 exemples que vous avez mentionnés dans votre question dans le sens de ce qu’ils font (mais diffèrent d’autres manières) – Dans les deux cas, une adresse de retour et toutes les informations de méthode sont chargées dans la stack. Dans un cas de récursivité, l’adresse de retour est simplement la ligne située juste après l’appel de la méthode (bien sûr, ce n’est pas exactement ce que vous voyez dans le code, mais plutôt dans le code créé par le compilateur). En Java, C et Python, la récursivité est relativement coûteuse par rapport à l’itération (en général) car elle nécessite l’allocation d’un nouveau cadre de stack. Sans oublier que vous pouvez obtenir une exception de dépassement de stack si l’entrée n’est pas valide plusieurs fois.

Je crois que le professeur a déduit des points puisque la récursivité est considérée comme un sujet à part entière et qu’il est peu probable qu’une personne sans expérience en programmation pense à la récursivité. (Bien sûr, cela ne signifie pas qu’ils ne le feront pas, mais c’est peu probable).

IMHO, je pense que le professeur a raison en vous déduisant les points. Vous auriez pu facilement utiliser la partie validation pour une méthode différente et l’utiliser comme ceci:

 public bool foo() { validInput = GetInput(); while(!validInput) { MessageBox.Show("Wrong Input, please try again!"); validInput = GetInput(); } return hasWon(x, y, piece); } 

Si ce que vous avez fait peut effectivement être résolu de cette manière, ce que vous avez fait était une mauvaise pratique et devrait être évité.

Peut-être que votre professeur ne l’a pas encore enseigné, mais il semble que vous soyez prêt à apprendre les avantages et les inconvénients de la récursivité.

Le principal avantage de la récursivité est que les algorithmes récursifs sont souvent beaucoup plus faciles et plus rapides à écrire.

Le principal inconvénient de la récursivité est que les algorithmes récursifs peuvent provoquer des débordements de stack, car chaque niveau de récursivité nécessite l’ajout d’un cadre de stack supplémentaire à la stack.

Pour le code de production, où la mise à l’échelle peut entraîner beaucoup plus de niveaux de récursivité en production que dans les tests unitaires du programmeur, l’inconvénient l’emporte généralement sur l’avantage, et le code récursif est souvent évité lorsque cela est possible.

En ce qui concerne la question spécifique, est-ce que la récursivité est une caractéristique, je suis enclin à dire oui, mais après avoir réinterprété la question. Il existe des choix de conception communs des langages et des compilateurs qui rendent la récursivité possible, et il existe des langages Turing-complets qui ne permettent aucune récursivité . En d’autres termes, la récursivité est une capacité qui est activée par certains choix dans la conception du langage / compilateur.

  • Soutenir des fonctions de première classe rend la récursivité possible sous des hypothèses très minimales; voir des boucles d’écriture dans Unlambda pour un exemple, ou cette expression Python obtuse ne contenant pas d’auto-références, de boucles ou d’affectations:

     >>> map((lambda x: lambda f: x(lambda g: f(lambda v: g(g)(v))))( ... lambda c: c(c))(lambda R: lambda n: 1 if n < 2 else n * R(n - 1)), ... xrange(10)) [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] 
  • Les langages / compilateurs utilisant une liaison tardive ou définissant des déclarations avancées rendent la récursivité possible. Par exemple, alors que Python autorise le code ci-dessous, c'est un choix de conception (liaison tardive), pas une exigence pour un système Turing-complet . Les fonctions récursives mutuelles dépendent souvent du support des déclarations avancées.

     factorial = lambda n: 1 if n < 2 else n * factorial(n-1) 
  • Les langages typés statiquement qui permettent des types définis récursivement consortingbuent à l'activation de la récursivité. Voir cette implémentation du Y Combinator dans Go . Sans types récursivement définis, il serait toujours possible d'utiliser la récursivité dans Go, mais je pense que le combinateur Y serait spécifiquement impossible.

D’après ce que je peux déduire de votre question, utiliser une fonction récursive pour demander des informations en cas d’échec de saisie n’est pas une bonne pratique. Pourquoi?

Parce que chaque appel à des fonctions récursives est poussé sur la stack. Étant donné que cette récursivité est pilotée par une entrée utilisateur, il est possible d’avoir une fonction récursive infinie et d’entraîner un StackOverflow :-p

Avoir une boucle non récursive pour faire cela est la voie à suivre.

La récursivité est un concept de programmation, une fonctionnalité (comme une itération) et une pratique . Comme vous pouvez le voir sur le lien, il existe un vaste domaine de recherche dédié au sujet. Peut-être n’avons-nous pas besoin d’approfondir le sujet pour comprendre ces points.

Récursivité comme fonctionnalité

En termes clairs, Java le supporte implicitement, car il permet à une méthode (qui est essentiellement une fonction spéciale) d’avoir “connaissance” de soi et d’autres méthodes composant la classe à laquelle elle appartient. Considérons un langage où ce n’est pas le cas: vous pourriez écrire le corps de cette méthode a , mais vous ne seriez pas en mesure d’inclure un appel à celui a ci. La seule solution serait d’utiliser l’itération pour obtenir le même résultat. Dans un tel langage, il faudrait faire une distinction entre les fonctions conscientes de leur propre existence (en utilisant un jeton de syntaxe spécifique) et celles qui ne le sont pas! En fait, tout un groupe de langues fait cette distinction (voir les familles Lisp et ML par exemple). Fait intéressant, Perl permet même aux fonctions anonymes (appelées lambdas ) de s’appeler récursivement (là encore, avec une syntaxe dédiée).

pas de récursivité?

Pour les langages qui ne supportent même pas la possibilité de récursivité, il existe souvent une autre solution, sous la forme du combinateur à virgule fixe , mais le langage doit toujours prendre en charge des fonctions appelées objects de première classe (objects pouvant être manipulé dans la langue elle-même).

La récursivité comme pratique

Avoir cette fonctionnalité disponible dans une langue ne signifie pas nécessairement qu’elle est idiomatique. Dans Java 8, les expressions lambda ont été incluses. Il est donc possible d’adopter une approche fonctionnelle de la programmation. Cependant, il existe des considérations pratiques:

  • la syntaxe n’est toujours pas très récursive
  • les compilateurs peuvent ne pas être en mesure de détecter cette pratique et de l’ optimiser

La ligne du bas

Heureusement (ou plus exactement, pour plus de facilité d’utilisation), Java permet aux méthodes de prendre conscience d’elles-mêmes par défaut, et donc de la récursivité, donc ce n’est pas vraiment un problème pratique, mais cela rest théorique. votre professeur voulait y répondre spécifiquement. En outre, à la lumière de l’évolution récente de la langue, cela pourrait devenir quelque chose d’important à l’avenir.