revenons aux fonctions et étudions-les plus en profondeur.

Notre premier sujet sera la récursivité.

Si vous n’êtes pas nouveau dans la programmation, alors c’est probablement familier et vous pouvez sauter ce chapitre.

la récursivité est un modèle de programmation qui est utile dans les situations où une tâche peut être naturellement divisée en plusieurs tâches du même type, mais plus simple. Ou quand une tâche peut être simplifiée en une action facile plus une variante plus simple de la même tâche. Ou, comme nous le verrons bientôt, pour traiter certaines structures de données.,

Lorsqu’une fonction résout une tâche, dans le processus, elle peut appeler de nombreuses autres fonctions. Un cas partiel de ceci est quand une fonction s’appelle elle-même. Cela s’appelle de la récursivité.

Deux façons de penser

Pour quelque chose de simple pour commencer – nous allons écrire une fonction pow(x, n) qui soulève x pour une puissance naturelle de n. En d’autres mots, multiplie x par lui-même n fois.

pow(2, 2) = 4pow(2, 3) = 8pow(2, 4) = 16

Il y a deux façons de la mettre en œuvre.,

veuillez noter En quoi la variante récursive est fondamentalement différente.

Lors de la pow(x, n) est appelée, l’exécution se divise en deux branches:

 if n==1 = x /pow(x, n) = \ else = x * pow(x, n - 1)

1. Si n == 1, puis tout ce qui est trivial. On l’appelle la base de la récursivité, car elle produit immédiatement le résultat évident: pow(x, 1) est égal à x.
2. Sinon, on peut représenter pow(x, n) x * pow(x, n - 1)., En mathématiques, on écrirait xn = x * xn-1. C’est ce qu’on appelle une étape récursive: on transforme la tâche en une action plus simple (multiplication par x) et un appel plus simple de la même tâche (pow avec n). Les étapes suivantes le simplifient de plus en plus jusqu’à ce que n atteigne 1.

On peut aussi dire que pow récursivement appelle elle-même jusqu’ n == 1.,

par exemple, Pour calculer pow(2, 4) le récursive variante n’ces étapes:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

Donc, la récursivité réduit d’un appel de fonction pour une, plus simple, et puis encore plus simples, et ainsi de suite, jusqu’à ce que le résultat est évident.,

le nombre maximal d’appels imbriqués (y compris le premier) est appelé profondeur de récursivité. Dans notre cas, ce sera exactement n.

La profondeur de récursivité maximale est limitée par le moteur JavaScript. Nous pouvons compter sur 10000, certains moteurs en permettent plus, mais 100000 est probablement hors limite pour la majorité d’entre eux. Il existe des optimisations automatiques qui aident à atténuer cela (« tail calls optimizations”), mais elles ne sont pas encore prises en charge partout et ne fonctionnent que dans des cas simples.

cela limite l’application de la récursivité, mais cela reste très large., Il existe de nombreuses tâches où la façon récursive de penser donne un code plus simple, plus facile à maintenir.

le contexte d’exécution et la pile

examinons maintenant comment fonctionnent les appels récursifs. Pour cela, nous allons regarder sous le capot des fonctions.

Les informations sur le processus de l’exécution d’une fonction courante est stockée dans son contexte d’exécution.,

Le contexte d’exécution est une structure de données interne qui contient des détails sur l’exécution d’une fonction: lorsque le contrôle de flux est maintenant, les variables, la valeur de this (nous n’utilisons pas ici) et quelques autres détails internes.

un appel de fonction a exactement un contexte d’exécution qui lui est associé.

Lorsqu’une fonction effectue un appel imbriqué, ce qui suit se produit:

• La fonction actuelle est mise en pause.
• le contexte d’exécution qui lui est associé est mémorisé dans une structure de données spéciale appelée pile de contexte d’exécution.,
• l’appel imbriqué s’exécute.
• Une fois terminé, l’ancien contexte d’exécution est récupéré à partir de la pile et la fonction externe est reprise à partir de l’endroit où elle s’est arrêtée.

voyons ce qui se passe pendant l’appelpow(2, 3).

pow(2, 3)

au début de l’appel pow(2, 3) le contexte d’exécution permettra de stocker des variables: x = 2, n = 3, le flux d’exécution est à la ligne 1 de la fonction.,

