Récursivité et Programmation Dynamique

Ce document traite des concepts fondamentaux de la récursivité et de la programmation dynamique, destinés aux étudiants en algorithmique avancée. Il présente les définitions, exemples, algorithmes et principes clés pour comprendre et appliquer ces techniques dans la résolution de problèmes informatiques.

Récursivité

Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même. Il résout un problème en calculant des solutions d’instances plus petites du même problème. Un algorithme récursif est obligatoirement une fonction.

Exemple classique : la fonction puissance xⁿ définie récursivement par :

xⁿ = {
  1 si n = 0 ;
  x × xⁿ⁻¹ si n ≥ 1
}

L’algorithme correspondant s’écrit :

PUISSANCE(x, n)
if (n == 0) return 1;
else return x * PUISSANCE(x, n - 1);

Récursivité multiple

Une définition récursive peut contenir plusieurs appels récursifs. Par exemple, le calcul des combinaisons C(n, p) selon la relation de Pascal :

C(n, p) = {
  1 si p = 0 ou p = n ;
  C(n - 1, p) + C(n - 1, p - 1) sinon
}

Algorithme :

COMBINAISON(n, p)
if (p == 0 || p == n) return 1;
else return COMBINAISON(n - 1, p) + COMBINAISON(n - 1, p - 1);

Récursivité mutuelle

Des définitions sont dites mutuellement récursives si elles dépendent les unes des autres. Par exemple, la parité :

pair(n) = {
  vrai si n = 0 ;
  impair(n - 1) sinon
}

impair(n) = {
  faux si n = 0 ;
  pair(n - 1) sinon
}

Algorithmes correspondants :

PAIR(n)
if (n == 0) return true;
else return IMPAIR(n - 1);

IMPAIR(n)
if (n == 0) return false;
else return PAIR(n - 1);

Récursivité imbriquée : fonction d’Ackermann

Un exemple de récursivité imbriquée est la fonction d’Ackermann, définie par :

A(m, n) = {
  n + 1 si m = 0 ;
  A(m - 1, 1) si m > 0 et n = 0 ;
  A(m - 1, A(m, n - 1)) sinon
}

Algorithme :

ACKERMANN(m, n)
if (m == 0) return n + 1;
else if (n == 0 && m > 0) return ACKERMANN(m - 1, 1);
else return ACKERMANN(m - 1, ACKERMANN(m, n - 1));

Non-décidabilité de la terminaison

Il est impossible d’écrire un programme qui vérifie automatiquement si un programme donné P termine sur un jeu de données D. La démonstration par contradiction utilise un programme Q qui appelle ce vérificateur, montrant que la terminaison est un problème indécidable.

Programmation Dynamique

La programmation dynamique est une méthode d’optimisation introduite par Bellman dans les années 50. Elle est une adaptation de la méthode diviser pour régner, mais contrairement à cette dernière (qui est récursive et descendante), la programmation dynamique calcule les solutions de bas en haut.

Elle est particulièrement utile lorsque la résolution d’un sous-problème dépend de celle d’autres sous-problèmes, et permet d’éviter les calculs redondants en mémorisant les résultats intermédiaires.

Étapes de la programmation dynamique

1. Obtenir l’équation récursive liant la solution d’un problème à celle de ses sous-problèmes.
2. Initialiser une table selon les conditions initiales de l’équation.
3. Remplir progressivement la table en résolvant les sous-problèmes de taille croissante.

Il n’existe pas de règle stricte pour savoir quand utiliser la programmation dynamique, mais elle est adaptée aux problèmes où les sous-problèmes se recoupent.

Exemple : suite de Fibonacci

La suite de Fibonacci est définie par :

F(0) = 1, F(1) = 1, et F(n) = F(n - 1) + F(n - 2) pour n ≥ 2

Solution récursive :

public int Fibo(int n) {
  if (n <= 1)
    return 1;
  else
    return Fibo(n - 1) + Fibo(n - 2);
}

Complexité : O(2^n), car de nombreux calculs sont répétés.

Solution avec programmation dynamique (itérative) :

public int Fib(int n) {
  int[] F = new int[n + 1];
  F[0] = 1; F[1] = 1;
  for (int i = 2; i <= n; i++)
    F[i] = F[i - 1] + F[i - 2];
  return F[n];
}

Complexité : O(n), beaucoup plus efficace.

Exemple : calcul du nombre de combinaisons

Le nombre de combinaisons C(n, k) peut être calculé par la relation :

C(n, k) = {
  1 si k = 0 ou k = n ;
  C(n - 1, k - 1) + C(n - 1, k) sinon
}

Solution récursive :

int Combinaison(int n, int k) {
  if (k == 0 || k == n)
    return 1;
  else
    return Combinaison(n - 1, k - 1) + Combinaison(n - 1, k);
}

Complexité : exponentielle O(2^n), à cause des répétitions.

Solution avec programmation dynamique :

int Combinaison(int n, int k) {
  int[][] B = new int[n + 1][k + 1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= Math.min(i, k); j++) {
      if (j == 0 || j == i)
        B[i][j] = 1;
      else
        B[i][j] = B[i - 1][j - 1] + B[i - 1][j];
    }
  }
  return B[n][k];
}

Complexité : O(nk), bien plus efficace.

Une autre solution optimisée en espace :

public int Combinaison(int n, int p) {
  int[] t = new int[n + 1];
  t[0] = 1;
  for (int i = 1; i <= n; i++) {
    t[i] = 1;
    for (int j = i - 1; j >= 1; j--)
      t[j] = t[j] + t[j - 1];
  }
  return t[p];
}

Glossaire des termes clés

• Algorithme récursif : Algorithme qui s’appelle lui-même pour résoudre un problème.
• Récursivité multiple : Définition récursive comportant plusieurs appels récursifs.
• Récursivité mutuelle : Plusieurs fonctions récursives qui s’appellent mutuellement.
• Récursivité imbriquée : Appels récursifs imbriqués dans les arguments d’autres appels récursifs.
• Programmation dynamique : Méthode algorithmique qui résout les problèmes en mémorisant les solutions des sous-problèmes pour éviter les calculs redondants.
• Complexité exponentielle : Croissance du temps de calcul proportionnelle à une fonction exponentielle de la taille de l’entrée.
• Complexité linéaire : Croissance du temps de calcul proportionnelle à la taille de l’entrée.
• Relation de Pascal : Relation utilisée pour calculer les coefficients binomiaux (combinaisons).
• Indécidabilité : Propriété d’un problème pour lequel il n’existe pas d’algorithme général permettant de décider une réponse dans tous les cas.

Points clés à retenir

• Un algorithme récursif se définit par un cas de base et une ou plusieurs appels récursifs sur des sous-problèmes plus petits.
• La récursivité peut être simple, multiple, mutuelle ou imbriquée selon la nature des appels.
• Le problème de la terminaison d’un programme est indécidable en général.
• La programmation dynamique optimise les algorithmes récursifs en évitant les calculs redondants via la mémorisation.
• La programmation dynamique calcule les solutions de bas en haut, contrairement à la récursivité classique descendante.
• Exemples classiques : calcul de la puissance, suite de Fibonacci, et calcul des combinaisons.
• La complexité peut passer d’exponentielle à linéaire grâce à la programmation dynamique.