Comprendre la récursivité avec JavaScript

Introduction

Certains problèmes sont résolus plus naturellement à l’aide de la récursivité. Par exemple, une séquence telle que Fibonacci a une définition récursive. Chaque numéro est la somme des deux nombres précédents de la séquence. Les problèmes qui vous obligent à construire ou à couper une structure de données semblable à une arbre peuvent également être résolus avec la récursion. Le train pour penser récursivement vous donnera une capacité puissante à résoudre ces problèmes.

Dans ce didacticiel, je ferai une revue étape par étape de plusieurs fonctions récursives pour voir comment elles fonctionnent et vous montrent des techniques que vous pouvez utiliser pour définir systématiquement les fonctions récursives.

Contenu:

• Quelle est la récursion?
• Récursion avec des chiffres
• Récursion avec des listes
• Listes de bâtiments
• revue

Quelle est la récursion?

Une fonction définie de manière récursive est une fonction qui est définie en termes de version plus simple. Ceci est un exemple simplifié:

function doA(n) { ... doA(n-1);}

Pour comprendre comment les travaux de recours conceptuellement, nous verrons un exemple qui n’a rien à voir avec le code. Imaginez que vous êtes responsable de répondre aux appels téléphoniques dans votre travail. Comme il s’agit d’une entreprise occupée, votre téléphone dispose de plusieurs lignes afin que vous puissiez assister à plusieurs appels en même temps. Chaque ligne téléphonique est une touche du récepteur et, lorsqu’il y a un appel entrant, le bouton clignote. Aujourd’hui, lorsque vous arrivez au travail et allumez le téléphone, il y a quatre lignes clignotantes en même temps. Par conséquent, vous commencez à travailler en répondant à tous les appels.

Vous répondez à la ligne une et dites « Veuillez patienter ». Ensuite, vous répondez à la ligne deux et mettez-le en attente. Ci-dessous vous répondez aux trois lignes et mettez-la en attente. Enfin, vous répondez à la quatrième ligne et parlez à la personne que vous appelez. Lorsque vous avez terminé avec la quatrième personne, vous vous présentez et répondez au troisième appel. Lorsque vous avez terminé avec le troisième appel, vous raccrochez et répondez au second. Lorsque vous avez terminé avec le deuxième appel, vous raccrochez et répondez au premier. Lorsque vous vous retrouvez avec cet appel, vous pouvez enfin accrocher le téléphone.

Chacun des appels téléphoniques de cet exemple est comme un appel récursif dans une fonction. Lorsque vous recevez un appel, il est placé sur la pile d’appels (en termes de code). Si vous ne pouvez pas terminer un appel immédiatement, vous le tenez en attente. Si vous avez un appel à une fonction qui ne peut pas être évaluée immédiatement, il reste dans la pile d’appels. Lorsque vous pouvez répondre à un appel, cela est servi. Lorsque votre code est capable d’évaluer l’appel à une fonction, il est supprimé de la pile. Demandez à cette analogie lorsque vous vérifiez les exemples de code suivants.

Récursion avec des chiffres

toutes les fonctions récursives nécessitent une base de base pour pouvoir terminer. Cependant, le simple fait d’ajouter un cas de base à notre fonction ne l’empêchera pas de fonctionner infiniment. La fonction doit faire une étape pour approcher le cas de base. Enfin, il y a l’étape récursive. Dans l’étape récursive, le problème est réduit à une version plus petite du problème.

supposons que vous ayez une fonction qui ajoutera les chiffres de 1 à n. Par exemple, si n = 4, la fonction ajoutera 1 + 2 + 3 + 4.

Nous déterminons d’abord le boîtier de base. Trouver le cas de base est comme la recherche du cas dans lequel le problème peut être résolu sans récursion. Dans cet exemple, il est quand n est égal à zéro. Zéro n’a pas de pièces, notre récursivité peut donc s’arrêter lors de l’arrivée à 0.

dans chaque étape, vous soustrayez la valeur du numéro actuel. Quel est le cas récursif? Le boîtier récursif est la fonction SUMA invoquée avec le nombre réduit.

function sum(num){ if (num === 0) { return 0; } else { return num + sum(--num) }}sum(4); //10

C’est ce qui se passe à chaque étape:

• Aller à la somme (4).
• 4 est égal à 0? Non. Placez la somme (4) en attente et passez à la somme (3).
• 3 est égal à 0? Non. Placez la somme (3) en attente et allez à la somme (2).
• 2 est égal à 0? Non. Placez la somme (2) en attente et passez à la somme (1).
• 1 est égal à 0? Non. Placez la somme (1) en attente et allez à la somme (0).
• 0 est égal à 0? Oui. Évaluer la somme (0).
• reta somme (1).
• reta somme (2).
• reta somme (3).
• reta somme (4).

Ceci est une autre façon de voir comment la fonction traite chaque appel:

sum(4)4 + sum(3)4 + ( 3 + sum(2) )4 + ( 3 + ( 2 + sum(1) ))4 + ( 3 + ( 2 + ( 1 + sum(0) )))4 + ( 3 + ( 2 + ( 1 + 0 ) ))4 + ( 3 + ( 2 + 1 ) )4 + ( 3 + 3 ) 4 + 6 10

