Des ressources pour améliorer votre compréhension de la récursivité? [fermé]

13

Je sais ce qu'est la récursion (lorsqu'un motif se reproduit en lui-même, généralement une fonction qui s'appelle sur une de ses lignes, après une rupture conditionnelle ... n'est-ce pas?), Et je peux comprendre les fonctions récursives si je les étudie de près. Mon problème est que lorsque je vois de nouveaux exemples, je suis toujours confus au départ. Si je vois une boucle, ou un mappage, un zip, une imbrication, un appel polymorphe, etc., je sais ce qui se passe simplement en le regardant. Quand je vois du code récursif, mon processus de réflexion est généralement «wtf is this? suivi de «oh c'est récursif» suivi de «je suppose que cela doit fonctionner, s'ils disent que c'est le cas».

Avez-vous donc des conseils / plans / ressources pour développer des compétences dans ce domaine? La récursivité est une sorte de concept étrange, donc je pense que la façon de l'aborder peut être tout aussi étrange et inévitable.

Andrew M
la source
28
Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité.
Andreas Johansson
1
«Le chat au chapeau revient» du Dr Seuss, cela peut ne pas être entièrement utile, mais l'appel récursif sur le chat se débarrasse de cette tache embêtante. :-) Il a également l'avantage d'être une lecture très rapide!
DKnight
2
Pratique, pratique, pratique.
David Thornley
20
Déjà répondu à cette question: programmers.stackexchange.com/questions/57243/…
Graham Borland
3
@Graham Borland: C'est un exemple de récursion infinie. Dans la plupart des programmes, manquer le cas de base entraîne généralement un débordement de pile ou une erreur de mémoire insuffisante. Pour les utilisateurs du site Web, cela risque de créer de la confusion. ;)
FrustratedWithFormsDesigner

Réponses:

10

Commencez avec quelque chose de simple et tracez-le avec un crayon et du papier. Seriosuly. Un bon point de départ est les algorithmes de traversée d'arbre, car ils sont beaucoup plus faciles à gérer en utilisant la récursivité que l'itération régulière. Cela ne doit pas être un exemple compliqué, mais quelque chose de simple et avec lequel vous pouvez travailler.

Oui, c'est bizarre et parfois contre-intuitif, mais une fois qu'il clique, une fois que vous dites "Eureka!" vous vous demanderez comment vous ne l' aviez pas compris auparavant! ;) J'ai suggéré des arbres car ils sont (OMI) la structure la plus facile à comprendre en récursivité, et ils sont faciles à travailler avec un crayon et du papier. ;)

FrustratedWithFormsDesigner
la source
1
+1 c'est ainsi que je l'ai fait. Par exemple, si vous utilisez OO, créez des classes avec une relation parent-enfant, puis essayez de créer une fonction / méthode qui vérifie si un objet a un ancêtre spécifique.
Alb
5

Je recommande fortement Scheme, en utilisant le livre The Little Lisper. Une fois que vous avez terminé, vous allez comprendre récursion, en profondeur. Presque garanti.

jcomeau_ictx
la source
1
+1 Ce livre l'a vraiment fait pour moi. Mais il a été renommé "The Little Schemer"
mike30
4

Je suggère définitivement le SICP. En outre, vous devriez consulter les vidéos de cours d'introduction des auteurs ici ; ils sont incroyablement ouverts.

Une autre voie, pas si strictement liée à la programmation, est la lecture de Gödel, Escher, Bach: an Eternal Golden Braid de Hofstadter. Une fois que vous l'avez traversée, la récursivité sera aussi naturelle que l'arithmétique. De plus, vous serez convaincu que P = nP et vous voudrez construire des machines à penser - mais c'est un effet secondaire si petit par rapport aux avantages.

cbrandolino
la source
GEB vaut quand même la peine d'être lu; même si certaines des choses dont il parle sont un peu datées (certains progrès en matière de recherche fondamentale en sciences de la société ont été réalisés au cours des 40 dernières années), la compréhension de base ne l'est pas.
Donal Fellows
2

Essentiellement, cela se résume à la pratique ... Prenez des problèmes généraux (tri, recherche, problèmes mathématiques, etc.) et voyez si vous pouvez voir comment ces problèmes peuvent être résolus si vous appliquez une seule fonction plusieurs fois.

