Share
Certains problèmes sont plus naturellement résolus en utilisant la récursivité. Par exemple, une séquence telle que la séquence de Fibonacci a une définition récursive. Chaque numéro de la séquence est la somme des deux nombres précédents de la séquence. Les problèmes qui nécessitent que vous construisiez ou traversiez une structure de données arborescente peuvent également être résolus avec la récursivité. En vous entraînant à penser récursivement, vous obtiendrez une puissante habileté pour vous attaquer à ces problèmes.
Dans ce tutoriel, je vais passer en revue plusieurs fonctions récursives pour voir leur fonctionnement et vous montrer des techniques que vous pouvez utiliser pour définir systématiquement des fonctions récursives..
Une fonction définie récursivement est une fonction définie en termes de version simplifiée d'elle-même. Ceci est un exemple simplifié:
fonction doA (n) … doA (n-1);
Pour comprendre le fonctionnement conceptuel de la récursivité, examinons un exemple qui n'a rien à voir avec du code. Imaginez que vous soyez responsable de répondre aux appels téléphoniques au travail. Comme il s’agit d’une entreprise très active, votre téléphone dispose de plusieurs lignes téléphoniques pour vous permettre de jongler avec plusieurs appels en même temps. Chaque ligne téléphonique est un bouton sur le récepteur et, en cas d'appel entrant, le bouton clignote. Aujourd'hui, lorsque vous arrivez au travail et allumez le téléphone, quatre lignes clignotent en même temps. Donc, vous vous mettez au travail en répondant à tous les appels.
Vous décrochez la ligne un et leur dites «veuillez patienter». Ensuite, vous décrochez la ligne deux et les mettez en attente. Ensuite, vous prenez la ligne trois et les mettez en attente. Enfin, à la quatrième ligne, vous répondez et parlez à l'appelant. Lorsque vous avez terminé avec le quatrième appelant, vous raccrochez et décrochez le troisième appel. Lorsque vous avez terminé avec le troisième appel, vous raccrochez et prenez le deuxième appel. Lorsque vous avez terminé avec le deuxième appel, vous raccrochez et prenez le premier appel. Lorsque vous avez terminé cet appel, vous pouvez enfin poser le téléphone.
Chacun des appels téléphoniques dans cet exemple est semblable à un appel récursif dans une fonction. Lorsque vous recevez un appel, il est mis sur la pile d’appels (en langage parlé). Si vous ne pouvez pas terminer un appel tout de suite, vous le mettez en attente. Si vous avez un appel de fonction qui ne peut pas être évalué immédiatement, il reste sur la pile d'appels. Lorsque vous êtes en mesure de répondre à un appel, il est pris en charge. Lorsque votre code est capable d'évaluer un appel de fonction, il est extrait de la pile. Gardez cette analogie à l'esprit lorsque vous examinez les exemples de code suivants..
Toutes les fonctions récursives nécessitent un scénario de base afin qu'elles se terminent. Cependant, le simple fait d'ajouter un cas de base à notre fonction ne l'empêche pas de fonctionner à l'infini. La fonction doit comporter une étape pour nous rapprocher du scénario de base. Le dernier est l'étape récursive. À l'étape récursive, le problème est réduit à une version plus petite du problème..
Supposons que vous ayez une fonction qui additionnera les nombres de 1 à n. Par exemple, si n = 4, cela donnera 1 + 2 + 3 + 4.
Premièrement, nous déterminons le scénario de base. Trouver le cas de base peut aussi être considéré comme trouver le cas où le problème peut être résolu sans récursion. Dans ce cas, c’est lorsque n est égal à zéro. Zero n'a pas de pièces, donc notre récursivité peut s'arrêter lorsque nous atteignons 0.
A chaque étape, vous soustrairez un du nombre actuel. Quel est le cas récursif? Le cas récursif est la fonction somme appelée avec le nombre réduit.
fonction sum (num) if (num === 0) retour 0; else return num + sum (- num) sum (4); //dix
Voici ce qui se passe à chaque étape:
C'est une autre façon de voir comment la fonction traite chaque appel:
somme (4) 4 + somme (3) 4 + (3 + somme (2)) 4 + (3 + (2 + somme (1))) 4 + (3 + (2 + (1) somme (0)) )) 4 + (3 + (2 + (1 + 0))) 4 + (3 + (2 + 1)) 4 + (3 + 3) 4 + 6 10
L'argument devrait changer dans le cas récursif et vous rapprocher du cas de base. Cet argument doit être testé dans le cas de base. Dans l'exemple précédent, comme nous en soustrayons un dans le cas récursif, nous testons si l'argument est égal à zéro dans notre scénario de base..
Accentsconagua
multiplier (2,4) retournera 8. Écrivez ce qui se passe à chaque étape pour multiplier (2,4).Récurrence sur une liste est similaire à récurrence sur un nombre, sauf qu'au lieu de réduire le nombre à chaque étape, nous réduisons la liste à chaque étape jusqu'à ce que nous obtenions une liste vide..
Considérons la fonction sum qui prend une liste en entrée et renvoie la somme de tous les éléments de la liste. Ceci est une implémentation pour la somme de fonctions:
fonction sum (l) if (vide (l)) retour 0; else voiture de retour (l) + somme (cdr (l));
le vide fonction renvoie true si la liste ne contient aucun élément. le voiture fonction renvoie le premier élément de la liste. Par exemple, voiture ([1,2,3,4]) renvoie 1. Le cdr fonction renvoie la liste sans le premier élément. Par exemple, cdr ([1,2,3,4]) renvoie [2,3,4]. Qu'est-ce qui se passe quand on exécute somme ([1,2,3,4])?
somme ([1,2,3,4]) 1 + somme ([2,3,4]) 1 + (2 + somme ([3,4])) 1 + (2 + (3 + somme ([4 ]))) 1 + (2 + (3 + (4 + somme ([])))) 1 + (2 + (3 + (4 + 0))) 1 + (2 + (3 + 4)) 1 + (2 + 7) 1 + 9 10
Lorsque vous vous retrouvez dans une liste, vérifiez si elle est vide. Sinon, effectuez l'étape récursive sur une version réduite de la liste.
longueur (['a', 'b', 'c', 'd']) devrait revenir 4. Écrivez ce qui se passe à chaque étape.Dans le dernier exemple, nous retournions un nombre. Mais supposons que nous voulions renvoyer une liste. Cela signifierait qu'au lieu d'ajouter un nombre à notre étape récursive, nous devrions ajouter une liste. Considérons la fonction retirer, qui prend en entrée un élément et une liste et retourne la liste avec l’élément supprimé. Seul le premier article trouvé sera supprimé.
fonction remove (item, l) if (empty (l)) return []; else if (eq (car (l), élément)) return cdr (l); else return conso (car (l), remove (item, cdr (l))); remove ('c', ['a', 'b', 'c', 'd']) // // '' a ',' b ',' d ']Ici le eq function renvoie true si les deux entrées sont identiques. le les inconvénients function prend un élément et une liste en tant qu'entrées et renvoie une nouvelle liste avec l'élément ajouté au début.
Nous vérifierons si le premier élément de la liste est égal à celui que nous voulons supprimer. Si tel est le cas, supprimez le premier élément de la liste et renvoyez la nouvelle liste. Si le premier élément n'est pas égal à l'élément que vous souhaitez supprimer, nous prenons le premier élément de la liste et l'ajoutons à l'étape récursive. L'étape récursive contiendra la liste avec le premier élément supprimé.
Nous continuerons à supprimer des éléments jusqu'à atteindre notre cas de base, qui est une liste vide. Une liste vide signifie que nous avons parcouru tous les éléments de notre liste. Qu'est-ce que remove ('c', ['a', 'b', 'c', 'd']) faire?
remove ('c', ['a', 'b', 'c', 'd']) contre ('a', remove ('c', ['b', 'c', 'd']) ) contre ("a", contre ("b", supprimer ("c", ["c", "d"]))) contre ("a", contre ("b", ["d"]) contre ('a', ['b', 'd']) ['a', 'b', 'd']Dans une situation où nous avons besoin de construire une liste, nous prenons le premier élément et l'ajoutons à la partie récursive de notre liste.
remove ('c', ['a', 'b', 'c', 'd', 'c'] renvoie ['a', 'b', 'd']. Ecrivez ce qui se passe pas à pas.Une fonction récursive comporte trois parties. Le premier est le cas de base, qui est la condition finale. La seconde est la marche à suivre pour nous rapprocher de notre cas de base. La troisième est l'étape récursive, où la fonction s'appelle avec l'entrée réduite.
La récursion est comme une itération. Toute fonction que vous pouvez définir de manière récursive peut également être définie à l'aide de boucles. D'autres éléments à prendre en compte lors de l'utilisation de la récursivité sont les récurrences récurrentes dans les listes imbriquées et l'optimisation de vos appels récursifs..
Le livre The Little Schemer est une excellente ressource pour continuer à apprendre sur la récursivité. Il vous apprend à penser de manière récursive en utilisant un format de questions et réponses.
