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

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.

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. ;)

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.

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.

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

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.

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.

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.

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.

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.