Par exemple, le tri rapide fonctionne en ce qu'il déplace l'élément d'une liste en deux moitiés, puis s'applique à nouveau à chacune de ces moitiés. Lorsque le tri initial a lieu, il n'est pas inquiet de faire trier les deux moitiés à ce stade. Plutôt, il prend l'élément pivot et place tous les éléments plus petits que cet élément d'un côté et tous les éléments plus grands ou égaux de l'autre côté. Est-ce que cela a du sens comment il peut s'appeler récursivement à ce point pour trier les deux nouvelles listes plus petites? Ce sont aussi des listes. Juste plus petit. Mais ils doivent encore être triés.

Le pouvoir derrière la récursivité est la notion de division et de conquête. Divisez un problème à plusieurs reprises en problèmes plus petits qui sont de nature identique mais juste plus petits. Si vous le faites suffisamment finalement, vous arrivez à un point où la seule pièce restante est déjà résolue, alors vous revenez simplement de la boucle et le problème est résolu. Étudiez les exemples que vous avez mentionnés jusqu'à ce que vous les compreniez . Cela peut prendre un certain temps, mais finalement, cela deviendra plus facile. Essayez ensuite de prendre d'autres problèmes et de créer une fonction récursive pour les résoudre! Bonne chance!

EDIT: Je dois également ajouter qu'un élément clé de la récursivité est la capacité garantie de la fonction de pouvoir s'arrêter. Cela signifie que la décomposition du problème d'origine doit continuellement diminuer et il doit finalement y avoir un point d'arrêt garanti (un point auquel le nouveau sous-problème est résoluble ou déjà résolu).

Kenneth
la source
Oui, je pense avoir déjà vu une explication de tri rapide, je peux imaginer comment cela fonctionne à partir de votre rappel ci-dessus. Dans quelle mesure la récursivité est-elle expressive / flexible - la plupart des problèmes peuvent-ils être contraints à une approche récursive (même si elle n'est pas optimale)? J'ai vu des gens répondre à des énigmes de codage sur le net que la plupart des gens abordaient de manière procédurale, comme s'ils pouvaient utiliser la récursivité quand ils le voulaient juste pour l'enfer. J'ai également lu une fois, je pense, que certains langages dépendent ou récursivité pour remplacer la construction de la boucle. Et vous mentionnez le point d'arrêt garanti. J'ai l'impression que l'une de ces choses pourrait être la clé.
Andrew M
Un bon problème de démarrage simple à créer par vous-même serait d'écrire un programme récursif qui trouve la factorielle d'un nombre.
Kenneth
Toute structure en boucle peut être mise dans une structure récursive. Toute structure récursive peut être mise dans une structure en boucle ... plus ou moins. Il faut du temps et de la pratique pour savoir quand et quand ne pas utiliser la récursivité, car vous devez vous rappeler que lorsque vous utilisez la récursivité, il y a BEAUCOUP de surcharge en termes de ressources utilisées au niveau matériel.
Kenneth
Par exemple, je pouvais voir qu'il était possible de créer une structure en boucle qui effectue un tri rapide ... MAIS il est certain que cela serait une douleur royale et, selon la façon dont cela a été fait, pourrait utiliser plus de ressources système à la fin qu'une fonction récursive pour les grands tableaux.
Kenneth
voici donc ma tentative de factorielle. pour être honnête, je l'ai déjà vu, et même si je l'ai écrit à partir de zéro, pas de mémoire, c'est probablement encore plus facile qu'il ne l'aurait été. Je l'ai essayé dans JS mais j'ai eu une erreur d'analyse, mais ça fonctionne en Python def factorial(number): """return factorial of number""" if number == 0: return 0 elif number == 1: return 1 else: return number * factorial(number - 1)
Andrew M
2

Personnellement, je pense que votre meilleur pari est de vous entraîner.

J'ai appris la récursivité avec LOGO. Vous pouvez utiliser LISP. La récursivité est naturelle dans ces langues. Sinon, vous pouvez le comparer à l'étude des suites et séries mathématiques où vous exprimez ce qui suit en fonction de ce qui est arrivé auparavant, c'est-à-dire u (n + 1) = f (u (n)), ou des séries plus complexes où vous avez plusieurs variables et dépendances multiples, par exemple u (n) = g (u (n-1), u (n-2), v (n), v (n-1)); v (n) = h (u (n-1), u (n-2), v (n), v (n-1)) ...

Donc, ma suggestion serait que vous trouviez des "problèmes" de récursion standard simples (dans leur expression) et que vous essayiez de les implémenter dans la langue de votre choix. La pratique vous aidera à apprendre à penser, à lire et à exprimer ces «problèmes». Notez que souvent certains de ces problèmes peuvent être exprimés par itération, mais la récursivité peut être un moyen plus élégant de les résoudre. L'un d'eux est le calcul des nombres factoriels.

Les "problèmes" graphiques que je trouve facilitent la vue. Regardez donc les flocons de Koch, Fibonacci, la courbe du dragon et les fractales en général. Mais regardez aussi l'algorithme de tri rapide ...

Vous devez planter quelques programmes (boucles sans fin, utilisation provisoire de ressources infinies) et mal gérer les conditions de fin (pour obtenir des résultats inattendus) avant de vous familiariser avec tout cela. Et même lorsque vous l'obtiendrez, vous ferez encore ces erreurs, un peu moins souvent.

asoundmove
la source
2

Structure et interprétation des programmes informatiques

C'est le livre utilisé pour l'apprentissage, pas seulement pour la récursivité, mais pour la programmation en général dans diverses universités. C'est l'un de ces livres fondamentaux qui fournit plus d'informations, plus vous gagnez d'expérience et plus vous les lisez.

Dietbuddha
la source
0

Autant j'aime SICP et Gödel, Escher, Bach: an Eternal Golden Braid , LISP de Touretzky : A Gentle Introduction to Symbolic Computation fait également un bon travail sur l'introduction de la récursivité.

Le concept de base est le suivant: tout d'abord, vous devez savoir quand votre fonction récursive est terminée, afin qu'elle puisse retourner un résultat. Ensuite, vous devez savoir comment prendre le cas inachevé et le réduire à quelque chose que vous pouvez répéter. Pour l'exemple factoriel traditionnel (N), vous avez terminé lorsque N <= 1, et le cas inachevé est N * factoriel (N-1).

Pour un exemple beaucoup plus laid, il y a la fonction d' Ackermann A (m, n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.
John R. Strohm
la source
0

Je suggère de jouer avec certains langages fonctionnels de style ML comme OCaml ou Haskell. J'ai trouvé que la syntaxe de correspondance de motifs m'a vraiment aidé à comprendre des fonctions récursives même relativement compliquées, certainement beaucoup mieux que celles de Scheme ifet les condinstructions. (J'ai appris Haskell et Scheme en même temps.)

Voici un exemple trivial de contraste:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

et avec correspondance de motifs:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Cet exemple ne fait pas vraiment la différence - je n'ai jamais eu de problème avec l'une ou l'autre version de la fonction. C'est juste pour illustrer à quoi ressemblent les deux options. Une fois que vous arrivez à des fonctions beaucoup plus complexes, en utilisant des choses comme des listes et des arbres, la différence devient beaucoup plus prononcée.

Je recommande particulièrement Haskell car c'est un langage simple avec une syntaxe très agréable. Cela rend également beaucoup plus facile de travailler avec des idées plus avancées comme la corécursion :

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(Vous ne comprendrez pas le code ci-dessus avant de jouer un peu avec Haskell, mais soyez assuré qu'il est fondamentalement magique: P.) Bien sûr, vous pouvez faire de même avec les flux dans Scheme, mais c'est beaucoup plus naturel dans Haskell.

Tikhon Jelvis
la source
0

C'est épuisé, mais si vous pouvez le trouver, "Algorithmes récursifs" de Richard Lorentz n'est rien d'autre que la récursivité. Il couvre les bases de la récursivité, ainsi que des algorithmes récursifs spécifiques.

Les exemples sont en Pascal, mais ne sont pas si grands que le choix de la langue est gênant.

Wayne Conrad
la source