Les dangers de la récursivité

La programmation dynamique consiste à ramener la résolution d’un problème à celle de sous-problèmes de taille inférieure, mais non indépendants (c’est la différence avec la méthode « diviser pour régner ». La récursivité, qui conduirait à un complexité exponentielle doit donc être évitée. En général, on procède aux étapes suivantes :

  • exprimer par récurrence la solution du problème en fonction de celle de sous-problèmes ;
  • initialiser un tableau avec les conditions initiales vues à la première étape ;
  • remplir progressivement ce tableau par taille croissante de sous-problème, avec la récurrence vue en étape 1.

7.1.1 Deux fonctions pour mesurer le temps qui passe

On écrit la fonction test1 telle que test1 f x renvoie le couple {(f(x),t),} où {f} est une fonction{,x} un argument de {f,} et où

{t} est le temps (exprimé en secondes) nécessaire au calcul de expression {f(x).} De même, l’expression test2 f x y renvoie {(f(x,y),t),} où {f} est une fonction{,x,y} ses deux arguments, et {t} est le temps

(exprimé en secondes) nécessaire au calcul de l’expression {f(x,y).}

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :