23 novembre 2020

Récursion et pile

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

Notre premier sujet sera la recursion.

Si vous n’êtes pas novice en programmation, cela vous est probablement familier et vous pouvez sauter ce chapitre.

La récursion 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 simple. 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, pour traiter certaines structures de données.

Lorsqu’une fonction résout une tâche, elle peut appeler de nombreuses autres fonctions. Cela se produit partiellement lorsqu’une fonction s’appelle elle-même. Cela s’appelle la récursion.

Deux façons de penser

Prenons quelque chose de simple pour commencer – écrivons une fonction pow(x, n) qui élève x à une puissance naturel de n. En d’autres termes, multiplie x par lui-même n fois.

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

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

  1. La pensée itérative: la boucle for:

    function pow(x, n) {
      let result = 1;
    
      // multiplier le résultat par x n fois dans la boucle
      for (let i = 0; i < n; i++) {
        result *= x;
      }
    
      return result;
    }
    
    alert( pow(2, 3) ); // 8
  2. La pensée récursive: simplifie la tâche et s’appele elle-même:

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

Veuillez noter en quoi la variante récursive est fondamentalement différente.

Quand pow(x, n) est appelé, l’exécution se scinde en deux branches:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)
  1. Si n == 1, alors tout est trivial. On l’appelle la base de la récursion, car elle produit immédiatement le résultat évident: pow(x, 1) équivaut à x.
  2. Sinon, nous pouvons représenter pow(x, n) comme x * pow(x, n - 1). En maths, on écrirait xn = x * xn-1. Ceci s’appelle une étape récursive: nous transformons la tâche en une action plus simple (multiplication par x) et un appel plus simple de la même tâche (pow avec le petit n). Les prochaines étapes le simplifient de plus en plus jusqu’à ce que n atteigne 1.

On peut aussi dire que pow s’appelle récursivement jusqu’à ce que n == 1.

Par exemple, pour calculer pow(2, 4) la variante récursive effectue 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

Ainsi, la récursion réduit un appel de fonction à un processus plus simple, puis – à un processus encore plus simple, etc. jusqu’à ce que le résultat devienne évident.

La récursion 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:

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

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

