De la récursion naïve à la programmation dynamique

Comment un ordinateur calcule-t-il F(n) ? La traduction directe de la définition est récursive :

   fib(n) :
       si n < 2 : renvoyer n
       sinon    : renvoyer fib(n-1) + fib(n-2)

Simple, mais désastreux. Pour calculer fib(5), l'arbre des appels recalcule sans cesse les mêmes valeurs :

                fib(5)
              /        \
          fib(4)       fib(3)
          /    \        /    \
      fib(3) fib(2)  fib(2) fib(1)
       /   \
   fib(2)  fib(1)

fib(3) est recalculé plusieurs fois, fib(2) encore davantage. Le nombre d'appels enfle presque au rythme de φ à chaque étage : le coût est exponentiel, de l'ordre de φ^n. Calculer fib(50) ainsi demande déjà des milliards d'appels.

La parade porte un nom : la programmation dynamique. Son principe : ne jamais recalculer deux fois la même sous-valeur. Deux variantes :

• Mémoïsation : on garde en mémoire chaque résultat déjà obtenu, et on le réutilise.
• Itération ascendante : on remonte de F(0) vers F(n) en ne conservant que les deux derniers termes.

   a, b = 0, 1
   repeter n fois :  a, b = b, a + b
   renvoyer a

Coût : linéaire — n additions — et mémoire constante. On passe de milliards d'opérations à quelques dizaines. C'est l'exemple canonique de la programmation dynamique : il montre pourquoi « recalculer » est l'ennemi, et pourquoi mémoriser les sous-résultats change radicalement la donne.