Fibonacci, tu peux pas test

Ce billet date de plusieurs années, ses informations peuvent être devenues obsolètes.

Quand on me fait passer des tests, on me demande quasi systématiquement d'écrire un algorithme pour calculer la valeur des termes de la suite de Fibonacci.

Voici quelques notes (avec du JavaScript et du Python) que je relis avant de me faire cuisiner, sinon j'oublie :D

Algorithme

La suite de Fibonacci est une suite d'entiers qui commence par 0 et 1 et dont la valeur de chacun des termes suivants est la somme des deux termes précédents :

Fn = Fn-1 + Fn-2

C'est à dire :

n
(position dans la suite)
F
(valeur du terme)
Fn-1 + Fn-2
(somme des deux termes précédents)
0 0
1 1
2 1 1 + 0
3 2 1 + 1
4 3 2 + 1
5 5 3 + 2
6 8 5 + 3
7 13 8 + 5
8 21 13 + 8
9 34 21 + 13
Etc.

La récursivité

const fib = num => {
  console.log(`Performing fib(${num})`)
  if (num === 0) return 0
  if (num <= 2) return 1
  return fib(num - 1) + fib(num - 2)
}

Cette solution récursive est connue pour être mauvaise. On obtient un algorithme de type O(2N) au temps d'exécution exponentiel. Bonus : vous avez la classe quand vous dites O(2N) à votre interlocuteur, moi je le fais jamais :D

La potentielle profonde récursion de cette solution fait en outre courir le risque du dépassement de la limite de mémoire de la pile d'exécution (ou call stack, ou execution context dans la spécification ECMAScript). En effet, chaque fois qu'un programme fait un appel, il pousse un nouveau contexte d'exécution sous forme de bloc de pile (ou stack frame) en haut de la pile d'exécution. Or chaque bloc de pile occupe de la mémoire, et la mémoire n'est pas infinie.

Pour contourner ce problème, certains langages supportent la récursivité terminale (tail call optimization). Elle était supportée dans les versions 6 et 7 de Node.js mais la mayonnaise n'a pas pris. Peu d'autres moteurs JavaScript la supportent. En ce qui concerne Python, Guido l'a jugée unpythonic :)

Le calcul linéaire

C'est la solution que je trouve la plus rapide à écrire, à lire et à comprendre. Ci-dessous en Python :

def fib(n):
    a = 0
    b = 1
    for __ in range(n):
        a, b = b, a + b
    return a

Et en JavaScript :

const fib = n => {
  let a = 0
  let b = 1
  for (let __ of Array(n).keys()) {
    [a, b] = [b, a + b]
  }
  return a
}

On utilise le double underscore __ de façon idiomatique pour indiquer explicitement une variable inutilisée.

On utilise aussi une affectation simultanée en Python, l'astuce est de comprendre l'ordre d'évaluation : de gauche à droite, et quand il y a une affectation c'est d'abord le côté droit qui est évalué avant le côté gauche. On peut avoir le même résultat en JavaScript en utilisant l'affectation par décomposition. Vous pouvez éventuellement vous passer d'un one liner mais il vous faudra utiliser une variable supplémentaire :

let sum = a + b;
a = b;
b = sum;

À partir de fib(79), JavaScript n'est plus capable de représenter le résultat de façon sûre car on dépasse la valeur sûre maximale d'un nombre entier que JavaScript est capable de représenter : fib(79) > Number.MAX_SAFE_INTEGER. Avec Python, on a encore de la marge :)

Le reste

  • on peut améliorer la solution du calcul linéaire avec des générateurs
  • les autres algorithmes sont présentés sur la page Wikipedia, je vais pas tous les copier-coller quand même
  • si je n'étais pas une telle pine d'huître en math, j'utiliserais le calcul matriciel

Avant 10 ans de freelancing, goodbye Paris Après Héritage et classes en JavaScript

Tag Kemar Joint