La récursivité est-elle une fonctionnalité 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 pour appeler une fonction de manière récursive sur la base que nous n'avons pas couvert la récursivité en classe, et mon argument est que nous l'avons appris implicitement par l'apprentissage returnet les méthodes.

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();
    }

À part " acontinue pour toujours" (dans le programme réel, il est utilisé correctement pour inviter à nouveau un utilisateur lorsqu'il est fourni avec une entrée invalide), y a-t-il une différence fondamentale entre aet b? Pour un compilateur non optimisé, comment sont-ils gérés différemment?

Au bout du compte , il se résume à savoir si en apprenant à return a()partir bque nous à cet effet aussi appris à return a()partir a. Avons-nous?

Pour répondre à votre question spécifique: Non, du point de vue de l'apprentissage d'une langue, la récursivité n'est pas une fonctionnalité. Si votre professeur vous a vraiment marqué pour avoir utilisé une "fonction" qu'il n'avait pas encore enseignée, c'était faux.

En lisant entre les lignes, une possibilité est qu'en utilisant la récursivité, vous avez évité d'utiliser une fonctionnalité qui était censée être un résultat d'apprentissage pour son cours. Par exemple, vous n'avez peut-être pas du tout utilisé l'itération, ou peut-être n'avez-vous utilisé que des forboucles au lieu d'utiliser à la fois foret while. Il est courant qu'un devoir 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 à cette fonctionnalité. Cependant, si cela était vraiment la cause de vos notes perdues, le professeur devrait considérer cela comme une expérience d'apprentissage qui lui est propre - si la démonstration de certains résultats d'apprentissage est l'un des critères d'une tâche, cela devrait être clairement expliqué aux étudiants. .

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

Dépassements de pile

Le plus évident est que vous risquez d'obtenir une erreur de débordement de pile. En réalité, il est très peu probable que la méthode que vous avez écrite en mène à une, car un utilisateur devrait donner une entrée incorrecte plusieurs fois pour déclencher un débordement de pile.

Cependant, une chose à garder à l'esprit est que non seulement la méthode elle-même, mais d'autres méthodes supérieures ou inférieures dans la chaîne d'appels seront sur la pile. Pour cette raison, engloutir avec désinvolture l'espace disponible dans la pile est une chose assez impolie pour toute méthode. Personne ne veut avoir à s'inquiéter constamment de l'espace libre dans la pile à chaque fois qu'il écrit du code en raison du risque que d'autres codes en aient inutilement utilisé une grande partie.

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 devriez vous soucier, c'est que la chose est faite. Vous ne devriez pas avoir à vous soucier des détails de mise en œuvre de la façon dont cela est fait. Mais une utilisation gourmande de la pile rompt ce principe, car chaque bit de code doit s'inquiéter de la quantité de pile qu'il peut supposer en toute sécurité qu'il lui a laissé par le 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'il fait. Adoptez 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 méthodes fonctionnent, et oui, elles sont toutes les deux assez faciles à comprendre. Mais comment les deux approches pourraient-elles être décrites en anglais? Je pense que ce serait quelque chose comme:

Je vais demander une entrée jusqu'à ce que l'entrée soit valide, puis la retourner

contre

Je vais demander une entrée, puis si l'entrée est valide, je la retournerai, sinon j'obtiens l'entrée et je renvoie le résultat à la place

Peut-être pouvez-vous penser à un libellé un peu 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ù cela brille, comme la traversée d'arbres, vous pouvez faire le même type d'analyse côte à côte entre la récursivité et une autre approche et vous trouverez presque certainement que la récursivité donne un code qui se décrit plus clairement, ligne par ligne.

Isolés, ces deux éléments sont de petits points. Il est très peu probable que cela conduise vraiment à un débordement de pile, et le gain de lisibilité est mineur. Mais tout programme sera une collection de bon nombre de ces petites décisions, donc même si isolément elles n'ont pas beaucoup d'importance, il est important d'apprendre les principes pour les faire correctement.

Pour répondre à la question littérale, plutôt qu'à la méta-question: la récursivité est une fonctionnalité, dans le sens où tous les compilateurs et / ou langages ne le permettent pas nécessairement. En pratique, il est attendu de tous les compilateurs modernes (ordinaires) - 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é peut ne pas être prise en charge, considérez un compilateur qui stocke l'adresse de retour d'une fonction dans un emplacement statique; cela peut être le cas, par exemple, pour un compilateur pour un microprocesseur qui n'a pas de pile.

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

a();

il est implémenté comme

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

et la définition de (),

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

est implémenté 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 revenir de l'appel externe, car l'adresse de retour a été écrasée.

Pour le compilateur que j'ai réellement utilisé (fin des années 70 ou début des années 80, je pense) sans prise en charge de la récursivité, le problème était légèrement plus subtil que cela: l'adresse de retour serait stockée sur la pile, comme dans les compilateurs modernes, mais les variables locales n'étaient pas '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 l'a explicitement pris en charge ou non. Il a peut-être eu besoin de variables locales implicites pour une raison quelconque.)

En regardant vers l'avenir, je peux imaginer des scénarios spécialisés - des systèmes fortement parallèles, peut-être - où ne pas avoir à fournir une pile pour chaque thread pourrait être avantageux, et où la récursivité n'est donc autorisée que si le compilateur peut la refactoriser en boucle. (Bien sûr, les compilateurs primitifs dont j'ai parlé ci-dessus n'étaient pas capables de tâches compliquées telles que la refactorisation du code.)

L'enseignant veut savoir si vous avez étudié ou non. Apparemment, vous n'avez pas résolu le problème de la manière qu'il vous a enseignée ( la bonne façon ; itération), et par conséquent, vous considérez que vous ne l'avez pas fait. Je suis tout à fait pour les solutions créatives, mais dans ce cas, je dois être d'accord avec votre enseignant pour une raison différente:
si l'utilisateur fournit une entrée invalide trop de fois (c'est-à-dire en maintenant la touche Entrée enfoncée), vous aurez une exception de dépassement de capacité de pile et votre la solution plantera. De plus, la solution itérative est plus efficace et plus facile à entretenir. Je pense que c'est la raison pour laquelle votre professeur aurait dû vous donner.

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

D'un autre côté, nous devrons voir le code réel pour décider si, dans votre cas particulier, l'utilisation de la récursivité est vraiment la bonne chose à faire. Il n'y a pas beaucoup de détails, mais cela semble faux.

Il y a de nombreux points de vue à examiner concernant la question spécifique que vous avez posée, mais ce que je peux dire, c'est que du point de vue de l'apprentissage d'une langue, la récursivité n'est pas une fonctionnalité en soi. Si votre professeur vous a vraiment marqué pour avoir utilisé une "fonction" 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 à considérer ici qui font en fait que le professeur a raison lorsqu'il déduit des points.

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 d'entrée n'est pas une bonne pratique puisque chaque appel de fonctions récursives est poussé vers la pile. Étant donné que cette récursivité est pilotée par l'entrée de l'utilisateur, il est possible d'avoir une fonction récursive infinie et donc un StackOverflow.

Il n'y a aucune 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 par d'autres moyens) - Dans les deux cas, une adresse de retour et toutes les informations de méthode sont chargées dans la pile. Dans un cas de récursivité, l'adresse de retour est simplement la ligne juste après l'appel de la méthode (bien sûr, ce n'est pas exactement ce que vous voyez dans le code lui-même, mais plutôt dans le code créé par le compilateur). En Java, C et Python, la récursivité est assez chère par rapport à l'itération (en général) car elle nécessite l'allocation d'un nouveau frame de pile. Sans oublier que vous pouvez obtenir une exception de dépassement de capacité de pile si l'entrée n'est pas valide trop de fois.

Je crois que le professeur a déduit des points car la récursivité est considérée comme un sujet à part entière et il est peu probable que quelqu'un 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 dans une autre méthode 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, alors 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 pile, car chaque niveau de récursivité nécessite l'ajout d'un frame de pile supplémentaire à la pile.

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 pratique.

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

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

  >>> 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 qui utilisent une liaison tardive , ou qui définissent des déclarations directes , 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 mutuellement récursives dépendent souvent de la prise en charge des déclarations directes.

  factorial = lambda n: 1 if n < 2 else n * factorial(n-1)
  

• Les langages à typage statique qui autorisent les types définis de manière récursive contribuent à activer la récursivité. Voir cette implémentation du Y Combinator dans Go . Sans types définis de manière récursive, 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 une entrée en cas d'échec d'entrée n'est pas une bonne pratique. Pourquoi?

Parce que chaque appel de fonctions récursives est poussé vers la pile. Étant donné que cette récursion est entraîné par l' entrée utilisateur , il est possible d'avoir une fonction récursive infinie et entraînant ainsi une StackOverflow :-p

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

La récursivité est un concept de programmation , une fonctionnalité (comme l'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.

La récursivité comme fonctionnalité

En termes simples, Java le prend en charge implicitement, car il permet à une méthode (qui est fondamentalement une fonction spéciale) d'avoir une "connaissance" d'elle-même et des autres méthodes composant la classe à laquelle elle appartient. Considérez un langage où ce n'est pas le cas: vous seriez capable d'écrire le corps de cette méthode a, mais vous ne seriez pas capable d'inclure un appel adedans. 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 font pas! En fait, tout un groupe de langages fait cette distinction (voir les familles Lisp et ML par exemple). Fait intéressant, Perl autorise même les fonctions anonymes (appeléeslambdas ) pour s'appeler récursivement (encore une fois, 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 cela nécessite toujours que le langage prenne en charge des fonctions comme des objets dits de première classe (c'est-à-dire des objets qui peuvent ê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, des expressions lambda ont été incluses, il pourrait donc devenir plus facile d'adopter une approche fonctionnelle de la programmation. Cependant, il y a des considérations pratiques:

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

La ligne du bas

Heureusement (ou plus précisément, pour plus de facilité d'utilisation), Java laisse les méthodes prendre conscience d'elles-mêmes par défaut et prend donc en charge la récursivité, donc ce n'est pas vraiment un problème pratique, mais cela reste encore théorique, et je suppose que 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.