Comprendre la récursivité

J’ai beaucoup de mal à comprendre la récursivité à l’école. Chaque fois que le professeur en parle, il semble que je le comprenne, mais dès que je l’essaie tout seul, cela me casse la tête.

J’essayais de résoudre les tours de Hanoi toute la nuit et j’ai complètement soufflé. Mon manuel ne contient qu’environ 30 pages en récursivité, ce qui n’est pas très utile. Est-ce que quelqu’un connaît des livres ou des ressources qui peuvent aider à clarifier ce sujet?

    Comment vider un vase contenant cinq fleurs?

    Réponse: si le vase n’est pas vide, vous en sortez une puis vous videz un vase contenant quatre fleurs.

    Comment vider un vase contenant quatre fleurs?

    Réponse: si le vase n’est pas vide, vous en sortez une puis vous videz un vase contenant trois fleurs.

    Comment vider un vase contenant trois fleurs?

    Réponse: si le vase n’est pas vide, vous en sortez une fleur et vous videz un vase contenant deux fleurs.

    Comment vider un vase contenant deux fleurs?

    Réponse: si le vase n’est pas vide, vous en sortez une fleur et vous videz un vase contenant une fleur.

    Comment vider un vase contenant une fleur?

    Réponse: si le vase n’est pas vide, vous en sortez une fleur et vous videz un vase ne contenant pas de fleurs.

    Comment vider un vase ne contenant pas de fleurs?

    Réponse: si le vase n’est pas vide, vous en sortez une mais le vase est vide, alors vous avez terminé.

    C’est répétitif. Généralisons-le:

    Comment vider un vase contenant N fleurs?

    Réponse: si le vase n’est pas vide, vous en sortez une puis vous videz un vase contenant des fleurs N-1 .

    Hmm, pouvons-nous voir cela dans le code?

    void emptyVase( int flowersInVase ) { if( flowersInVase > 0 ) { // take one flower and emptyVase( flowersInVase - 1 ) ; } else { // the vase is empty, nothing to do } } 

    Hmm, on ne pourrait pas juste faire ça dans une boucle for?

    Pourquoi oui, la récursion peut être remplacée par une itération, mais souvent la récursivité est plus élégante.

    Parlons des arbres. En informatique, un arbre est une structure composée de nœuds , où chaque nœud a un certain nombre d’enfants qui sont aussi des nœuds, ou null. Un arbre binary est un arbre constitué de nœuds ayant exactement deux enfants, généralement appelés “gauche” et “droit”; encore une fois, les enfants peuvent être des nœuds, ou null. Une racine est un nœud qui n’est l’enfant d’un autre nœud.

    Imaginez qu’un nœud, en plus de ses enfants, ait une valeur, un nombre et imaginez que nous souhaitons faire la sum de toutes les valeurs d’un arbre.

    Pour résumer la valeur dans un nœud quelconque, nous appendions la valeur du nœud lui-même à la valeur de son enfant gauche, le cas échéant, et à la valeur de son enfant droit, le cas échéant. Rappelez-vous maintenant que les enfants, s’ils ne sont pas nuls, sont également des nœuds.

    Donc, pour résumer l’enfant gauche, nous appendions la valeur du noeud enfant lui-même à la valeur de son enfant gauche, le cas échéant, et à la valeur de son enfant droit, le cas échéant.

    Donc, pour résumer la valeur de l’enfant gauche de l’enfant gauche, nous ajoutons la valeur du nœud enfant lui-même à la valeur de son enfant gauche, le cas échéant, et à la valeur de son enfant droit, le cas échéant.

    Peut-être avez-vous anticipé où je vais avec ceci et aimerais voir du code? D’ACCORD:

     struct node { node* left; node* right; int value; } ; int sumNode( node* root ) { // if there is no tree, its sum is zero if( root == null ) { return 0 ; } else { // there is a tree return root->value + sumNode( root->left ) + sumNode( root->right ) ; } } 

    Notez qu’au lieu de tester explicitement les enfants pour voir s’ils sont nuls ou des nœuds, nous faisons simplement en sorte que la fonction récursive renvoie zéro pour un nœud nul.

    Donc, disons que nous avons un arbre qui ressemble à ceci (les nombres sont des valeurs, les barres obliques pointent vers les enfants et @ signifie que le pointeur pointe vers null):

      5 / \ 4 3 /\ /\ 2 1 @ @ /\ /\ @@ @@ 

    Si nous appelons sumNode sur la racine (le noeud avec la valeur 5), nous retournerons:

     return root->value + sumNode( root->left ) + sumNode( root->right ) ; return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ; 

    Développons cela en place. Partout où nous voyons sumNode, nous le remplacerons par l’extension de la déclaration de retour:

     sumNode( node-with-value-5); return root->value + sumNode( root->left ) + sumNode( root->right ) ; return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + sumNode(null ) + sumNode( null ) + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + sumNode(null ) + sumNode( null ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + sumNode(null ) + sumNode( null ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + 0 + 0 ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 ; return 5 + 4 + 2 + 0 + 0 + 1 + 3 ; return 5 + 4 + 2 + 1 + 3 ; return 5 + 4 + 3 + 3 ; return 5 + 7 + 3 ; return 5 + 10 ; return 15 ; 

    Maintenant, voyons comment nous avons conquis une structure de profondeur arbitraire et de “branchia”, en la considérant comme l’application répétée d’un modèle composite? À chaque fois, grâce à notre fonction sumNode, nous avons traité un seul nœud, en utilisant une twig simple si / alors, et deux instructions de retour simples qui ont presque écrit les mots, directement à partir de notre spécification?

     How to sum a node: If a node is null its sum is zero otherwise its sum is its value plus the sum of its left child node plus the sum of its right child node 

    C’est le pouvoir de la récursivité.


    L’exemple de vase ci-dessus est un exemple de récursion de queue . Toute la récursion de la queue signifie que dans la fonction récursive, si nous récursions (c’est-à-dire si nous appelions à nouveau la fonction), c’était la dernière chose que nous faisions.

    L’exemple de l’arbre n’était pas récursif, car même si la dernière chose que nous avons faite, c’était de récurer le bon enfant, nous avons récuré l’enfant gauche avant de le faire.

    En fait, l’ordre dans lequel nous avons appelé les enfants et ajouté la valeur du nœud actuel n’a aucune importance, car l’addition est commutative.

    Regardons maintenant une opération où l’ordre compte. Nous utiliserons un arbre binary de noeuds, mais cette fois la valeur retenue sera un caractère, pas un nombre.

    Notre arbre aura une propriété spéciale, que pour tout nœud, son caractère vient après (dans l’ordre alphabétique) le caractère détenu par son enfant gauche et avant (dans l’ordre alphabétique) le caractère détenu par son enfant droit.

    Ce que nous voulons faire, c’est imprimer l’arbre en ordre alphabétique. C’est facile à faire, étant donné la propriété spéciale de l’arbre. Nous imprimons simplement l’enfant gauche, puis le caractère du nœud, puis le bon enfant.

    Nous ne voulons pas simplement imprimer bon gré mal gré, nous allons donc passer notre fonction à imprimer. Ce sera un object avec une fonction print (char); Nous n’avons pas besoin de nous inquiéter de la façon dont cela fonctionne, juste que lorsque l’impression est appelée, elle imprime quelque chose, quelque part.

    Voyons cela dans le code:

     struct node { node* left; node* right; char value; } ; // don't worry about this code class Printer { private ostream& out; Printer( ostream& o ) :out(o) {} void print( char c ) { out << c; } } // worry about this code int printNode( node* root, Printer& printer ) { // if there is no tree, do nothing if( root == null ) { return ; } else { // there is a tree printNode( root->left, printer ); printer.print( value ); printNode( root->right, printer ); } Printer printer( std::cout ) ; node* root = makeTree() ; // this function returns a tree, somehow printNode( root, printer ); 

    En plus de l’ordre des opérations qui compte maintenant, cet exemple montre que nous pouvons passer les choses dans une fonction récursive. La seule chose à faire est de nous assurer que chaque appel récursif continue à être transmis. Nous avons transmis un pointeur de nœud et une imprimante à la fonction, et à chaque appel récursif, nous les avons passés “en panne”.

    Maintenant, si notre arbre ressemble à ceci:

      k / \ hn /\ /\ aj @ @ /\ /\ @@ i@ /\ @@ 

    Que imprimons-nous?

     From k, we go left to h, where we go left to a, where we go left to null, where we do nothing and so we return to a, where we print 'a' and then go right to null, where we do nothing and so we return to a and are done, so we return to h, where we print 'h' and then go right to j, where we go left to i, where we go left to null, where we do nothing and so we return to i, where we print 'i' and then go right to null, where we do nothing and so we return to i and are done, so we return to j, where we print 'j' and then go right to null, where we do nothing and so we return to j and are done, so we return to h and are done, so we return to k, where we print 'k' and then go right to n where we go left to null, where we do nothing and so we return to n, where we print 'n' and then go right to null, where we do nothing and so we return to n and are done, so we return to k and are done, so we return to the caller 

    Donc, si nous regardons les lignes, nous avons imprimé:

      we return to a, where we print 'a' and then go right to we return to h, where we print 'h' and then go right to we return to i, where we print 'i' and then go right to we return to j, where we print 'j' and then go right to we return to k, where we print 'k' and then go right to we return to n, where we print 'n' and then go right to 

    Nous voyons que nous avons imprimé “ahijkn”, qui est en effet dans l’ordre alphabétique.

    Nous parvenons à imprimer un arbre entier, par ordre alphabétique, simplement en sachant imprimer un seul nœud par ordre alphabétique. Ce qui était juste (parce que notre arbre avait la propriété spéciale d’ordonner les valeurs à gauche des valeurs alphabétiques ultérieures) sachant imprimer l’enfant gauche avant d’imprimer la valeur du noeud, et t imprimer le bon enfant après avoir imprimé la valeur du noeud.

    Et c’est le pouvoir de la récursivité: être capable de faire des choses entières en ne sachant que faire une partie du tout (et savoir quand arrêter de récurer).

    Rappelant que dans la plupart des langues, opérateur || (“ou”) court-circuit lorsque son premier opérande est vrai, la fonction récursive générale est:

     void recurse() { doWeStop() || recurse(); } 

    Luc M commente:

    SO devrait créer un badge pour ce type de réponse. Toutes nos félicitations!

    Merci Luc! Mais, en fait, parce que j’ai édité cette réponse plus de quatre fois (pour append le dernier exemple, mais surtout pour corriger les fautes de frappe et le peaufiner – taper sur un petit clavier de netbook est difficile), je ne peux pas obtenir plus de points . Ce qui me décourage quelque peu de mettre autant d’efforts dans les réponses futures.

    Voir mon commentaire ici sur ceci: https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

    Votre cerveau a explosé parce qu’il a fait une récursion infinie. C’est une erreur courante des débutants.

    Croyez-le ou non, vous comprenez déjà la récursivité, vous êtes simplement entraîné par une métaphore commune mais erronée pour une fonction: une petite boîte contenant des choses qui entrent et sortent.

    Pensez plutôt à une tâche ou à une procédure, telle que “en savoir plus sur la récursivité sur le net”. C’est récursif et vous n’avez aucun problème avec ça. Pour effectuer cette tâche, vous pouvez:

     a) Lisez la page de résultats de Google pour la "récursivité"
     b) Une fois que vous l'avez lu, suivez le premier lien et ...
     a.1) Lisez cette nouvelle page sur la récursivité 
     b.1) Une fois que vous l'avez lu, suivez le premier lien et ...
     a.2) Lisez cette nouvelle page sur la récursivité 
     b.2) Une fois que vous l'avez lu, suivez le premier lien et ...
    

    Comme vous pouvez le voir, vous faites des choses récursives depuis longtemps sans aucun problème.

    Pendant combien de temps continuerais-tu à faire cette tâche? Jusqu’à ce que ton cerveau explose? Bien sûr que non, vous vous arrêterez à un moment donné, chaque fois que vous croyez avoir terminé la tâche.

    Vous n’avez pas besoin de le préciser pour vous demander de “découvrir la récursivité sur le net”, car vous êtes un humain et vous pouvez en déduire vous-même.

    Les ordinateurs ne peuvent pas déduire le jack, vous devez donc inclure une terminaison explicite: “en savoir plus sur la récursivité sur le net, JUSQU’À ce que vous l’aurez compris ou que vous ayez lu un maximum de 10 pages “.

    Vous avez également déduit que vous devriez commencer par la page de résultats de Google pour la “récursivité”, et encore une fois, c’est quelque chose qu’un ordinateur ne peut pas faire. La description complète de notre tâche récursive doit également inclure un sharepoint départ explicite:

    “En savoir plus sur la récursivité sur le net, JUSQU’À ce que vous l’aurez compris ou que vous ayez lu un maximum de 10 pages à partir de http://www.google.com/search?q=recursion

    Pour tout comprendre, je vous suggère d’essayer l’un de ces livres:

    • Common Lisp: Une introduction douce au calcul symbolique. C’est l’explication non mathématique la plus mignonne de la récursivité.
    • Le petit schemer.

    Pour comprendre la récursivité, il suffit de regarder l’étiquette de votre bouteille de shampoing:

     function repeat() { rinse(); lather(); repeat(); } 

    Le problème est qu’il n’ya pas de condition de résiliation et que la récursivité se répète indéfiniment, ou jusqu’à ce que vous manquiez de shampoing ou d’eau chaude (conditions de terminaison externes, comme si vous jetiez votre stack).

    Si vous voulez un livre qui explique bien la récursivité en termes simples, consultez Gödel, Escher, Bach: une tresse dorée éternelle de Douglas Hofstadter, en particulier le chapitre 5. En plus de la récursivité, elle explique un certain nombre de concepts complexes en informatique et en mathématiques d’une manière compréhensible, avec une explication s’appuyant sur un autre. Si vous n’avez jamais eu beaucoup de contacts avec ce genre de concepts, cela peut être un livre assez époustouflant.

    C’est plus une plainte qu’une question. Avez-vous une question plus spécifique sur la récursivité? Comme pour la multiplication, ce n’est pas une chose sur laquelle les gens écrivent beaucoup.

    En parlant de multiplication, pensez à cela.

    Question:

    Qu’est-ce qu’un * b?

    Répondre:

    Si b est 1, c’est un. Sinon, c’est un + a * (b-1).

    Qu’est-ce qu’un * (b-1)? Voir la question ci-dessus pour un moyen de le résoudre.

    Je pense que cette méthode très simple devrait vous aider à comprendre la récursivité. La méthode appelle elle-même jusqu’à ce qu’une condition soit vraie et retourne ensuite:

     function writeNumbers( aNumber ){ write(aNumber); if( aNumber > 0 ){ writeNumbers( aNumber - 1 ); } else{ return; } } 

    Cette fonction imprimera tous les numéros du premier numéro que vous utiliserez jusqu’à 0. Ainsi:

     writeNumbers( 10 ); //This wil write: 10 9 8 7 6 5 4 3 2 1 0 //and then stop because aNumber is no longer larger then 0 

    Ce qui est grave, c’est que writeNumbers (10) écrira 10, puis appellera writeNumbers (9) qui écrira 9 et appellera writeNumber (8) etc. Jusqu’à ce que writeNumbers (1) écrive 1 et appelle ensuite writeNumbers butt n’appellera pas writeNumbers (-1);

    Ce code est essentiellement le même que:

     for(i=10; i>0; i--){ write(i); } 

    Alors, pourquoi utiliser la récursivité, si une boucle for fait essentiellement la même chose? Eh bien, vous utilisez principalement la récursivité lorsque vous devez imbriquer des boucles, mais vous ne saurez pas à quelle profondeur elles sont nestedes. Par exemple, lors de l’impression d’éléments à partir de tableaux nesteds:

     var nestedArray = Array('Im a ssortingng', Array('Im a ssortingng nested in an array', 'me too!'), 'Im a ssortingng again', Array('More nesting!', Array('nested even more!') ), 'Im the last ssortingng'); function printArrayItems( ssortingngOrArray ){ if(typeof ssortingngOrArray === 'Array'){ for(i=0; i 

    Cette fonction peut prendre un tableau qui pourrait être nested dans 100 niveaux, alors que vous écrivez une boucle for pour vous obliger à l'imbriquer 100 fois:

     for(i=0; i 

    Comme vous pouvez le voir, la méthode récursive est bien meilleure.

    En fait, vous utilisez la récursivité pour réduire la complexité de votre problème. Vous appliquez la récursivité jusqu’à ce que vous atteigniez un cas de base simple qui peut être résolu facilement. Avec cela, vous pouvez résoudre la dernière étape récursive. Et avec cela toutes les autres étapes récursives à votre problème initial.

    Récursivité

    Méthode A, appelle la méthode A appelle la méthode A. Finalement, l’une de ces méthodes A n’appelle pas et quitte, mais c’est la récurrence parce que quelque chose s’appelle lui-même.

    Exemple de récursivité où je souhaite imprimer chaque nom de dossier sur le disque dur: (en c #)

     public void PrintFolderNames(DirectoryInfo directory) { Console.WriteLine(directory.Name); DirectoryInfo[] children = directory.GetDirectories(); foreach(var child in children) { PrintFolderNames(child); // See we call ourself here... } } 

    Je vais essayer de l’expliquer avec un exemple.

    Tu sais quoi n! veux dire? Si non: http://en.wikipedia.org/wiki/Factorial

    3! = 1 * 2 * 3 = 6

    voilà un pseudo-code

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

    Alors essayons:

     factorial(3) 

    est n 0?

    non!

    donc nous creusons plus profondément avec notre récursion:

     3 * factorial(3-1) 

    3-1 = 2

    est 2 == 0?

    non!

    alors on va plus loin! 3 * 2 * factoriel (2-1) 2-1 = 1

    est 1 == 0?

    non!

    alors on va plus loin! 3 * 2 * 1 * factorielle (1-1) 1-1 = 0

    est 0 == 0?

    Oui!

    nous avons un cas sortingvial

    nous avons donc 3 * 2 * 1 * 1 = 6

    j’espère que cela t’a aidé

    Quel livre utilisez-vous?

    Le manuel standard sur les algorithmes qui est réellement bon est Cormen & Rivest. Mon expérience est que cela enseigne assez bien la récursivité.

    La récursivité est l’une des parties les plus difficiles de la programmation à saisir, et même si elle nécessite un instinct, elle peut être apprise. Mais il faut une bonne description, de bons exemples et de bonnes illustrations.

    En outre, 30 pages en général sont beaucoup, 30 pages dans un seul langage de programmation sont déroutantes. N’essayez pas d’apprendre la récursivité en C ou en Java avant de comprendre la récursivité en général à partir d’un livre général.

    Une fonction récursive est simplement une fonction qui s’appelle autant de fois que nécessaire. C’est utile si vous devez traiter quelque chose plusieurs fois, mais vous n’êtes pas certain du nombre de fois que cela sera réellement nécessaire. D’une certaine manière, vous pourriez penser à une fonction récursive comme un type de boucle. Comme pour une boucle, cependant, vous devrez spécifier des conditions pour que le processus soit rompu, sinon il deviendra infini.

    http://javabat.com est un endroit amusant et excitant pour pratiquer la récursivité. Leurs exemples commencent assez légers et passent par de nombreux travaux (si vous voulez aller aussi loin). Note: Leur approche est d’apprendre en pratiquant. Voici une fonction récursive que j’ai écrite pour remplacer simplement une boucle for.

    Le pour la boucle:

     public printBar(length) { Ssortingng holder = ""; for (int index = 0; i < length; i++) { holder += "*" } return holder; } 

    Voici la récursivité pour faire la même chose. (notez que nous surchargerons la première méthode pour nous assurer qu'elle est utilisée comme ci-dessus). Nous avons également une autre méthode pour maintenir notre index (similaire à la façon dont la déclaration for le fait pour vous ci-dessus). La fonction récursive doit conserver son propre index.

     public Ssortingng printBar(int Length) // Method, to call the recursive function { printBar(length, 0); } public Ssortingng printBar(int length, int index) //Overloaded recursive method { // To get a better idea of how this works without a for loop // you can also replace this if/else with the for loop and // operationally, it should do the same thing. if (index >= length) return ""; else return "*" + printBar(length, index + 1); // Make recursive call } 

    Pour faire court, la récursivité est un bon moyen d'écrire moins de code. Dans le dernier printBar, notez que nous avons une instruction if. Si notre condition a été atteinte, nous allons quitter la récursivité et revenir à la méthode précédente, qui retourne à la méthode précédente, etc. Si j'ai envoyé un printBar (8), j'obtiens ********. J'espère que cela avec un exemple d'une fonction simple qui fait la même chose qu'une boucle for qui peut-être cela aidera. Vous pouvez pratiquer cela plus à Java Bat.

    La manière vraiment mathématique de concevoir une fonction récursive serait la suivante:

    1: Imaginez que vous ayez une fonction correcte pour f (n-1), construisez telle que f (n) est correct. 2: Construire f, tel que f (1) est correct.

    C’est ainsi que vous pouvez prouver que la fonction est correcte, mathématiquement, et cela s’appelle l’ induction . Cela équivaut à avoir des cas de base différents ou des fonctions plus complexes sur plusieurs variables). Il est également équivalent à imaginer que f (x) est correct pour tous x

    Maintenant, pour un exemple “simple”. Construisez une fonction qui peut déterminer s’il est possible d’avoir une combinaison de pièces de 5 cents et de 7 cents pour obtenir des centimes. Par exemple, il est possible d’avoir 17 cents par 2×5 + 1×7, mais impossible d’avoir 16 cents.

    Maintenant, imaginez que vous avez une fonction qui vous indique s’il est possible de créer des centimes, tant que x

     bool can_create_coins(int n) { if (n >= 7 && can_create_coins_small(n-7)) return true; else if (n >= 5 && can_create_coins_small(n-5)) return true; else return false; } 

    L’astuce ici est de réaliser que le fait que can_create_coins fonctionne pour n signifie que vous pouvez remplacer can_create_coins par can_create_coins_small, en donnant:

     bool can_create_coins(int n) { if (n >= 7 && can_create_coins(n-7)) return true; else if (n >= 5 && can_create_coins(n-5)) return true; else return false; } 

    Une dernière chose à faire est d’avoir un cas de base pour arrêter la récursion infinie. Notez que si vous essayez de créer 0 centime, cela est possible en n’ayant pas de pièces. L’ajout de cette condition donne:

     bool can_create_coins(int n) { if (n == 0) return true; else if (n >= 7 && can_create_coins(n-7)) return true; else if (n >= 5 && can_create_coins(n-5)) return true; else return false; } 

    On peut prouver que cette fonction retournera toujours, en utilisant une méthode appelée descente infinie , mais ce n’est pas nécessaire ici. Vous pouvez imaginer que f (n) appelle seulement des valeurs plus faibles de n et atteindra toujours éventuellement 0.

    Pour utiliser cette information pour résoudre votre problème de Tower of Hanoi, je pense que le truc est de supposer que vous avez une fonction pour déplacer n-1 comprimés de a à b (pour tout a / b), en essayant de déplacer n tables de a à b .

    Exemple récursif simple en Common Lisp :

    MYMAP applique une fonction à chaque élément d’une liste.

    1) une liste vide n’a pas d’élément, nous renvoyons donc la liste vide – () et NIL sont toutes les deux la liste vide.

    2) appliquer la fonction à la première liste, appeler MYMAP pour le rest de la liste (l’appel récursif) et combiner les deux résultats dans une nouvelle liste.

     (DEFUN MYMAP (FUNCTION LIST) (IF (NULL LIST) () (CONS (FUNCALL FUNCTION (FIRST LIST)) (MYMAP FUNCTION (REST LIST))))) 

    Regardons l’exécution tracée. En entrant une fonction, les arguments sont imprimés. À la sortie d’une fonction, le résultat est imprimé. Pour chaque appel récursif, la sortie sera mise en retrait sur le niveau.

    Cet exemple appelle la fonction SIN sur chaque numéro d’une liste (1 2 3 4).

     Command: (mymap 'sin '(1 2 3 4)) 1 Enter MYMAP SIN (1 2 3 4) | 2 Enter MYMAP SIN (2 3 4) | 3 Enter MYMAP SIN (3 4) | | 4 Enter MYMAP SIN (4) | | 5 Enter MYMAP SIN NIL | | 5 Exit MYMAP NIL | | 4 Exit MYMAP (-0.75680256) | 3 Exit MYMAP (0.14112002 -0.75680256) | 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256) 1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256) 

    Ceci est notre résultat :

     (0.841471 0.9092975 0.14112002 -0.75680256) 

    Pour expliquer la récursivité à un enfant de six ans, expliquez-le d’abord à un enfant de cinq ans, puis attendez un an.

    En fait, c’est un contre-exemple utile, car votre appel récursif devrait être plus simple, pas plus difficile. Il serait encore plus difficile d’expliquer la récursion à un enfant de cinq ans, et bien que vous puissiez arrêter la récursivité à 0, vous n’avez pas de solution simple pour expliquer la récursivité à un an zéro.

    Pour résoudre un problème en utilisant la récursivité, commencez par le subdiviser en un ou plusieurs problèmes plus simples que vous pouvez résoudre de la même manière, puis, lorsque le problème est suffisamment simple à résoudre sans récursivité supplémentaire, vous pouvez revenir aux niveaux supérieurs.

    En fait, c’était une définition récursive de la façon de résoudre un problème de récursivité.

    Les enfants utilisent implicitement la récursivité, par exemple:

    Road sortingp à Disney World

    Sommes-nous encore là? (Non)

    Sommes-nous encore là? (Bientôt)

    Sommes nous encore là? (Presque …)

    Sommes-nous encore là? (SHHHH)

    Sommes-nous déjà là?(!!!!!)

    À quel point l’enfant s’endort …

    Cette fonction de compte à rebours est un exemple simple:

     function countdown() { return (arguments[0] > 0 ? ( console.log(arguments[0]),countdown(arguments[0] - 1)) : "done" ); } countdown(10); 

    Lorsque je travaille avec des solutions récursives, j’essaie toujours de:

    • Établissez le cas de base en premier, par exemple lorsque n = 1 dans une solution à factorielle
    • Essayez de trouver une règle générale pour chaque autre cas

    Il y a aussi différents types de solutions récursives, il y a l’approche de diviser et conquérir qui est utile pour les fractales et beaucoup d’autres.

    Cela aiderait également si vous pouviez d’abord travailler sur des problèmes plus simples, juste pour vous en assurer. Certains exemples résolvent le factoriel et génèrent le nième numéro de fibonacci.

    Pour les références, je recommande fortement les algorithmes de Robert Sedgewick.

    J’espère que cela pourra aider. Bonne chance.

    Aie. J’ai essayé de comprendre les tours de Hanoi l’année dernière. La difficulté de l’HO est qu’il ne s’agit pas d’un exemple simple de récursivité: vous avez des récursions nestedes qui changent également le rôle des tours à chaque appel. La seule façon dont je pouvais faire comprendre cela était de visualiser littéralement le mouvement des anneaux dans mon esprit et de verbaliser ce que serait l’appel récursif. Je commencerais par un seul anneau, puis deux, puis trois. J’ai en fait commandé le jeu sur internet. Il m’a fallu peut-être deux ou trois jours pour me casser la tête.

    Une fonction récursive est comme un ressort que vous compressez un peu à chaque appel. À chaque étape, vous mettez un peu d’information (contexte actuel) sur une stack. Lorsque l’étape finale est atteinte, le spring est libéré, collectant toutes les valeurs (contextes) en même temps!

    Pas sûr que cette métaphore soit efficace … 🙂

    Quoi qu’il en soit, au-delà des exemples classiques (factorielle qui est le pire exemple car inefficace et facilement aplati, Fibonacci, Hanoi …) qui sont un peu artificiels (je les utilise rarement, voire jamais, dans des cas de programmation réels) intéressant de voir où il est vraiment utilisé.

    Un cas très courant est de marcher sur un arbre (ou un graphique, mais les arbres sont généralement plus communs).
    Par exemple, une hiérarchie de dossiers: pour répertorier les fichiers, vous les parcourez. Si vous trouvez un sous-répertoire, la fonction listant les fichiers s’appelle lui-même avec le nouveau dossier comme argument. En revenant de la liste de ce nouveau dossier (et de ses sous-dossiers!), Il reprend son contexte, dans le fichier (ou dossier) suivant.
    Un autre cas concret est le dessin d’une hiérarchie de composants d’interface graphique: des conteneurs, tels que des panneaux, peuvent contenir des composants pouvant également être des panneaux, des composants composés, etc. La routine de peinture appelle récursivement la fonction appelle la fonction de peinture de tous les composants qu’il contient, etc.

    Je ne sais pas si je suis très clair, mais j’aime montrer l’utilisation réelle du matériel pédagogique, car c’était quelque chose que je rencontrais par le passé.

    Pensez à une ouvrière. Il essaie de faire du miel. Il fait son travail et s’attend à ce que d’autres abeilles ouvrières fassent le rest du miel. Et quand le nid d’abeilles est plein, il s’arrête.

    Pensez comme magique. You have a function that has the same name with the one you are trying to implement and when you give it the subproblem, it solves it for you and the only thing you need to do is to integrate the solution of your part with the solution it gave you.

    For example, we want to calculate the length of a list. Lets call our function magical_length and our magical helper with magical_length We know that if we give the sublist which does not have the first element, it will give us the length of the sublist by magic. Then only thing we need to think is how to integrate this information with our job. The length of the first element is 1 and magic_counter gives us the length of sublist n-1, therefore total length is (n-1) + 1 -> n

     int magical_length( list ) sublist = rest_of_the_list( list ) sublist_length = magical_length( sublist ) // you can think this function as magical and given to you return 1 + sublist_length 

    However this answer is incomplete because we didn’t consider what happens if we give an empty list. We thought that the list we have always has at least one element. Therefore we need to think about what should be the answer if we are given an empty list and answer is obviously 0. So add this information to our function and this is called base/edge condition.

     int magical_length( list ) if ( list is empty) then return 0 else sublist_length = magical_length( sublist ) // you can think this function as magical and given to you return 1 + sublist_length