Revenons aux fonctions et étudions-les plus en profondeur.
Notre premier sujet sera la récursivité .
Si vous n'êtes pas novice en programmation, cela vous est probablement familier et vous pouvez ignorer ce chapitre.
La récursivité est un modèle de programmation utile dans les situations où une tâche peut être naturellement divisée en plusieurs tâches du même type, mais plus simples. Ou lorsqu’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, de gérer certaines structures de données.
Lorsqu’une fonction résout une tâche, elle peut appeler de nombreuses autres fonctions au cours du processus. Un cas partiel de ceci est celui où une fonction s'appelle elle-même . C'est ce qu'on appelle la récursivité .
Pour commencer par quelque chose de simple, écrivons une fonction pow(x, n) qui élève x à une puissance naturelle de n . En d’autres termes, multiplie x par lui-même n fois.
puissance(2, 2) = 4 puissance(2, 3) = 8 puissance(2, 4) = 16
Il existe deux manières de le mettre en œuvre.
Pensée itérative : la boucle for :
fonction pow(x, n) {
soit le résultat = 1 ;
// multiplie le résultat par x n fois dans la boucle
pour (soit i = 0; i < n; i++) {
résultat *= x ;
}
renvoyer le résultat ;
}
alerte( pow(2, 3) ); // 8Pensée récursive : simplifiez la tâche et appelez-vous :
fonction pow(x, n) {
si (n == 1) {
renvoyer x ;
} autre {
retourner x * pow(x, n - 1);
}
}
alerte( pow(2, 3) ); // 8Veuillez noter en quoi la variante récursive est fondamentalement différente.
Lorsque pow(x, n) est appelé, l'exécution se divise en deux branches :
si n==1 = x
/
pow(x, n) =
sinon = x * pow(x, n - 1) Si n == 1 , alors tout est trivial. On l'appelle la base de récursivité, car elle produit immédiatement le résultat évident : pow(x, 1) est égal à x .
Sinon, nous pouvons représenter pow(x, n) comme x * pow(x, n - 1) . En mathématiques, on écrirait x n = x * x n-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 inférieur). Les étapes suivantes le simplifient de plus en plus jusqu'à ce que n atteigne 1 .
On peut aussi dire que pow s'appelle récursivement jusqu'à n == 1 .
Par exemple, pour calculer pow(2, 4) la variante récursive effectue ces étapes :
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
Ainsi, la récursion réduit un appel de fonction à un appel plus simple, puis à un appel encore plus simple, et ainsi de suite, jusqu'à ce que le résultat devienne évident.
La récursivité est généralement plus courte
Une solution récursive est généralement plus courte qu’une solution itérative.
Ici, nous pouvons réécrire la même chose en utilisant l'opérateur conditionnel ? au lieu de if pour rendre pow(x, n) plus concis et toujours très lisible :
fonction pow(x, n) {
retourner (n == 1) ? x : (x * pow(x, n - 1));
} Le nombre maximal d'appels imbriqués (y compris le premier) est appelé profondeur de récursion . Dans notre cas, ce sera exactement n .
La profondeur de récursion maximale est limitée par le moteur JavaScript. On peut compter sur 10 000, certains moteurs autorisent plus, mais 100 000 est probablement hors limite pour la majorité d'entre eux. Il existe des optimisations automatiques qui aident à atténuer ce problème (« optimisations des appels de queue »), 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 elle reste tout de même très large. Il existe de nombreuses tâches pour lesquelles la façon de penser récursive donne un code plus simple, plus facile à maintenir.
Examinons maintenant le fonctionnement des appels récursifs. Pour cela, nous allons regarder sous le capot des fonctions.
Les informations sur le processus d'exécution d'une fonction en cours d'exécution sont stockées 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 : où se trouve actuellement le flux de contrôle, les variables actuelles, la valeur de this (nous ne l'utilisons pas ici) et quelques autres détails internes.
Un appel de fonction est associé à exactement un contexte d’exécution.
Lorsqu'une fonction effectue un appel imbriqué, les événements suivants se produisent :
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 l'opération terminée, l'ancien contexte d'exécution est récupéré de la pile et la fonction externe reprend là où elle s'était arrêtée.
Voyons ce qui se passe lors de l'appel pow(2, 3) .
Au début de l'appel pow(2, 3) le contexte d'exécution stockera les variables : x = 2, n = 3 , le flux d'exécution est à la ligne 1 de la fonction.
Nous pouvons le schématiser ainsi :
Contexte : { x : 2, n : 3, à la ligne 1 } pow(2, 3)
C'est à ce moment-là que la fonction commence à s'exécuter. La condition n == 1 est fausse, donc le flux continue dans la deuxième branche de if :
fonction pow(x, n) {
si (n == 1) {
renvoyer x ;
} autre {
retourner x * pow(x, n - 1);
}
}
alerte( pow(2, 3) );Les variables sont les mêmes, mais la ligne change, donc le contexte est maintenant :
Contexte : { x : 2, n : 3, à la ligne 5 } pow(2, 3)
Pour calculer x * pow(x, n - 1) , nous devons faire un sous-appel de pow avec de nouveaux arguments pow(2, 2) .
Pour effectuer un appel imbriqué, JavaScript mémorise le contexte d'exécution actuel dans la pile de contexte d'exécution .
Ici, nous appelons la même fonction pow , mais cela n'a absolument pas d'importance. Le processus est le même pour toutes les fonctions :
Le contexte actuel est « mémorisé » en haut de la pile.
Le nouveau contexte est créé pour le sous-appel.
Lorsque le sous-appel est terminé, le contexte précédent est extrait de la pile et son exécution continue.
Voici la pile de contexte lorsque nous avons entré le sous-appel pow(2, 2) :
Contexte : { x : 2, n : 2, à la ligne 1 } pow(2, 2)
Contexte : { x : 2, n : 3, à la ligne 5 } pow(2, 3)
Le nouveau contexte d'exécution actuel est en haut (et en gras), et les contextes mémorisés précédents sont en dessous.
Lorsque nous avons terminé 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é.
Veuillez noter:
Ici, dans l'image, nous utilisons le mot « ligne », car dans notre exemple, il n'y a qu'un seul sous-appel dans la ligne, mais généralement une seule ligne de code peut contenir plusieurs sous-appels, comme pow(…) + pow(…) + somethingElse(…) .
Il serait donc plus précis de dire que l'exécution reprend « immédiatement après le sous-appel ».
Le processus se répète : un nouveau sous-appel est effectué à la ligne 5 , maintenant avec les arguments x=2 , n=1 .
Un nouveau contexte d'exécution est créé, le précédent est poussé en haut de la pile :
Contexte : { x : 2, n : 1, à la ligne 1 } pow(2, 1)
Contexte : { x : 2, n : 2, à la ligne 5 } pow(2, 2)
Contexte : { x : 2, n : 3, à la ligne 5 } pow(2, 3)
Il y a maintenant 2 anciens contextes et 1 actuellement en cours d'exécution pour pow(2, 1) .
Lors de l'exécution de pow(2, 1) , contrairement à avant, la condition n == 1 est véridique, donc la première branche de if fonctionne :
fonction pow(x, n) {
si (n == 1) {
renvoyer x ;
} autre {
retourner x * pow(x, n - 1);
}
} Il n'y a plus d'appels imbriqués, donc la fonction se termine en renvoyant 2 .
Une fois la fonction terminée, son contexte d'exécution n'est plus nécessaire, elle est donc supprimée de la mémoire. Le précédent est restauré en haut de la pile :
Contexte : { x : 2, n : 2, à la ligne 5 } pow(2, 2)
Contexte : { x : 2, n : 3, à la ligne 5 } pow(2, 3)
L'exécution de pow(2, 2) reprend. Il a le résultat du sous-appel pow(2, 1) , il peut donc également terminer l'évaluation de x * pow(x, n - 1) , en renvoyant 4 .
Ensuite le contexte précédent est restauré :
Contexte : { x : 2, n : 3, à la ligne 5 } pow(2, 3)
Quand cela se termine, nous avons un résultat de pow(2, 3) = 8 .
La profondeur de récursion dans ce cas était : 3 .
Comme nous pouvons le voir sur les illustrations ci-dessus, la profondeur de récursion est égale au nombre maximal de contextes dans la pile.
Notez les besoins en mémoire. Les contextes prennent de la mémoire. Dans notre cas, élever à la puissance n nécessite en fait de la mémoire pour n contextes, pour toutes les valeurs inférieures de n .
Un algorithme basé sur des boucles économise davantage de mémoire :
fonction pow(x, n) {
soit le résultat = 1 ;
pour (soit i = 0; i < n; i++) {
résultat *= x ;
}
renvoyer le résultat ;
} Le pow itératif utilise un seul contexte changeant i et result au processus. Ses besoins en mémoire sont petits, fixes et ne dépendent pas de n .
Toute récursion peut être réécrite sous forme de boucle. La variante en boucle peut généralement être rendue plus efficace.
…Mais parfois, la réécriture n'est pas triviale, en particulier lorsqu'une fonction utilise différents sous-appels récursifs en fonction des conditions et fusionne leurs résultats ou lorsque le branchement est plus complexe. Et l’optimisation peut s’avérer inutile et ne vaut absolument pas la peine d’être déployée.
La récursivité peut donner un code plus court, plus facile à comprendre et à prendre en charge. Les optimisations ne sont pas nécessaires partout, nous avons surtout besoin d'un bon code, c'est pourquoi il est utilisé.
Une autre grande application de la récursion est un parcours récursif.
Imaginez, nous avons une entreprise. La structure du personnel peut être présentée comme un objet :
laissez l'entreprise = {
ventes: [{
nom : « Jean »,
salaire: 1000
}, {
nom: 'Alice',
salaire : 1600
}],
développement: {
sites : [{
nom : « Pierre »,
salaire : 2000
}, {
nom: 'Alex',
salaire : 1800
}],
internes : [{
nom : « Jack »,
salaire: 1300
}]
}
} ;En d’autres termes, une entreprise a des départements.
Un département peut avoir un personnel très varié. Par exemple, le service sales compte 2 employés : John et Alice.
Ou bien, un département peut être divisé en sous-départements, comme development comporte deux branches : sites et internals . Chacun d'eux a son propre personnel.
Il est également possible que lorsqu'un sous-département s'agrandit, il se divise en sous-sous-départements (ou équipes).
Par exemple, le service sites pourrait à l'avenir être divisé en équipes pour siteA et siteB . Et ils peuvent potentiellement se diviser encore plus. Ce n'est pas sur la photo, c'est juste quelque chose à garder à l'esprit.
Supposons maintenant qu'une fonction obtienne la somme de tous les salaires. Comment pouvons-nous faire cela ?
Une approche itérative n’est pas facile, car la structure n’est pas simple. La première idée peut être de créer une boucle for sur company avec une sous-boucle imbriquée sur les départements de 1er niveau. Mais ensuite nous avons besoin de plus de sous-boucles imbriquées pour parcourir le personnel des départements de 2ème niveau comme sites … Et puis une autre sous-boucle à l'intérieur de celles des départements de 3ème niveau qui pourrait apparaître dans le futur ? Si nous mettons 3 ou 4 sous-boucles imbriquées dans le code pour parcourir un seul objet, cela devient plutôt moche.
Essayons la récursion.
Comme nous pouvons le voir, lorsque notre fonction fait la somme d'un département, il y a deux cas possibles :
Soit il s'agit d'un département « simple » avec un large éventail de personnes – alors nous pouvons additionner les salaires dans une simple boucle.
Ou c'est un objet avec N sous-départements – alors nous pouvons faire N appels récursifs pour obtenir la somme de chacun des sous-départements et combiner les résultats.
Le 1er cas est la base de la récursion, le cas trivial, lorsqu'on obtient un tableau.
Le 2ème cas où l'on obtient un objet est l'étape récursive. Une tâche complexe est divisée en sous-tâches pour des départements plus petits. Ils peuvent à leur tour se séparer à nouveau, mais tôt ou tard, la séparation se terminera en (1).
L'algorithme est probablement encore plus facile à lire à partir du code :
let company = { // le même objet, compressé par souci de concision
ventes : [{nom : 'John', salaire : 1 000}, {nom : 'Alice', salaire : 1 600 }],
développement: {
sites : [{nom : 'Peter', salaire : 2000}, {nom : 'Alex', salaire : 1800 }],
internes : [{nom : 'Jack', salaire : 1 300}]
}
} ;
// La fonction pour faire le travail
fonction sommeSalaires (département) {
if (Array.isArray(department)) { // cas (1)
return département.reduce((prev, current) => prev + current.salary, 0); // somme le tableau
} autre { // cas (2)
soit somme = 0 ;
for (laisser le sous-dépôt de Object.values (département)) {
somme += sommeSalaires(subdep); // appelle récursivement les sous-départements, additionne les résultats
}
retourner la somme ;
}
}
alert(sumSalaries(entreprise)); // 7700Le code est court et facile à comprendre (j'espère ?). C'est le pouvoir de la récursion. Cela fonctionne également pour n’importe quel niveau d’imbrication de sous-départements.
Voici le schéma des appels :
On voit facilement le principe : pour un objet {...} des sous-appels sont effectués, tandis que les tableaux [...] sont les « feuilles » de l'arbre de récursion, ils donnent un résultat immédiat.
Notez que le code utilise des fonctionnalités intelligentes que nous avons déjà abordées :
Méthode arr.reduce expliquée dans le chapitre Méthodes Array pour obtenir la somme du tableau.
Boucle for(val of Object.values(obj)) pour parcourir les valeurs des objets : Object.values en renvoie un tableau.
Une structure de données récursive (définie de manière récursive) est une structure qui se réplique en plusieurs parties.
Nous venons de le voir dans l’exemple de structure d’entreprise ci-dessus.
Un département d'entreprise est :
Soit un éventail 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.
Commentaires HTML.
Autres balises HTML (qui peuvent à leur tour contenir des morceaux de texte/commentaires ou d'autres balises, etc.).
C'est encore une fois une définition récursive.
Pour une meilleure compréhension, nous aborderons une autre structure récursive nommée « Liste chaînée » qui pourrait être une meilleure alternative aux tableaux dans certains cas.
Imaginez, nous voulons stocker une liste ordonnée d'objets.
Le choix naturel serait un tableau :
soit arr = [obj1, obj2, obj3] ;
…Mais il y a un problème avec les tableaux. Les opérations « supprimer un élément » et « insérer un élément » sont coûteuses. Par exemple, l'opération arr.unshift(obj) 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. Idem avec arr.shift() .
Les seules modifications structurelles qui ne nécessitent pas de renumérotation en masse sont celles qui opèrent avec la fin du tableau : arr.push/pop . Ainsi, un tableau peut être assez lent pour les grandes files d'attente, lorsque nous devons travailler avec le début.
Alternativement, si nous avons vraiment besoin d’une 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 défini de manière récursive comme un objet avec :
value .
propriété next faisant référence au prochain élément de liste chaînée ou null si c'est la fin.
Par exemple:
laissez la liste = {
valeur : 1,
suivant: {
valeur : 2,
suivant: {
valeur : 3,
suivant: {
valeur : 4,
suivant: nul
}
}
}
} ;Représentation graphique de la liste :
Un code alternatif pour la création :
let list = { valeur : 1 } ;
list.next = {valeur : 2} ;
list.next.next = {valeur : 3} ;
list.next.next.next = { valeur : 4 } ;
liste.next.next.next.next = null ; Ici, nous pouvons voir encore plus clairement qu'il existe plusieurs objets, chacun a une value et pointe next vers le voisin. 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ée en plusieurs parties, puis reconstituée ultérieurement :
laissez secondList = list.next.next; liste.next.next = null ;
Pour adhérer :
list.next.next = secondeList;
Et nous pouvons sûrement insérer ou supprimer des éléments n’importe où.
Par exemple, pour ajouter une nouvelle valeur, nous devons mettre à jour la tête de liste :
let list = { valeur : 1 } ;
list.next = {valeur : 2} ;
list.next.next = {valeur : 3} ;
list.next.next.next = { valeur : 4 } ;
// ajoute la nouvelle valeur à la liste
list = { valeur : "nouvel élément", suivant : liste } ; Pour supprimer une valeur du milieu, modifiez next de la précédente :
liste.suivant = liste.suivant.suivant;
Nous avons fait passer list.next de 1 à la valeur 2 . La valeur 1 est désormais 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 meilleures que les tableaux. Sinon, tout le monde n'utiliserait que des listes.
Le principal inconvénient est qu'on ne peut pas accéder facilement à un élément par son numéro. Dans un tableau, c'est simple : arr[n] est une référence directe. Mais dans la liste, nous devons commencer par le premier élément et next N fois pour obtenir le Nième élément.
…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 enrichies :
On peut ajouter la propriété prev en plus de next pour référencer l'élément précédent, pour revenir facilement en arrière.
Nous pouvons également ajouter une variable nommée tail référençant le dernier élément de la liste (et la mettre à jour lors de l'ajout/suppression d'éléments à la fin).
…La structure des données peut varier en fonction de nos besoins.
Termes:
La récursivité est un terme de programmation qui signifie appeler une fonction à partir d'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écursion . La base de la récursivité réside dans les arguments de fonction qui rendent la tâche si simple que la fonction ne fait plus d'appels.
Une structure de données définie de manière récursive 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 constituée d'un objet référençant une liste (ou null).
liste = { valeur, suivant -> liste }Les arbres comme l'arbre des éléments HTML ou l'arbre des départements de ce chapitre sont également naturellement récursifs : ils ont des branches et chaque branche peut avoir d'autres branches.
Des fonctions récursives peuvent être utilisées pour les parcourir comme nous l'avons vu dans l'exemple sumSalary .
Toute fonction récursive peut être réécrite en une fonction itérative. Et c'est parfois nécessaire pour optimiser les choses. Mais pour de nombreuses tâches, une solution récursive est suffisamment rapide et plus facile à écrire et à prendre en charge.
importance : 5
Écrivez une fonction sumTo(n) qui calcule la somme des nombres 1 + 2 + ... + n .
Par exemple:
sommeÀ(1) = 1 sommeÀ(2) = 2 + 1 = 3 sommeÀ(3) = 3 + 2 + 1 = 6 sommeÀ(4) = 4 + 3 + 2 + 1 = 10 ... sommeÀ(100) = 100 + 99 + ... + 2 + 1 = 5050
Faites 3 variantes de solution :
Utiliser une boucle for.
En utilisant une récursion, faites sumTo(n) = n + sumTo(n-1) for n > 1 .
Utiliser la formule de progression arithmétique.
Un exemple du résultat :
function sumTo(n) { /*... votre code ... */ }
alerte( sumTo(100) ); // 5050PS Quelle variante de solution est la plus rapide ? Le plus lent ? Pourquoi?
PPS Pouvons-nous utiliser la récursivité pour compter sumTo(100000) ?
La solution utilisant une boucle :
fonction sommeTo(n) {
soit somme = 0 ;
pour (soit i = 1; i <= n; i++) {
somme += je;
}
retourner la somme ;
}
alerte( sumTo(100) );La solution utilisant la récursion :
fonction sommeTo(n) {
si (n == 1) renvoie 1 ;
return n + sumTo(n - 1);
}
alerte( sumTo(100) ); La solution utilisant la formule : sumTo(n) = n*(n+1)/2 :
fonction sommeTo(n) {
renvoyer n * (n + 1) / 2 ;
}
alerte( sumTo(100) ); PS Naturellement, la formule est la solution la plus rapide. Il utilise seulement 3 opérations pour n’importe quel nombre n . Le calcul aide !
La variante en boucle est la deuxième en termes de vitesse. Dans les variantes récursive et en boucle, nous additionnons les mêmes nombres. Mais la récursivité implique des appels imbriqués et une gestion de la pile d'exécution. Cela demande également des ressources, donc c'est plus lent.
PPS Certains moteurs prennent en charge l'optimisation du « tail call » : si un appel récursif est le tout dernier de la fonction, sans aucun autre calcul effectué, alors la fonction externe n'aura pas besoin de reprendre l'exécution, donc le moteur n'aura pas besoin de le faire. rappelez-vous son contexte d’exécution. Cela supprime le fardeau de la mémoire. Mais si le moteur JavaScript ne prend pas en charge l'optimisation des appels de queue (la plupart d'entre eux ne le font pas), il y aura une erreur : taille maximale de la pile dépassée, car il existe généralement une limitation sur la taille totale de la pile.
importance : 4
La factorielle d'un nombre naturel est un nombre multiplié par "number minus one" , puis par "number minus two" , et ainsi de suite jusqu'à 1 . La factorielle de n est notée n!
Nous pouvons écrire une définition de factorielle comme ceci :
n! = n * (n - 1) * (n - 2) * ...*1
Valeurs des factorielles pour différents n :
1 ! = 1 2 ! = 2 * 1 = 2 3 ! = 3 * 2 * 1 = 6 4 ! = 4 * 3 * 2 * 1 = 24 5 ! = 5 * 4 * 3 * 2 * 1 = 120
La tâche consiste à écrire une fonction factorial(n) qui calcule n! en utilisant des appels récursifs.
alerte( factorielle(5) ); // 120
PS Indice : n! peut s'écrire n * (n-1)! Par exemple : 3! = 3*2! = 3*2*1! = 6
Par définition, une factorielle n! peut s'écrire n * (n-1)! .
En d’autres termes, le résultat de factorial(n) peut être calculé comme n multiplié par le résultat de factorial(n-1) . Et l'appel à n-1 peut descendre récursivement de plus en plus bas, jusqu'à 1 .
fonction factorielle(n) {
retourner (n != 1) ? n * factorielle(n - 1) : 1;
}
alerte( factorielle(5) ); // 120 La base de la récursion est la valeur 1 . Nous pouvons également faire 0 la base ici, cela n'a pas beaucoup d'importance, mais cela donne une étape récursive supplémentaire :
fonction factorielle(n) {
retourner n ? n * factorielle(n - 1) : 1;
}
alerte( factorielle(5) ); // 120importance : 5
La séquence de nombres de Fibonacci a la formule F n = F n-1 + F n-2 . Autrement dit, le nombre suivant est la somme des deux précédents.
Les deux premiers nombres sont 1 , puis 2(1+1) , puis 3(1+2) , 5(2+3) et ainsi de suite : 1, 1, 2, 3, 5, 8, 13, 21... .
Les nombres de Fibonacci sont liés au nombre d'or et à de nombreux phénomènes naturels qui nous entourent.
Écrivez une fonction fib(n) qui renvoie le n-th nombre de Fibonacci.
Un exemple de travail :
function fib(n) { /* votre code */ }
alerte(fib(3)); // 2
alerte(fib(7)); // 13
alerte(fib(77)); //5527939700884757 PS La fonction devrait être rapide. L'appel à fib(77) ne devrait pas prendre plus d'une fraction de seconde.
La première solution que nous pourrions essayer ici est la solution récursive.
Les nombres de Fibonacci sont récursifs par définition :
fonction fib(n) {
retourner n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
alerte( fib(3) ); // 2
alerte( fib(7) ); // 13
// fib(77); // sera extrêmement lent ! … Mais pour les grandes valeurs de n c'est très lent. Par exemple, fib(77) peut bloquer le moteur pendant un certain temps en consommant toutes les ressources du processeur.
C'est parce que la fonction effectue trop de sous-appels. Les mêmes valeurs sont réévaluées encore et encore.
Par exemple, voyons un morceau de calculs pour fib(5) :
... fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) ...
Ici, nous pouvons voir que la valeur de fib(3) est nécessaire à la fois pour fib(5) et fib(4) . Ainsi, fib(3) sera appelé et évalué deux fois de manière totalement indépendante.
Voici l'arbre de récursion complet :
On peut clairement remarquer que fib(3) est évalué deux fois et fib(2) est évalué trois fois. Le nombre total de calculs augmente beaucoup plus vite que n , ce qui le rend énorme même pour n=77 .
Nous pouvons optimiser cela en mémorisant les valeurs déjà évaluées : si une valeur, par exemple, fib(3) est calculée une fois, alors nous pouvons simplement la réutiliser dans des calculs futurs.
Une autre variante consisterait à abandonner la récursion et à utiliser un algorithme basé sur des boucles totalement différent.
Au lieu de passer de n à des valeurs inférieures, nous pouvons faire une boucle qui commence à partir de 1 et 2 , puis obtient fib(3) comme somme, puis fib(4) comme somme de deux valeurs précédentes, puis fib(5) et monte et monte, jusqu'à ce qu'il atteigne la valeur nécessaire. À chaque étape, nous n'avons besoin de mémoriser que deux valeurs précédentes.
Voici les étapes du nouvel algorithme en détail.
Le départ :
// a = fib(1), b = fib(2), ces valeurs sont par définition 1 soit a = 1, b = 1 ; // obtient c = fib(3) comme somme soit c = a + b ; /* nous avons maintenant fib(1), fib(2), fib(3) abc 1, 1, 2 */
Maintenant, nous voulons obtenir fib(4) = fib(2) + fib(3) .
Déplaçons les variables : a,b obtiendra fib(2),fib(3) , et c obtiendra leur somme :
une = b; // maintenant a = fib(2) b = c; // maintenant b = fib(3) c = une + b ; // c = fib(4) /* maintenant nous avons la séquence : abc 1, 1, 2, 3 */
L'étape suivante donne un autre numéro de séquence :
une = b; // maintenant a = fib(3)
b = c; // maintenant b = fib(4)
c = une + b ; // c = fib(5)
/* maintenant la séquence est (un nombre de plus) :
abc
1, 1, 2, 3, 5
*/… Et ainsi de suite jusqu'à ce que nous obtenions la valeur nécessaire. C'est beaucoup plus rapide que la récursivité et n'implique aucun calcul en double.
Le code complet :
fonction fib(n) {
soit a = 1 ;
soit b = 1;
pour (soit i = 3; i <= n; i++) {
soit c = a + b ;
une = b;
b = c;
}
retourner b ;
}
alerte( fib(3) ); // 2
alerte( fib(7) ); // 13
alerte( fib(77) ); //5527939700884757 La boucle commence par i=3 , car les première et deuxième valeurs de séquence sont codées en dur dans les variables a=1 , b=1 .
Cette approche est appelée programmation dynamique ascendante.
importance : 5
Disons que nous avons une liste à chaînage unique (comme décrit dans le chapitre Récursion et pile) :
laissez la liste = {
valeur : 1,
suivant: {
valeur : 2,
suivant: {
valeur : 3,
suivant: {
valeur : 4,
suivant: nul
}
}
}
} ; Écrivez une fonction printList(list) qui génère les éléments de la liste un par un.
Faites deux variantes de la solution : utiliser une boucle et utiliser la récursivité.
Quoi de mieux : avec ou sans récursivité ?
La variante basée sur une boucle de la solution :
laissez la liste = {
valeur : 1,
suivant: {
valeur : 2,
suivant: {
valeur : 3,
suivant: {
valeur : 4,
suivant: nul
}
}
}
} ;
fonction printList(liste) {
laissez tmp = liste ;
tandis que (tmp) {
alerte(tmp.value);
tmp = tmp.next;
}
}
printList(liste); Veuillez noter que nous utilisons une variable temporaire tmp pour parcourir la liste. Techniquement, nous pourrions utiliser une list de paramètres de fonction à la place :
fonction printList(liste) {
pendant que (liste) {
alerte(liste.value);
liste = liste.next;
}
} … Mais ce serait imprudent. Dans le futur, nous devrons peut-être étendre une fonction, faire autre chose avec la liste. Si nous changeons list , nous perdons cette capacité.
En parlant de bons noms de variables, list ici est la liste elle-même. Le premier élément de celui-ci. Et ça devrait rester comme ça. C'est clair et fiable.
De l'autre côté, le rôle de tmp est exclusivement un parcours de liste, comme i dans la boucle for .
La variante récursive de printList(list) suit une logique simple : pour afficher une liste, nous devons afficher l'élément actuel list , puis faire de même pour list.next :
laissez la liste = {
valeur : 1,
suivant: {
valeur : 2,
suivant: {
valeur : 3,
suivant: {
valeur : 4,
suivant: nul
}
}
}
} ;
fonction printList(liste) {
alerte(liste.value); // affiche l'élément actuel
si (liste.suivant) {
printList(list.next); // fais la même chose pour le reste de la liste
}
}
printList(liste);Maintenant, qu'est-ce qui est mieux ?
Techniquement, la boucle est plus efficace. Ces deux variantes font la même chose, mais la boucle ne dépense pas de ressources pour les appels de fonctions imbriquées.
D’un autre côté, la variante récursive est plus courte et parfois plus facile à comprendre.
importance : 5
Générer une liste à lien unique à partir de la tâche précédente Générer une liste à lien unique dans l'ordre inverse.
Faites deux solutions : utiliser une boucle et utiliser une récursion.
La logique récursive est ici un peu délicate.
Nous devons d’abord afficher le reste de la liste, puis afficher la liste actuelle :
laissez la liste = {
valeur : 1,
suivant: {
valeur : 2,
suivant: {
valeur : 3,
suivant: {
valeur : 4,
suivant: nul
}
}
}
} ;
fonction printReverseList(liste) {
si (liste.suivant) {
printReverseList(list.next);
}
alerte(liste.value);
}
printReverseList(liste);
La variante en boucle est également un peu plus compliquée que la sortie directe.
Il n'y a aucun moyen d'obtenir la dernière valeur de notre list . Nous ne pouvons pas non plus « revenir en arrière ».
Donc, ce que nous pouvons faire, c'est d'abord parcourir les éléments dans l'ordre direct et les mémoriser dans un tableau, puis afficher ce dont nous nous sommes souvenus dans l'ordre inverse :
laissez la liste = {
valeur : 1,
suivant: {
valeur : 2,
suivant: {
valeur : 3,
suivant: {
valeur : 4,
suivant: nul
}
}
}
} ;
fonction printReverseList(liste) {
soit arr = [];
laissez tmp = liste ;
tandis que (tmp) {
arr.push(tmp.value);
tmp = tmp.next;
}
pour (soit i = arr.length - 1; i >= 0; i--) {
alerte( arr[i] );
}
}
printReverseList(liste);Veuillez noter que la solution récursive fait exactement la même chose : elle suit la liste, mémorise les éléments de la chaîne d'appels imbriqués (dans la pile de contexte d'exécution), puis les affiche.