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 



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


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

VM379:3 Recursive: 1521.569091796875 ms




La tentative de calcul du 50e nombre a empêché l'onglet Chrome de répondre.

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 



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 environ 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 



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 :

Pour 0 et 1, nous renvoyons des tableaux codés en dur.
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 



Cette fonction fonctionne comme suit :

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

• Nous initialisons les variables prev et next pour stocker les valeurs précédentes et suivantes.
• Nous créons un 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 à jour avec les dernières nouvelles sur JavaScript et le développement de logiciels ! Rejoignez ma chaîne Telegram pour plus d'informations et de discussions : TechSavvy : Frontend & Backend.