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?
Différence entre récursion et itérationDifférence entre récursivité et itérationLa récursivité et l’itération exécutent plusieurs fois un ensemble d’instructions. La récursivité se produit lorsqu’une instruction dans une fonction s’appelle elle-même plusieurs fois. L’itération est…Lire plus Nous pouvons utiliser la récursivité dans la programmation dynamique. La plupart des problèmes lié à la programmation dynamique peuvent être résolus par une récursion descendante ou une approche ascendante mettant en cache les résultats intermédiaires, une technique appelée « Mémorisation ».
 
 
Vous pouvez également mettre en cache les résultats en utilisant la récursivité.
 
Une différence majeure en utilisant ces deux méthodes pour résoudre un problème est la suivante, dans une approche «récursive descendante», vous ne devez pas calculer tous les sous-problèmes, vous ne calculez que les sous-problèmes dont vous avez besoin pour la solution finale en éliminant certains sous-problèmes.
 
Dans l’approche ascendante, vous calculez tous les sous-problèmes, qu’ils soient utilisés ou non dans la solution finale. Cette différence peut ne pas être pertinente dans tous les problème.
 
Nous allons illustrer par un simple exemple. Voici deux fonctions pour calculer les coefficients binomiaux: le premier programme utilise la récursivité, le deuxième utilise la programmation dynamique.
 

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.
 
 

Partagez cet article

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *