Mastering Programmation Récursive

J'ai de la difficulté à penser ou de résoudre le problème dans les termes de la récursivité. J'ai vraiment apprécié le concept et je peux les comprendre comme la création de la base de cas, la sortie de cas & les appels récursifs etc. Je peux résoudre des problèmes simples comme l'écriture factorielle ou la sommation des nombres entiers dans un tableau. C'est là que ma pensée s'arrête. Je ne pouvais pas vraiment d'appliquer les concepts ou de trouver des solutions quand le problème se complique. Par exemple, la tour de Hanoi, même si je peux comprendre le problème et la solution, j'ai, sur mon propre ne peut pas une solution. Elle s'applique à d'autres algorithmes comme le tri rapide/binary tree traversal ainsi. Donc ma question est

  1. Quelle est la meilleure façon de le maîtriser?
  2. Quelqu'un peut-il suggérer une liste de problèmes ou de questions, que je peux utiliser comme un exercice pratique?
  3. La connaissance fonctionnelle de la langue m'aider à comprendre?

S'il vous plaît conseils.

  • La récursivité est difficile tout simplement parce que nous ne sommes pas appris à penser de manière récursive tôt dans notre vie. J'ai trouvé utile lors de l'attaque d'un appel récursif problème d'abord penser à un cas de base. Quand j'ai réussi à identifier un cas de base, en s'appuyant sur haut de il est plutôt facile. Qui fonctionne pour moi.
  • Ce que j'ai trouvé m'a aidé lors de l'apprentissage de la récursivité est cette pensée: "la Récursivité est la façon de banaliser, ce qui signifie qu'il est généralement sous la forme de votre solution = trivial étape + un peu plus facile solution" Par exemple, pour l'hanoi exemple, je l'ai résolu en utilisant le raisonnement: le problème est résolu par la prise de conscience qu'elle implique a) le déplacement de la grande pièce (seul) du point 1 au point 3 (trivial étape) b) le déplacement d'un n-1 tour du point 2 au point 3 (un peu plus facile la solution) est légèrement plus facile solution peut être trouvée en répétant les étapes a) et b), uniquement pour la cible 2, et ainsi de suite...
  • La récursivité est tout au sujet de l'abstraction. Vous essayez d'exprimer la solution d'un problème dans le même format que le problème d'origine, mais avec des paramètres différents. Par exemple, 10! = 1 * 10! = 10 * 9!, donc, à la fois le problème et sa solution sont de la forme a * b!. La plupart des gens trouvent des abstractions difficile. Mais en fait, il est tout au sujet d'essayer de la trouver des similitudes dans des situations différentes. Vous pouvez même pratique dans votre vie de tous les jours (essayez de voir les similitudes entre les deux concepts différents).
  • En effet, la récursivité (et les preuves par induction) est quelque chose qu'on ne peut généralement pas être compris instantanément, bien qu'il n'est généralement pas très complexe. Un bon moyen est en effet d'étudier les problèmes mentionnés dans les réponses ci-dessous et essayer de formuler des problèmes et des structures de manière récursive, même si elle semble totalement artificiel. Cependant, je voudrais ajouter l'algorithme minimax qui peuvent être utilisés pour jouer à plusieurs jeux de société. Il peut également être vu comme la navigation d'un arbre de recherche.
  • Exercices: énumérer toutes les permutations d'une chaîne de caractères 'abcdefgh'. Ou toutes les combinaisons de 5 lettres de cette série. Conseils: supposons que vous disposez d'une fonction qui énumère toutes les permutations de 'abcdefg'; supposons que vous disposez d'une fonction qui énumère toutes les combinaisons de 4 lettres de 'abcdefgh' ou supposons que vous disposez d'une fonction qui énumère toutes les combinaisons de 5 lettres entre 'abcdefg'.
  • Une grande réponse sur la récursivité, par l'utilisateur @Barney: stackoverflow.com/a/22242301/2736496. C'est à propos d'une question à propos de la résolution d'un 0/1 labyrinthe en 2D-tableau, mais c'est aussi sur la récursivité en général.

InformationsquelleAutor Hunter | 2014-03-28
  1. 39

    La récursivité est juste une façon de penser, tout comme itératif est. Quand nous étions enfants à l'école, on ne nous a pas appris à penser de manière récursive et c'est là que réside le vrai problème. Vous avez besoin d'incorporer cette façon de penser dans votre arsenal, une fois que vous faites cela, il va y rester pour toujours.

    Meilleure façon de master:

    J'ai trouvé utile de toujours trouver la base de cas, les premiers, peut-être au début, ils ne sont pas les plus simples, mais une fois que vous commencez à construire la récursivité sur le dessus de cette base de cas, vous allez réaliser que vous pouvez simplifier. L'importance d'identifier les cas de base est que tout d'abord, vous vous concentrez sur ce qui doit être résolu à sa forme la plus simple (le plus simple des cas) et ce en quelque sorte trace une feuille de route pour l'avenir de l'algorithme, la seconde, vous assurez-vous que l'algorithme s'arrête. Peut-être ne renvoie pas le résultat attendu, mais au moins s'arrête, ce qui est toujours encourageant.

    Aussi, il sera toujours aider à comprendre comment un petit exemple d'un problème va vous aider à trouver la solution d'une plus grande instance du problème. C'est, par exemple, comment pouvez-vous construire la solution pour l'entrée n ayant déjà la solution d'entrée n-1.

    Résoudre tous les problèmes que vous pouvez penser de manière récursive. Oui, les Tours de Hanoi n'est pas un très bon exemple, sa récursive solutions est une très intelligent solution. Essayez plus facile des problèmes, presque élémentaire problèmes.

    Liste de problèmes

    1. Opérations mathématiques: Exponentiation et chaque opération mathématique que vous pouvez penser.
    2. Chaîne de manutention: Palindrome est un très bon exercice. La recherche de mots dans une grille est également utile.
    3. Apprendre sur l'arbre de structures de données:, en particulier, est IMO le meilleur de la formation. Les arbres sont des structures de données récursives. Apprendre au sujet de leur traversals (afinde, postorder, précommande, calculer sa hauteur, son diamètre, etc). Presque chaque opération sur un arbre comme structure de données est un excellent exercice.
    4. Problèmes combinatoires: Très important, combinaisons, permutations, etc.
    5. Découverte de parcours: Lee algorithme, Labyrinthe algorithmes etc.

    Mais le plus important, commencer avec de simples problèmes. Presque tous les problèmes ont une solution récursive. Problèmes de mathématiques sont grands à obtenir une prise de. Chaque fois que vous voyez un for boucle ou un while boucle, tourner cet algorithme dans la récursivité.

    Langage de programmation

    De la programmation fonctionnelle s'appuie fortement sur la récursivité. Je ne pense pas que cela devrait aider beaucoup puisqu'ils sont par nature récursive et peut être gênant pour les utilisateurs qui ne comprennent pas la récursivité encore beaucoup.

    Utiliser un langage de programmation simple, celui que vous êtes plus familier avec, de préférence un qui n'est pas occupé à votre esprit de beaucoup de mémoire désagréments et des pointeurs. Python est un très bon début à mon avis. C'est très simple, ne prend pas la peine de vous taper ou de structures de données complexes. Aussi longtemps que la langue vous aide à rester concentré uniquement sur la récursivité, ce sera mieux.

    Un dernier conseil, si vous ne pouvez pas trouver une solution à un problème, faites une recherche sur internet ou appeler à l'aide, comprendre ce qu'il fait complètement et passer à l'autre. Ne leur permettez pas de vous contourner, parce que ce que vous essayez de faire est de intégrer cette façon de penser à votre tête.

    À maître de récursivité, vous devez d'abord maître de récursivité 🙂

    Espérons que cette aide!

    • Python n'est pas construit pour la récursivité de sorte que vous êtes supposons que pour tout résoudre avec des interprétations de la liste à ne pas sauter la pile.
    • Mon est bien, un langage fonctionnel est dur pour les gens qui ne connaissent pas la récursivité. Python est un langage de programmation simple, vous ne serez pas sauter la pile de petits récursive des problèmes.
    • Je ne pense pas que Lisp est plus difficile à apprendre que l'Algol. Le problème est que j'ai programmé dans 7 Fortran et Algol dialectes avant de voir Lisp syntaxe et ma première réaction a été que je l'ai détesté. Il faut s'habituer et après l'apprentissage d'un couple de dialectes Lisp je veux c'est les fonctionnalités (comme call/cc et fermetures)dans mon Algol dialectes. J'ai l'intention d'enseigner le Système comme la première langue de ma fille pour vérifier comment il fonctionne.
    • Je suis d'accord avec vous, mon point est que si vous êtes en se concentrant sur l'apprentissage de la récursivité, c'est probablement mieux de le former avec la langue que vous êtes plus familier avec. De cette façon vous pouvez vous concentrer sur la récursivité lui-même plutôt que de vous battre avec les constructions d'un langage inconnu. La récursivité est la langue agnostique, donc mon conseil est de le former avec le langage de programmation que vous vous sentez plus à l'aise avec.
    • Je suis d'accord avec la formation dans une langue familière est la meilleure façon d'apprendre la récursivité, de sorte que l'OP doit garder pour Java et C# et plutôt apprendre une nouvelle langue quand il se sent prête pour un nouveau défi.
    InformationsquelleAutor Paulo Bu
  2. 9

    Mon conseil: confiance que la fonction récursive "fait le travail", c'est à dire remplit son cahier des charges. Et sachant cela, vous pouvez construire une fonction qui permet de résoudre un problème plus vaste, tout en satisfaisant le cahier des charges.

    Comment résoudre le problème des tours de Hanoi ? Supposons qu'il existe une fonction de Hanoi(N) capable de déplacer un tas de N disques sans enfreindre les règles. En utilisant cette fonction, vous pouvez facilement mettre en œuvre Hanoi'(N+1): effectuer Hanoi(N), déplacer le disque suivant et effectuer Hanoi(N) de nouveau.

    Si Hanoi(N) fonctionne, alors Hanoi'(N+1) fonctionne aussi bien, sans enfreindre les règles. Pour compléter l'argument, vous devez vous assurer que les appels récursifs faire résilier. Dans ce cas, si vous pouvez résoudre le Hanoi(1) non récursive (qui est trivial), vous avez terminé.

    En utilisant cette approche, vous n'avez pas à vous soucier de la façon dont les choses se produisent réellement, vous avez la garantie que cela fonctionne. (Si vous vous déplacez de plus en plus petites instances du problème.)

    Un autre exemple: récursive de la traversée d'un arbre binaire. Assumer la fonction Visit(root) fait le travail. Ensuite, if left -> Visit(left); if right -> Visit(right); print root fera le travail ! Parce que le premier appel d'imprimer le sous-arbre gauche (ne vous inquiétez pas comment) et la deuxième sur le droit de la sous-arborescence (ne vous inquiétez pas comment), et la racine sera imprimé trop.

    Dans ce dernier cas, la terminaison est garantie par le fait que vous traitez de plus en plus petits sous-arbres, jusqu'aux feuilles.

    Autre exemple: Quicksort. Supposons que vous disposez d'une fonction qui trie un tableau en place, et que Quicksort. Vous pourrez l'utiliser comme suit: déplacer de petits éléments devant de grands éléments en place, en les comparant à un bien choisis "pivot" de la valeur (en fait, n'importe quelle valeur de la matrice permet de le faire). Ensuite trier les éléments par le biais de la fonction Quicksort, et les grands éléments de la même façon, et vous avez terminé ! Pas besoin de demander la séquence exacte des partitions qui aura lieu. La terminaison est assurée si vous évitez de le vide des sous-tableaux.

    Dernier exemple, le Triangle de Pascal. Vous savez qu'un élément est la somme des deux au-dessus d'elle, à 1 sur les côtés. Donc, avec les yeux fermés, C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1). Que c'est !

    InformationsquelleAutor Yves Daoust
  3. 3

    L'étude d'un langage fonctionnel serait certainement vous aider à penser à la récursivité. Je vous conseille de Haskell ou Lisp (ou Clojure). La bonne chose est, vous n'avez pas besoin d'obtenir de "morceaux durs" de l'une de ces langues avant d'arriver à la récursivité. Pour en savoir sur la récursivité, vous n'avez pas ont pour apprendre assez de l'une de ces langues pour faire "vrai" de la programmation.

    Haskell pattern-matching syntaxe signifie que la base de cas sont faciles à voir. En Haskell, Factorielle ressemble à ceci:

    factorial 0 = 1
factorial n = n * factorial (n - 1)

    ... ce qui est exactement équivalent à un langage procédural de l':

    int factorial(n) {
    if(n==0) {
         return 1;
    } else {
         return n * factorial(n-1)
    }
}

    ... mais avec moins de syntaxe à obscurcir le concept.

    Pour être complet, voici le même algorithme en Lisp:

    (defun factorial (n)
   (if (== n 0)
       1
       (* n (factorial (- n 1)))))

    De laquelle vous devriez être en mesure de voir est équivalente, même si, au début, tous les parenthèses ont tendance à obscurcir les gens du point de vue de ce qui se passe. Encore, un Lisp livre va couvrir beaucoup de récursive techniques.

    En outre, tous les livres de la fonctionnelle de la langue vous donnera de nombreux exemples de récursivité. Vous allez commencer avec les algorithmes qui fonctionnent avec des listes:

     addone [] = []
 addone (head:tail) = head + 1 : addone tail

    .. qui utilise un schéma très commun, avec un appel récursif par fonction. (En fait, un modèle commun de sorte que presque toutes les langues abstraite dans une bibliothèque de fonction appelée map)

    Puis vous passez à des fonctions qui traverse les arbres, en faisant un appel récursif pour chaque branche d'un nœud.

    Plus généralement, pensez à ce genre de problème:

    "Puis-je résoudre qu'une petite partie de ce problème, et laissez moi avec le même problème, mais en plus petit?".

    ... ou ...

    "Serait-ce le problème facile à résoudre, si seulement le reste a déjà été résolue?".

    Ainsi, par exemple, factorial(n) est simple de travailler si vous connaissez factorial(n-1), ce qui suggère une solution récursive.

    Il s'avère que beaucoup de problèmes peuvent être pensé de cette façon:

    "Tri d'une liste de plus de 1000 articles, qui semble dur, mais si je choisis un nombre aléatoire, trier tous les nombres plus petits que cela, puis de trier tous les nombres plus grands que cela, je suis fait." (Vient finalement vers le bas pour le tri des listes de longueur 1)

    ...

    "Le calcul du plus court chemin d'un nœud est dur, mais si seulement je pouvais savoir la distance de y à partir de chacun de mes nœuds adjacents, il serait très facile."

    ...

    "La visite de tous les fichiers dans ce répertoire arbre est dur, mais je peux regarder les fichiers dans le répertoire de base, et de la menace des sous-répertoires de la même façon."

    De même, la Tour de Hanoï. La solution est simple si vous avez de l'état comme ceci:

     To move a stack from a to c:
  If the stack is of size 1
      just move it.
  otherwise
      Move the stack minus its largest ring, to b (n-1 problem)
      Move the largest ring to c (easy)
      Move the stack on b to c (n-1 problem)

    Nous avons fait le problème look facile à dessiner sur deux apparemment difficile étapes. Mais ces mesures sont tout simplement le même problème, mais "plus petit".

    Vous trouverez peut-être utile manuellement étape par le biais d'un algorithme récursif à l'aide de morceaux de papier pour représenter la pile d'appel, comme décrit dans cette réponse: Comprendre le déroulement de pile de récursion (l'arbre transversal)

    Après que vous avez de plus à l'aise avec la récursivité, cercle en arrière et réfléchir si c'est la bonne solution pour un cas particulier. Bien que factorial() est une bonne façon de démontrer le concept de récursivité, dans la plupart des langues d'une solution itérative est plus efficace. Découvrez queue de récursivité optimisation, qui fonction langues, et pourquoi.

    • Petite note sur Clojure, en raison de la façon dont Java fonctionne (absence de la queue de la récursivité optimisation), Clojure effectivement évite l'utilisation de la récursivité dans de nombreux cas où le Lisp de l'utiliser. Pour cette raison, une Clojure livre n'est probablement pas la meilleure ressource pour l'apprentissage de la récursivité.
    • Clojure a recur qui ne souffle pas la pile. Common Lisp n'a pas de coût total de possession et s'appuie donc sur loop tout est garantie de faire du coût total de possession pour mutuellement (la queue) des appels récursifs.
    InformationsquelleAutor slim
  4. 3

    La récursivité est un moyen pratique de mettre en œuvre la Fracture & Conquer paradigme: lorsque vous avez besoin pour résoudre un problème donné, une approche puissante est à la casse dans les problèmes de même nature, mais avec une taille plus petite. En répétant ce processus, vous aurez à travailler sur les problèmes de si petits qu'ils peuvent être facilement résolu par une autre méthode.

    La question que vous devez vous poser est: "puis-je résoudre ce problème en résolvant des parties de celui-ci ?". Lorsque la réponse est positive, vous appliquez ce bien connu schéma:

    • diviser le problème en sous-problèmes récursivement, jusqu'à ce que la taille est petite,

    • résoudre les sous-problèmes par une méthode directe,

    • fusionner les solutions dans l'ordre inverse.

    Noter que le fractionnement peut être réalisé en deux parties ou plus, et ceux-ci peuvent être équilibré ou non.

    Par exemple: puis-je trier un tableau de nombres en effectuant partielle sortes ?

    Réponse 1: oui, si je laisse le dernier élément et trier le reste, je peux trier tout le tableau en insérant le dernier élément au bon endroit. C'est le tri par insertion.

    Réponse 2: oui, si j'en trouve le plus grand élément et de le déplacer à la fin, je peux trier tout le tableau en triant les éléments restants. C'est la sélection de tri.

    Réponse 3: oui, si j'ai en quelque sorte les deux moitiés du tableau, je peux trier le tableau entier en fusionnant les deux séquences, à l'aide d'un auxiliaire de tableau de mouvements. C'est la fusion de tri.

    Réponse 4: oui, si j'ai la partition de la matrice à l'aide d'un pivot, je peux trier tout le tableau en triant les deux parties. C'est la fonction de tri rapide.

    Dans tous ces cas, vous résoudre le problème par la résolution de sous-problèmes de même nature et en ajoutant un peu de colle.

    InformationsquelleAutor Yves Daoust
  5. 2

    la récursivité est dur parce que c'est une façon différente de penser, que nous n'avons jamais été présenté à quand nous étions plus jeunes.

    de ce que vous dites vous avez déjà le concept tous vous avez vraiment besoin est juste de la pratique plus. un langage fonctionnel serait certainement aider; vous serez forcé de penser à vos problèmes de manière récursive et avant que vous savez récurrence semble très naturel

    il y a des tonnes d'exercices que vous pouvez faire liés à la récursivité, gardez à l'esprit que tout ce qui est fait avec une boucle qui peut être fait de manière récursive ainsi.

    voir ce réponse pour un de beaucoup de détails à propos des références et de l'exercice probelms

    InformationsquelleAutor Moha the almighty camel
  6. 1

    Pour des problèmes complexes, je suggère de faire le problème pour les petites tailles de problème et de voir quels types de modèles que vous trouvez. Par exemple, dans le cas des Tours de Hanoï, à commencer par un problème de taille de l'un, puis deux, puis trois, etc. À un certain point, vous aurez probablement commencer à voir un modèle, et vous vous rendrez compte que certains de ce que vous avez à faire, c'est juste comme ce que vous aviez à faire sur la plus petite taille des problèmes, ou que c'est assez similaire que vous pouvez utiliser la même technique que précédemment mais avec quelques variations.

    Je suis juste allé à travers les Tours de Hanoi problème moi-même et étudié ma propre pensée. J'ai commencé avec un problème de taille:

     Nous avons un disque sur peg A. 
*** Le déplacer vers le peg C. 
Fait!

    Pour deux maintenant.

     Nous avons deux disques sur peg A. 
J'ai besoin d'utiliser peg B pour obtenir le premier disque de la route. 
*** Passer d'Un peg de peg B 
Maintenant, je peux faire le reste 
*** Passer d'Un peg de peg C 
*** Passer de la peg B de peg C 
Fait!

    Maintenant trois.

    Les choses commencent à devenir un peu plus intéressant. La solution n'est pas évidente. Cependant, j'ai compris comment se déplacer de deux disques à partir d'une cheville à l'autre, donc si je pouvais déplacer deux disques à partir d'Un peg de peg B, puis passer à un disque de peg à Un peg C, puis deux disques de peg B de peg C, j'aurais fait!
    Ma logique pour le cas de deux disques de travail, sauf que les chevilles sont différents. Si nous mettons de la logique dans une fonction, et faire de paramètres pour les chevilles, puis il est possible de ré-utiliser la logique.

    def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   print 'Move from peg '+from_peg+' to peg '+other_peg
   # Now I can do the rest
   print 'Move from peg '+from_peg+' to peg '+to_peg
   print 'Move from peg '+other_peg+' to peg '+to_peg

    La logique est alors:

     move2('A','B','C') 
impression "de se Déplacer à partir d'Un peg de peg C' 
move2('B','C','A')

    Je peux faire ce plus simple en ayant une move1 fonction:

    def move1(from_peg,to_peg):
    print 'Move from '+from_peg+' to '+to_peg

    Maintenant mon move2 fonction peut être

    def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   move1(from_peg,other_peg,to_peg)
   # Now I can do the rest
   move1(from_peg,to_peg)
   move1(other_peg,to_peg)

    Ok, qu'en quatre?

    Semble que je peux appliquer la même logique. J'ai besoin d'obtenir trois disques à partir d'Un peg de peg B, alors on A à C, puis trois à partir de B à C. j'ai résolu le déplacement de trois déjà, mais avec le mauvais chevilles, donc je vais généraliser ce:

    def move3(from_peg,to_peg,other_peg):
   move2(from_peg,other_peg,to_peg)
   move1(from_peg,to_peg)
   move2(other_peg,to_peg,from_peg)

    Cool! Et attendre, move3 et move2 sont assez similaires, maintenant, et qui a du sens. Pour tout problème de taille, nous pouvons déplacer des disques de peg B, puis déplacez l'un des disques de A vers C, puis déplacer tous les disques sur le peg B de peg C. Donc notre fonction déplacer suffit de prendre le nombre de disques qu'un paramètre:

    def move(n,from_peg,to_peg,other_peg):
    move(n-1,from_peg,other_peg,to_peg)
    move1(from_peg,to_peg)
    move(n-1,other_peg,to_peg,from_peg)

    Cela ressemble vraiment à proximité, mais il ne fonctionne pas dans le cas où n==1, car à la fin nous devons appeler move(0,...). Nous avons donc besoin de poignée:

    def move(n,from_peg,to_peg,other_peg):
    if n==1:
        move1(from_peg,to_peg)
    else:
        move(n-1,from_peg,other_peg,to_peg)
        move1(from_peg,to_peg)
        move(n-1,other_peg,to_peg,from_peg)

    Excellent! Que penser d'un problème de taille de cinq ans? Il suffit d'appeler déplacer(5,'A','C','B'). On dirait que toute la taille du problème est la même chose, de sorte que notre fonction principale est juste:

    def towers(n):
    move(n,'A','C','B')

    et nous y sommes!

    InformationsquelleAutor Vaughn Cato