Différence entre la programmation dynamique et la récursivité

La récursivité une technique de programmation dans laquelle une méthode peut s’appeler elle-même pour résoudre un problème. Ce terme n’est pas lié à la programmation dynamique, comme si on pose la question quelle est différence entre la récursivité et l’itération?

Récursivité

int binom(int x, int y) {
     if (y==0 || y==x) 
           return 1;
     else 
          return binom(x-1,y-1)+binom(x-1,y);
}

Programmation dynamique

int binom(int x, int y) {
     int tab[x+1][x+1];
     for (int i=0; i<=x; i++) {
          for (int j=0; j<=i; j++) {
               if (j==0 || j==i)
                   tab[i][j] = 1;
               else 
                  tab[i][j] = tab[i-1][j-1] + tab[i-1][j];
          }
     }
     return tab[x][y];
}

 
Comme vous pouvez le constater, les deux fonctions font exactement la même chose, de la même manière. Mais le deuxième est beaucoup plus rapide (utilise beaucoup plus de mémoire), car les « appels récursifs » se déroulent en un temps constant (ils n’accèdent qu’à un tableau).
 

Conclusion

La programmation dynamique est un cas particulier de la récursivité. Dans la récursivité, s’il existe des sous-problèmes résolus plusieurs fois, vous stockez les résultats au lieu de les recalculer. Le fait de rappeler s’appelle Memoization. Tout ce processus s’appelle la programmation dynamique.