L’argument doit changer dans le cas récursif et approcher le boîtier de base. Cet argument doit être vérifié dans le cas de base. Dans l’exemple précédent, puisque nous rétablissons la valeur 1 dans le cas récursif, nous devons vérifier si l’argument est égal à zéro dans notre cas de base.

Tâche

1. Mise en œuvre la fonction de lame utilisant un cycle au lieu de récursivité.
2. crée une fonction qui multiplie deux numéros récursives. Par exemple, multiply(2,4) entraînera 8. Écrivez ce qui se passe pendant chaque étape pour multiply(2,4)

Récursion avec les listes

La récursion sur une liste est similaire à la récursion d’un numéro, mais au lieu de réduire le nombre à chaque étape, nous réduirons la liste à chaque étape jusqu’à ce que nous ayons une liste vide.

Considérez la fonction Somme qui reçoit une liste comme entrée et renvoie la somme de tous les éléments de cette liste. Ceci est une implémentation de la fonction Somme:

function sum(l){ if (empty(l)) { return 0; } else { return car(l) + sum(cdr(l)); }}

la fonction empty renvoie la valeur true (vrai) si La liste n’a pas d’éléments. La fonction car renvoie le premier élément de la liste. Par exemple, retourne la valeur 1. La fonction renvoie la liste sans le premier élément. Par exemple, cdr() retourne. Que se passe-t-il lorsque nous exécutons sum()?

sum()1 + sum()1 + ( 2 + sum() )1 + ( 2 + ( 3 + sum() ))1 + ( 2 + ( 3 + ( 4 + sum() )))1 + ( 2 + ( 3 + ( 4 + 0 ) ))1 + ( 2 + ( 3 + 4 ) )1 + ( 2 + 7 ) 1 + 910

Lorsque vous exécutez la réursion sur une liste est examinée si vide. Sinon, l’étape récursive est effectuée dans une version réduite de la liste.

Tâche

1. Retrait de cette fonction de somme afin d’utiliser un cycle pour ajouter chaque élément de chaque élément de La liste au lieu d’utiliser la récursion.
2. définit une fonction appelée longueur (longueur) qui reçoit une liste comme entrée et renvoie le nombre d’éléments dans cette liste. Vous ne devez pas utiliser la fonction de longueur intégrée dans JavaScript. Par exemple, length() doit renvoyer la valeur 4. Écrivez ce qui se passe à chaque étape.

Listes de construction

dans la Dernier exemple, nous retournions un numéro. Mais supposons que nous voulions retourner une liste. Cela signifie qu’au lieu d’ajouter un numéro à notre étape récursive, nous devons ajouter une liste. Considérez la fonction remove (Supprimer), qui reçoit un élément et une liste comme entrée et renvoie la liste sans l’élément que nous voulons supprimer. Seul le premier élément que nous trouvons sera éliminé.

function remove(item, l){ if (empty(l)) { return ; } else if (eq(car(l), item)) { return cdr(l); } else { return cons(car(l), remove(item, cdr(l))); }}remove('c', ) //

ici, la fonction eq retourne une valeur réelle (vrai) si les deux entrées sont égales. cons reçoit un élément et une liste comme entrée et renvoie une nouvelle liste avec l’élément ajouté au début de celui-ci.

Nous vérifions si le premier élément de la liste est égal à l’élément que nous voulons supprimer. Si tel est le cas, il supprimez le premier élément de la liste et renvoie la nouvelle liste. Si le premier élément n’est pas égal à l’élément que nous voulons 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 éliminé.

Nous continuerons à éliminer les éléments jusqu’à atteindre notre cas de base, qui est une liste vide. Une liste vide signifie que nous avons parcouru tous ses éléments. Que fait la fonction remove('c', )?

remove('c', )cons( ‘a’, remove(‘c’, ) )cons( ‘a’ , cons( ‘b’, remove(‘c’, ) ))cons( ‘a’, cons( ‘b’, )cons( ‘a’, )

Dans une situation où nous devons construire une liste, nous prenons Le premier élément et nous l’ajoutons à la partie récursive de notre liste.

tâche

1. Resserrer la fonction Supprimer afin que vous utilisiez des cycles au lieu de la récursivité pour supprimer un article de Une liste.
2. Modifiez la fonction Supprimer pour supprimer toutes les occurrences d’un élément sur une liste. Par exemple, remove(‘c’, retourne. Écrivez ce qui se passe pas à l’étape.

revue

Une fonction récursive a trois parties. Le premier est le boîtier de base, qui est la condition terminale. La seconde est l’étape qui vient à notre cas de base. La troisième est l’étape récursive, dans laquelle la fonction est invoquée à elle-même avec une entrée réduite.

La récursion est comme l’itération. Toute fonction que vous pouvez définir récursivement peut également être définie à l’aide de cycles. D’autres aspects à prendre en compte lors de l’utilisation de cette technique sont la récursion dans les listes imbriquées et l’optimisation de vos appels récursifs.

Une excellente ressource pour continuer à apprendre à propos de la récursivité est le livre Le petit SCHEMER. Cela vous apprend à réfléchir à de manière récursive à l’aide d’un format de questions et de réponses.