Nous pouvons esquisser comme:

• le Contexte: { x: 2, n: 3, à la ligne 1 } pow(2, 3)

c’est alors Que la fonction commence à s’exécuter., La condition n == 1 est falsy, de sorte que le flux continue dans la deuxième branche de la if:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}alert( pow(2, 3) );

Les variables sont les mêmes, mais les changements de ligne, de sorte que le contexte est maintenant:

• le Contexte: { x: 2, n: 3, à la ligne 5 } pow(2, 3)

Pour calculer x * pow(x, n - 1), nous avons besoin de faire un subcall de pow avec de nouveaux arguments pow(2, 2).,

pow(2, 2)

pour effectuer un appel imbriqué, JavaScript mémorise le contexte d’exécution en cours dans la pile de contexte d’exécution.

ici, nous appelons la même fonctionpow, mais cela n’a absolument pas d’importance. Le processus est le même pour toutes les fonctions:

1. le contexte actuel est « mémorisé” en haut de la pile.
2. Le nouveau contexte est créé pour le sous-appel.
3. lorsque le sous – appel est terminé-le contexte précédent est sorti de la pile et son exécution continue.,

Voici la pile de contexte lorsque nous avons entré le sous-appelpow(2, 2):

• Context: { x: 2, n: 2, à la ligne 1 } pow(2, 2)
• Context: { x: 2, n: 3, à la ligne 5 } pow(2, 3)

le nouveau contexte d’exécution en cours (et gras), et les contextes mémorisés précédents sont ci-dessous.

lorsque nous terminons le sous – appel, il est facile de reprendre le contexte précédent, car il conserve à la fois les variables et l’endroit exact du code où il s’est arrêté.,

pow(2, 1)

Le processus se répète: une nouvelle subcall est fait à la ligne 5, maintenant avec des arguments x=2, n=1.,

Un nouveau contexte d’exécution est créé, le précédent est poussé sur le dessus de la pile:

• le Contexte: { x: 2, n: 1, à la ligne 1 } pow(2, 1)
• le Contexte: { x: 2, n: 2, à la ligne 5 } pow(2, 2)
• le Contexte: { x: 2, n: 3, à la ligne 5 } pow(2, 3)

Il y a 2 anciens contextes maintenant et 1 en cours d’exécution pow(2, 1).,

La sortie

Lors de l’exécution de pow(2, 1), contrairement à avant, la condition n == 1 est truthy, de sorte que la première branche de la if fonctionne:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}

Il n’y a pas plus d’appels imbriqués, de sorte que la fonction se termine, retour 2.

à la fin de la fonction, son contexte d’exécution n’est plus nécessaire, il est donc supprimé de la mémoire., Le précédent est restauré en haut de la pile:

• le Contexte: { x: 2, n: 2, à la ligne 5 } pow(2, 2)
• le Contexte: { x: 2, n: 3, à la ligne 5 } pow(2, 3)

Ensuite, le contexte précédent est restauré:

• le Contexte: { x: 2, n: 3, à la ligne 5 } pow(2, 3)

Quand il se termine, nous avons une suite de pow(2, 3) = 8.

La profondeur de récursivité dans ce cas est: 3.

Comme nous pouvons le voir sur les illustrations ci-dessus, la profondeur de récursivité est égale au nombre maximal de contexte dans la pile.

Notez les besoins en mémoire. Les contextes prennent la mémoire., Dans notre cas, élever à la puissance de n nécessite en fait la mémoire pour les contextes n, pour toutes les valeurs inférieures de n.

dans Une boucle de l’algorithme est plus d’économie de mémoire:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

L’itératif pow utilise un seul contexte changeant i et result dans le processus. Ses besoins en mémoire sont faibles, fixes et ne dépendent pas de n.,

toute récursivité peut être réécrite sous forme de boucle. La variante de boucle peut généralement être rendue plus efficace.

But mais parfois la réécriture est non triviale, en particulier lorsque la fonction utilise différents sous-appels récursifs en fonction des conditions et fusionne leurs résultats ou lorsque la ramification est plus complexe. Et l’optimisation peut être inutile et ne vaut absolument pas les efforts.

la Récursivité peut donner un code plus court, plus facile à comprendre et à soutenir. Les optimisations ne sont pas nécessaires dans tous les endroits, la plupart du temps nous avons besoin d’un bon code, c’est pourquoi il est utilisé.,

traversées récursives

Une autre grande application de la récursivité est une traversée récursive.

Imaginez, nous avons une entreprise. La structure du personnel peut être présentée comme un objet:

en d’autres termes, une entreprise a des départements.

• Un département peut avoir une multitude de personnel. Par exemple, sales le département a 2 employés: John et Alice.

• Ou un département peut diviser en chaires, comme development a deux branches: sites et internals. Chacun d’eux a son propre personnel.,

• Il est également possible que lorsqu’un sous-département grandit, il se divise en subsubdepartments (ou des équipes).

  Par exemple, la balise sites département dans le futur peut être divisé en équipes de siteA et siteB. Et ils peuvent potentiellement se diviser encore plus. Ce n’est pas sur la photo, juste quelque chose à avoir à l’esprit.

maintenant, disons que nous voulons une fonction pour obtenir la somme de tous les salaires. Comment pouvons-nous faire?

Une approche itérative n’est pas facile, parce que la structure n’est pas simple., La première idée peut être de faire une bouclefor surcompany avec une sous-boucle imbriquée sur les départements de 1er niveau. Mais alors nous avons besoin de plus de sous-loops imbriqués pour itérer sur le personnel dans les départements de 2ème niveau comme sites t puis un autre sous-Loop à l’intérieur de ceux pour les départements de 3ème niveau qui pourraient apparaître à l’avenir? Si nous mettons 3-4 sous-boucles imbriquées dans le code pour traverser un seul objet, cela devient plutôt laid.

nous allons essayer de récursivité.,

Comme nous pouvons le voir, lorsque notre fonction obtient la somme d’un département, il y a deux cas possibles:

1. soit c’est un département « simple” avec un tableau de personnes – alors nous pouvons additionner les salaires dans une boucle simple.
2. soit c’est un objet avec des N chaires – alors on peut faire N appels récursifs pour obtenir la somme pour chacun des subdeps et de combiner les résultats.

Le 1er cas est la base de la récursivité, le cas trivial, quand nous obtenons un tableau.

Le 2ème cas lorsque nous obtenons un objet est l’étape récursive., Une tâche complexe est divisée en sous-tâches pour les petits départements. Ils peuvent à leur tour se diviser à nouveau, mais tôt ou tard, la scission se terminera à (1).

L’algorithme est probablement encore plus facile à lire à partir du code:

Le code est court et facile à comprendre (j’espère?). C’est le pouvoir de la récursivité. Cela fonctionne également pour n’importe quel niveau d’imbrication de sous-départements.,

Voici le schéma de l’appel:

Notez que le code utilise des fonctionnalités intelligentes que nous avons couvert avant:

• la Méthode arr.reduce expliqué dans le chapitre les méthodes de Tableau pour obtenir la somme de la matrice.
• Boucle for(val of Object.values(obj)) pour effectuer une itération sur les valeurs de l’objet: Object.values retourne un tableau d’entre eux.,

structures récursives

une structure de données récursive (définie récursivement) est une structure qui se réplique par parties.

nous venons de le voir dans l’exemple d’une structure d’entreprise ci-dessus.

un département d’entreprise est:

• soit un ensemble de personnes.
• ou un objet avec des départements.

pour les développeurs web, il existe des exemples bien plus connus: les documents HTML et XML.

dans le document HTML, une balise HTML peut contenir une liste de:

• morceaux de texte.
• HTML-commentaires.,
• autres balises HTML (qui à leur tour peuvent contenir des morceaux de texte / commentaires ou d’autres balises, etc.).

C’est encore une fois une définition récursive.

Pour mieux comprendre, nous allons couvrir une plus structure récursive nommée « liste” qui pourrait être une meilleure alternative pour les tableaux dans certains cas.

liste

Imaginez, nous voulons stocker une liste ordonnée d’objets.

Le choix naturel serait un tableau:

let arr = ;

…Mais il y a un problème avec les tableaux., Les opérations” supprimer l’élément « et” insérer l’élément » sont coûteuses. Par exemple, arr.unshift(obj) l’opération doit renuméroter tous les éléments pour faire de la place pour un nouveau obj, Et si le tableau est grand, cela prend du temps. Même chose avec arr.shift().

les seules modifications structurelles qui ne nécessitent pas de renumérotation en masse sont celles qui fonctionnent avec la fin du tableau:arr.push/pop. Donc, un tableau peut être assez lent pour les grandes files d’attente, quand nous devons travailler avec le début.,

alternativement, si nous avons vraiment besoin d’insertion / suppression rapide, nous pouvons choisir une autre structure de données appelée liste chaînée.

l’élément de liste chaînée est récursivement défini comme un objet avec:

• value.
• next propriété de référencement suivant d’un élément de liste ou null si c’est la fin.,

For instance:

let list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: null } } }};

Graphical representation of the list:

An alternative code for creation:

let list = { value: 1 };list.next = { value: 2 };list.next.next = { value: 3 };list.next.next.next = { value: 4 };list.next.next.next.next = null;

Here we can even more clearly see that there are multiple objects, each one has the value and next pointing to the neighbour., La variable list est le premier objet de la chaîne, donc en suivant les pointeurs next, nous pouvons atteindre n’importe quel élément.

La liste peut être facilement divisé en plusieurs parties, et plus tard rejoint:

let secondList = list.next.next;list.next.next = null;

Pour nous rejoindre:

list.next.next = secondList;

Et nous pouvons certainement d’insérer ou de supprimer des éléments dans n’importe quel endroit.,head of the list:

To remove a value from the middle, change next of the previous one:

list.next = list.next.next;

We made list.next jump over 1 to value 2., La valeur 1 est maintenant exclue de la chaîne. S’il n’est stocké nulle part ailleurs, il sera automatiquement supprimé de la mémoire.

Contrairement aux tableaux, il n’y a pas de renumérotation en masse, nous pouvons facilement réorganiser les éléments.

Naturellement, les listes ne sont pas toujours mieux que les tableaux. Sinon, tout le monde n’utiliserait que des listes.

le principal inconvénient est que nous ne pouvons pas accéder facilement à un élément par son numéro. Dans un tableau facile: arr est une référence directe., Mais dans la liste que nous devons commencer à partir du premier élément et aller next N fois pour obtenir le n-ième élément.

But mais nous n’avons pas toujours besoin de telles opérations. Par exemple, lorsque nous avons besoin d’une file d’attente ou même d’un deque – la structure ordonnée qui doit permettre d’Ajouter/Supprimer très rapidement des éléments des deux extrémités, mais l’accès à son milieu n’est pas nécessaire.

les Listes peuvent être améliorés:

• On peut ajouter une propriété prev outre next pour faire référence à l’élément précédent, pour revenir facilement.,
• nous pouvons également ajouter une variable nommée tail référençant le dernier élément de la liste (et le mettre à jour lors de l’Ajout/Suppression d’éléments à la fin).
• …La structure des données peut varier en fonction de nos besoins.

résumé

Termes:

• la récursivité est un terme de programmation qui signifie appeler une fonction depuis elle-même. Les fonctions récursives peuvent être utilisées pour résoudre des tâches de manière élégante.

  Lorsqu’une fonction s’appelle elle-même, cela s’appelle une étape de récursivité., La base de la récursivité est les arguments de fonction qui rendent la tâche si simple que la fonction ne fait pas d’autres appels.

• une structure de données définie récursivement est une structure de données qui peut être définie en utilisant elle-même.

  par exemple, la liste chaînée peut être définie comme une structure de données composée d’un objet référençant une liste (ou null).

  list = { value, next -> list }

  Les Arbres comme L’arbre des éléments HTML ou l’arbre des départements de ce chapitre sont également naturellement récursifs: ils se ramifient et chaque branche peut avoir d’autres branches.,

  Les fonctions récursives peuvent être utilisées pour les parcourir comme nous l’avons vu dans l’exemplesumSalary.

Toute fonction récursive peut être réécrit dans un processus itératif. Et cela est parfois nécessaire pour optimiser les choses. Mais pour de nombreuses tâches, une solution récursive est assez rapide et plus facile à écrire et à prendre en charge.