La profondeur maximale de récursion est limitée par le moteur JavaScript. Nous sommes sur qu’il va jusqu’à 10000, certains moteurs en autorisent plus, mais 100000 est probablement hors limite pour la majorité d’entre eux. Il existe des optimisations automatiques qui aident à atténuer ce problème (“optimisation 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écursion, mais cela reste très large. Il y a beaucoup de tâches pour lesquelles la pensée récursive donne un code plus simple et plus facile à gérer.

Le contexte d’exécution et la pile

Voyons maintenant comment fonctionnent les 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 contenant des détails sur l’exécution d’une fonction: où le flux de contrôle est maintenant, 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 en cours est suspendue.
  • 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 extrait de la pile et la fonction externe reprend à partir de son point d’arrêt.

Voyons ce qui se passe pendant l’appel de pow(2, 3).

pow(2, 3)

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

Nous pouvons l’esquisser comme:

  • Context: { x: 2, n: 3, at line 1 } pow(2, 3)

C’est à ce moment que la fonction commence à s’exécuter. La conditionn == 1 est faux, donc le flux continue dans la deuxième branche de 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 la ligne change, le contexte est donc le suivant:

  • Context: { x: 2, n: 3, at line 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).

pow(2, 2)

Pour effectuer un appel imbriqué, JavaScript se souvient du contexte d’exécution actuel dans le contexte d’exécution de la pile.

Ici, nous appelons la même fonction pow, mais cela n’a absolument aucune 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. Quand le sous-appel est fini – le contexte précédent est extrait de la pile et son exécution se poursuit.

Voici la pile de contexte lorsque nous sommes entrés dans le sous-appel pow(2, 2):

  • Context: { x: 2, n: 2, at line 1 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Le nouveau contexte d’exécution actuel est en haut (et en gras) et les contextes précédemment mémorisés sont en dessous.

Quand on termine le sous-appel – il est facile de reprendre le contexte précédent, car il conserve les deux variables et l’emplacement exact du code où il s’est arrêté.

Veuillez noter :

Ici, dans l’image, nous utilisons le mot “line”, comme dans notre exemple, il n’y a qu’un seul sous-appel en 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”.

pow(2, 1)

Le processus se répète: un nouveau sous-appel 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 placé en haut de la pile:

  • Context: { x: 2, n: 1, at line 1 } pow(2, 1)
  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

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

La sortie

Pendant l’exécution de pow(2, 1), contrairement à avant, la condition n == 1 est la vérité, donc la première branche de if fonctionne:

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

Il n’y a plus d’appels imbriqués, donc la fonction se termine en renvoyant2.

Lorsque la fonction se termine, son contexte d’exécution n’est plus nécessaire, il est donc supprimé de la mémoire. La précédente est restaurée en haut de la pile:

  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

L’exécution de pow(2, 2) est repris. Il a le résultat du sous-appel pow(2, 1), de sorte qu’il peut également terminer l’évaluation de x * pow(x, n - 1), retournant 4.

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

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Quand il 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 dans 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, augmenter à la puissance de n nécessite en réalité de la mémoire pour les contextes n, pour toutes les valeurs inférieures de n.

Un algorithme basé sur des boucles est plus économe en mémoire:

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Le pow itératif utilise un contexte unique qui change les processus i et result dans le processus. Ses besoins en mémoire sont faibles, fixes et ne dépendent pas de n.

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

…Parfois, la réécriture n’est pas 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 création de branche est plus complexe. Et l’optimisation risque de ne pas être nécessaire et de ne pas valoir la peine.

La récursion peut donner un code plus court, plus facile à comprendre et à supporter. Les optimisations ne sont pas nécessaires à chaque endroit, nous avons surtout besoin d’un bon code, c’est pourquoi il est utilisé.

Traversées récursives

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

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

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

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

  • Un département peut avoir un tableau de personnel. Par exemple, le département des ventes compte 2 employés: John et Alice.

  • Ou bien un département peut être divisé en sous-départements, comme development a deux branches: sites et internes. Chacun d’entre eux a son propre personnel.

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

    Par exemple, le département sites peut être divisé en équipes pour les sites siteA et siteB. Et, potentiellement, ils peuvent être diviser encore plus. Ce n’est pas sur la photo, c’est juste quelque chose qu’ont pourrait immaginer.

Maintenant, disons que nous voulons une fonction pour obtenir la somme de tous les salaires. Comment peut-on faire ça?

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é sur les départements de premier niveau. Mais ensuite, nous avons besoin de plus de sous-boucles imbriquées pour parcourir le personnel des départements de second niveau, tels que les sites… Et puis une autre sous-boucle dans ceux des départements de 3ème niveau qui pourraient apparaître dans le futur ? Si nous mettons 3-4 sous-boucles imbriquées dans le code pour traverser un seul objet, cela devient plutôt moche.

Essayons la récursion.

Comme nous pouvons le constater, lorsque notre fonction demande à un département de faire la somme, il existe deux cas possibles:

  1. S’il s’agit d’un “simple” département avec un tableau de personnes, nous pouvons alors additionner les salaires en une simple boucle.
  2. Ou bien c’est un objet avec N sous-départements – alors nous pouvons faire des appelsN récursifs pour obtenir la somme de chaque sous-étape et combiner les résultats.

Le premier cas est la base de la récursivité, le cas trivial, lorsque nous obtenons un tableau.

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

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

let company = { // le même objet, compressé pour la brièveté
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// La fonction pour faire le travail
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // additionne le tableau
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // appel récursivement pour les sous-départements, additionnez les résultats
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

Le code est court et facile à comprendre (tout va bien?). C’est le pouvoir de la récursion. Cela fonctionne également pour tous les niveaux d’imbrication de sous-départements.

Voici le schéma des appels:

On peut facilement voir le principe: pour un objet {...} les sous-appels sont faits, alors que les tableaux [...] sont les “feuilles” de l’arbre de récurrence, elles donnent un résultat immédiat.

Notez que le code utilise des fonctionnalités intelligentes que nous avons déjà abordées:

  • La méthode arr.reduce a été expliquée dans le chapitre Méthodes de tableau pour obtenir la somme du tableau.
  • La boucle for(val of Object.values(obj)) itérer sur les valeurs d’objet: Object.values retourne un tableau d’eux-mêmes.

Structures récursives

Une structure de données récursive (définie de manière récursive) 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 éventail de personnes.
  • Ou un objet avec des départements.

Pour les développeurs Web, il existe des exemples bien mieux 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 (pouvant à leur tour contenir des morceaux de texte/commentaires ou d’autres balises, etc.).

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

Pour une meilleure compréhension, nous allons couvrir une autre structure récursive nommée “Liste chaînée” qui pourrait être une meilleure alternative aux tableaux dans certains cas.

Liste chaînée

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

Le choix naturel serait un tableau:

let arr = [obj1, obj2, obj3];

… Mais il y a un problème avec les tableaux. Les opérations “delete element” et “insert element” 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 nouvel obj, et si le tableau est grand, cela prend du temps. Même chose avec arr.shift().

Les seules modifications structurelles ne nécessitant pas de renumérotation en masse sont celles qui fonctionnent 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 sont début.

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

L’élémentde la liste liée est défini de manière récursive en tant qu’objet avec:

  • value.
  • next propriété référençant le prochain élément de liste liée ou null si c’est la fin.

Par exemple:

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

Représentation graphique de la liste:

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;

Ici, nous pouvons voir encore plus clairement qu’il y a plusieurs objets, chacun ayant les valeurs value etnext pointant vers le voisin. La variable list est le premier objet de la chaîne. Par conséquent, en suivant les pointeurs next, nous pouvons atteindre n’importe quel élément.

La liste peut être facilement divisée en plusieurs parties et ultérieurement réunie:

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

Pour joindre:

list.next.next = secondList;

Et nous pouvons sûrement insérer ou retirer des objets n’importe où.

Par exemple, pour ajouter une nouvelle valeur, nous devons mettre à jour la tête de la liste:

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

// ajoute la nouvelle valeur à la liste
list = { value: "new item", next: list };

Pour supprimer une valeur du milieu, changez le next de la précédente:

list.next = list.next.next;

List.next a sauté 1 à la valeur 2. La valeur 1 est maintenant exclue de la chaîne. Si elle n’est pas stocké ailleurs, elle 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 que nous ne pouvons pas facilement accéder à un élément par son numéro. Dans un tableau simple: arr [n] est une référence directe. Mais dans la liste, nous devons commencer à partir du premier élément et aller next``N fois pour obtenir le Nième élément.

…Mais nous n’avons pas toujours besoin de telles opérations. Par exemple, quand on a besoin d’une file d’attente ou même d’un deque – la structure ordonnée qui doit permettre l’ajout/suppression très rapide d’éléments des deux extrémités, mais l’accès au milieu n’est pas nécessaire.

Les listes peuvent être améliorées:

  • Nous pouvons ajouter la propriété prev en plus de next pour référencer l’élément précédent, pour revenir facilement.
  • Nous pouvons également ajouter une variable nommée tail faisant référence au dernier élément de la liste (et la mettre à jour lors de l’ajout/suppression d’éléments de la fin).
  • … La structure de données peut varier en fonction de nos besoins.

Résumé

Terms:

  • Recursion est un terme de programmation qui signifie q’une fonction s’appelle 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écursion est constituée par les arguments de la fonction qui rendent la tâche si simple que la fonction ne fait plus d’appels.

  • Une structure de données de Type récursif est une structure de données qui peut être définie à l’aide de elle-même.

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

    list = { value, next -> list }

    Les arbres tels que l’arbre des éléments HTML ou l’arbre des départements de ce chapitre sont également naturellement récursifs: ils ont des branchent 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 assez rapide et plus facile à écrire et à supporter.

Exercices

importance: 5

Écrire une fonction sumTo(n) qui calcule la somme des nombres 1 + 2 + ... + n.

Par exemple:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Faites 3 variantes de solution:

  1. Utiliser une boucle for.
  2. Utiliser une récursion, avec sumTo(n) = n + sumTo(n-1) pour n > 1.
  3. Utiliser la formule de progression arithmétique.

Un exemple de résultat:

function sumTo(n) { /*... ton code ... */ }

alert( sumTo(100) ); // 5050

P.S. Quelle solution est la plus rapide? La plus lente? Pourquoi?

P.P.S. Peut-on utiliser la récursion pour compter sumTo(100000)?

La solution utilisant une boucle:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

La solution utilisant la récursion:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

La solution utilisant la formule: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

P.S. Naturellement, la formule est la solution la plus rapide. Elle n’utilise que 3 opérations pour n’importe quel nombre n. Le calcul aide!

La variante de boucle est la seconde en termes de vitesse. Dans la variante récursive et la variante de boucle, nous additionnons les mêmes nombres. Mais la récursion implique des appels imbriqués et la gestion de la pile d’exécution. Donc, cela prend des ressources, donc c’est plus lent.

P.P.S. Certains moteurs prennent en charge l’optimisation du “tail call (dernier appel)”: si un appel récursif est le dernier de la fonction (comme dans la somme ci-dessus), le moteur n’a pas besoin de reprendre son contexte d’exécution. Cela supprime la charge en mémoire, donc compter sumTo (100000) devient possible. Toutefois, si le moteur JavaScript ne prend pas en charge l’optimisation des appels en bout de ligne, il y aura une erreur: maximum stack size exceeded (la taille maximale de la pile est dépassée), car la taille totale de la pile est généralement limitée.

importance: 4

Le factorielle d’un nombre naturel est multiplié par "nombre moins un", ensuite par "nombre moins deux", et ainsi de suite jusqu’à 1. La factorielle de n est noté comme n!

Nous pouvons écrire une définition de factorielle comme ceci:

n! = n * (n - 1) * (n - 2) * ...*1

Valeurs des factorielles pour des n différents:

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 est d’écrire une fonction factorial(n) qui calcule n! en utilisant des appels récursifs.

alert( factorial(5) ); // 120

P.S. Indice: n! peut être écrit n * (n-1)! Par exemple: 3! = 3*2! = 3*2*1! = 6

Par définition, une factorielle est n! peut être écrit 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 de n-1 peut récursivement descendre plus bas, et plus bas, jusqu’à 1.

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

La base de la récursivité est la valeur 1. Nous pouvons aussi faire de 0 la base ici, ça importe peu, mais donne une étape récursive supplémentaire:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120
importance: 5

La séquence des Numéros de Fibonacci a la formule Fn = Fn-1 + Fn-2. En d’autres termes, le nombre suivant est la somme des deux précédents.

Les deux premiers chiffres sont 1, puis 2(1+1), ensuite 3(1+2), 5(2+3) etc: 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 autour de nous.

Écrire une fonction fib(n) qui retourne le Numéro de Fibonacci n-th.

Un exemple de travail:

function fib(n) { /* votre code */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

P.S. La fonction devrait être rapide. L’appel de fib(77) devrait prendre pas 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:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( 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 crée trop de sous-appels. Les mêmes valeurs sont réévaluées encore et encore.

Par exemple, voyons un calcul 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 pour les deux fib(5) et fib(4). Alors fib(3) sera appelé et évalué deux fois de manière totalement indépendante.

Voici l’arbre de récursion complet:

Nous pouvons clairement remarquer que fib(3) est évalué deux fois et fib(2) est évalué trois fois. La quantité totale de calculs augmente beaucoup plus vite que n, le rendant énorme même pour n=77.

Nous pouvons optimiser cela en nous rappelant les valeurs déjà évaluées: si une valeur de fib(3) est calculé une fois, alors nous pouvons simplement le réutiliser dans les calculs futurs.

Une autre variante consisterait à abandonner la récursion et à utiliser un algorithme totalement différent basé sur des boucles.

Au lieu de partir de n jusqu’à des valeurs plus basses, nous pouvons faire une boucle qui commence à partir de 1 et 2, puis obtient fib(3) comme leur somme, ensuite fib(4) comme la somme de deux valeurs précédentes, ensuite fib(5) et monte, jusqu’à ce qu’il atteigne la valeur nécessaire. À chaque étape, il suffit de rappeler deux valeurs précédentes.

Voici les étapes du nouvel algorithme en détails.

Le début:

// a = fib(1), b = fib(2), ces valeurs sont par définition 1
let a = 1, b = 1;

// obtien c = fib(3) comme leur somme
let c = a + b;

/* nous avons maintenant fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/

Maintenant, nous voulons obtenir fib(4) = fib(2) + fib(3).

Passons aux variables: a,b aura fib(2),fib(3), et c obtiendra leur somme:

a = b; // maintenant a = fib(2)
b = c; // maintenant b = fib(3)
c = a + b; // c = fib(4)

/* maintenant nous avons la séquence:
   a  b  c
1, 1, 2, 3
*/

L’étape suivante donne un autre numéro de séquence:

a = b; // maintenant a = fib(3)
b = c; // maintenant b = fib(4)
c = a + b; // c = fib(5)

/* maintenant la séquence est (encore un numéro):
      a  b  c
1, 1, 2, 3, 5
*/

…Et ainsi de suite jusqu’à l’obtention de la valeur nécessaire. C’est beaucoup plus rapide que la récursion et n’implique aucun calcul en double.

Le code complet:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

La boucle commence par i=3, parce que les première et deuxième valeurs de séquence sont codées en dur dans des variables a=1, b=1.

Cette approche s’appelle la programmation dynamique de bas en haut.

importance: 5

Disons que nous avons une liste de simple lien (comme décrit dans le chapitre Récursion et pile):

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

Écrire une fonction printList(list) qui sort les éléments de la liste un par un.

Faites deux variantes de la solution: en utilisant une boucle et en utilisant la récursion.

Qu’est-ce qui est le mieux: Avec ou sans récursion ?

Solution basée sur la boucle

La variante de la solution basée sur la boucle:

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

Veuillez noter que nous utilisons une variable temporaire tmp pour parcourir la liste. Techniquement, nous pourrions utiliser un paramètre de fonction list à la place:

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

…Mais ce ne serait pas sage. Dans le futur, nous allons peut-être devoir étendre une fonction, faire autre chose avec la liste. Si nous changeons list, alors nous perdons cette capacité.

Parlant des bons noms de variables, list 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 une liste de traversée, comme i dans la boucle for.

Solution récursive

La variante récursive de printList(list) suit une logique simple: pour afficher une liste, il faut afficher l’élément courant list, puis faire de même pour list.next:

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

function printList(list) {

  alert(list.value); // affiche l'élément en cours

  if (list.next) {
    printList(list.next); // fait la même chose pour le reste de la liste
  }

}

printList(list);

Maintenant qu’est-ce qui est le 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 fonction imbriqués.

De l’autre côté, la variante récursive est plus courte et parfois plus facile à comprendre.

importance: 5

Afficher une liste à lien unique de la tâche précédente Produire une liste de simple lien dans l’ordre inverse.

Faites deux solutions: en utilisant une boucle et en utilisant une récursion.

Utiliser une récursion

La logique récursive est un peu délicate ici.

Nous devons d’abord afficher le reste de la liste et ensuite afficher l’actuel:

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

En utilisant une boucle

La variante de boucle est aussi 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”.

Nous pouvons donc commencer par parcourir les éléments dans l’ordre direct et les mémoriser dans un tableau, puis afficher ce que nous nous sommes rappelés dans l’ordre inverse:

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

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

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 affiches.

Carte du tutoriel

Commentaires

lire ceci avant de commenter…
  • Si vous avez des améliorations à suggérer, merci de soumettre une issue GitHub ou une pull request au lieu de commenter.
  • Si vous ne comprenez pas quelque chose dans l'article, merci de préciser.
  • Pour insérer quelques bouts de code, utilisez la balise <code>, pour plusieurs lignes -- enveloppez-les avec la balise <pre>, pour plus de 10 lignes - utilisez une sandbox (plnkr, jsbin, codepen…)