Implémentation de la séquence de Fibonacci en JavaScript : approches et variations courantes

En tant que développeur, vous avez probablement rencontré la tâche d'écrire une fonction pour calculer les valeurs de la séquence de Fibonacci. Ce problème classique apparaît souvent lors des entretiens de codage, demandant généralement une implémentation récursive. Cependant, les enquêteurs peuvent parfois demander des approches spécifiques. Dans cet article, nous explorerons les implémentations de séquences de Fibonacci les plus courantes en JavaScript.

Qu'est-ce que la séquence de Fibonacci ?

Tout d’abord, rafraîchissons-nous la mémoire. La suite de Fibonacci est une suite de nombres où chaque nombre est la somme des deux précédents. Cela commence par 0 et 1 :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…

Approches communes de mise en œuvre

1. Approche récursive

La requête la plus traditionnelle concerne une implémentation récursive :

function fibonacciRecursive(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

Bien que simple, cette approche n'est pas performante pour les grandes valeurs de n. Sur un MacBook Pro i9 avec 16 Go de RAM, le calcul du 40ème nombre de Fibonacci a pris environ 1,5 seconde :

console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms

En tentant de calculer le 50e nombre, l'onglet Chrome ne répondait plus.

2. Approche récursive avec mise en cache (mémoïsation)

La prochaine variante de cette question consiste à améliorer les performances en ajoutant un mécanisme de mise en cache à notre implémentation récursive :

function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  if (cached[n]) {
    return cached[n];
  }

  cached[n] = 
    fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached);

  return cached[n];
}

Cette approche introduit un objet mis en cache avec des valeurs initiales pour 0 et 1. Pour un nombre donné, nous vérifions d'abord si nous avons déjà calculé sa valeur de Fibonacci. Si tel est le cas, nous renvoyons le résultat mis en cache au lieu de le recalculer. Sinon, nous calculons cette valeur et la stockons en cache.

L'amélioration des performances est significative (en raison de la mémoire supplémentaire utilisée, bien sûr). Le calcul du 40ème nombre de Fibonacci a pris ~0,02 ms :

console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms

3. Approche itérative avec une boucle for

Une autre variante courante consiste à implémenter la séquence de Fibonacci à l'aide d'une boucle for :

function fibonacciWithIteration(n) {
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let prev = 0;
    let next = 1;
    let result = 1;

    for (let i = 2; i <= n; i++) {
        result = prev + next;
        [prev, next] = [next, prev + next];
    }
    return result;
}

Cette approche est beaucoup plus rapide que la méthode récursive de base (celle sans mise en cache) :

console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms

L'approche itérative peut gérer efficacement de très grandes valeurs d'entrée :

console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e+292
VM325:23 With iteration: 0.5830078125 ms

Bonus : renvoyer la séquence de Fibonacci sous forme de tableau

Les enquêteurs peuvent également vous demander de renvoyer la séquence entière de Fibonacci jusqu'au n-ième nombre sous forme de tableau. Implémentons cela en utilisant des approches à la fois récursives et itératives.

Approche récursive

function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1] + arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]

Cette fonction fonctionne comme suit :

1. Pour 0 et 1, nous renvoyons des tableaux codés en dur.
2. Pour les autres cas :

• Nous obtenons la séquence du numéro précédent et la stockons dans arr.
• Nous calculons currentValue en additionnant les deux dernières valeurs de arr.
• Nous combinons arr et currentValue dans un nouveau tableau et le renvoyons.

Approche itérative

function fibonacciSequenceWithIteration(n) {
  if (n < 1) {
    return [0];
  }

  let prev = 0;
  let next = 1;
  const arr = [prev, next];

  for (let i = 2; i <= n; i++) {
    arr.push(prev + next);
    [prev, next] = [next, prev + next];
  }
  return arr;
}

console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]

Cette fonction fonctionne comme suit :

1. Si l'entrée est 0, nous renvoyons un tableau avec uniquement l'élément 0.
2. Pour les autres cas :

• Nous initialisons les variables prev et next pour stocker les valeurs précédentes et suivantes.
• Nous créons arr avec les valeurs initiales [0, 1].
• Nous itérons de 2 à n, en poussant la somme de prev et next à arr à chaque itération.
• Nous mettons à jour les valeurs précédentes et suivantes et passons à l'itération suivante.

Conclusion

Bien que cet article couvre plusieurs implémentations courantes de séquences de Fibonacci, il ne s’agit pas d’une liste exhaustive. Si vous avez rencontré d'autres variations dans les entretiens ou dans votre travail, partagez-les dans les commentaires !

Restez informé des dernières nouvelles concernant JavaScript et le développement de logiciels ! Rejoignez ma chaîne Telegram pour plus d'informations et de discussions : TechSavvy : Frontend & Backend.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!