Récursion
La récursion est une technique de programmation dans laquelle une fonction s'appelle elle-même directement ou indirectement lors de sa définition ou de son exécution. L'idée centrale est de décomposer un problème complexe en sous-problèmes plus petits de même structure.
Concepts de base de la récursion
fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6
Boîte orange (condition de base) → arrêter la récursion et commencer à retourner | Les cadres de pile sont dépilés dans l'ordre LIFO : le dernier empilé est le premier à retourner
Une fonction récursive valide doit contenir deux éléments clés :
| Élément | Signification | Exemple (Factorielle) |
|---|---|---|
| Condition de base | La condition qui met fin à la récursion, empêchant une récursion infinie. | if (n == 0) return 1; |
| Condition récursive | Décomposer le problème en sous-problèmes plus petits et s'appeler elle-même. | return n * factorial(n-1); |
Problèmes classiques de récursion
Factorielle
Exemple
/* Implémentation récursive de la factorielle
n! = n × (n-1)!, condition de base : 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* Condition de base */
return n * factorial(n - 1); /* Condition récursive */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* Sortie : 120 */
return 0;
}
Suite de Fibonacci
Exemple
/* Récursion naïve : beaucoup de calculs répétés, O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* Condition de base */
return fib(n-1) + fib(n-2); /* Condition récursive */
}
/* Optimisation par mémoïsation : mise en cache des résultats calculés, O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* Déjà calculé, retourner directement */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (naïf) : %d\n", fib(10)); /* Sortie : 55 */
printf("fibMemo(50) (mémoïsé) : %lld\n", fibMemo(50)); /* Sortie : 12586269025 */
return 0;
}
Problème des tours de Hanoï
Exemple
/* Solution récursive des tours de Hanoï
Déplacer n disques de src vers dst à l'aide d'aux
Étapes : déplacer n-1 de src→aux, le plus grand de src→dst, n-1 d'aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("Déplacer le disque 1 de %c vers %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* Déplacer n-1 disques de src à aux */
printf("Déplacer le disque %d de %c à %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* Déplacer n-1 disques de aux à dst */
}
int main() {
printf("Tour de Hanoï (3 disques) :\n");
hanoi(3, 'A', 'B', 'C');
/* Sortie : 7 étapes au total (2³-1), nombre minimum d'étapes = 2ⁿ-1 */
return 0;
}
Récursion vs Itération
| Dimension | Récursion | Itération |
|---|---|---|
| Lisibilité du code | Élevée(Proche de la définition mathématique) | Parfois moins intuitif que la récursion |
| Efficacité d'exécution | Plus faible(Surcharge de trame de pile) | Plus élevé |
| Surcoût d'espace | Espace de pile O(profondeur de récursion) | O(1) |
| Risque de dépassement de pile | Oui(Lorsque la profondeur est trop grande) | Aucune |
| Structures applicables | Structures récursives naturelles comme les arbres et les graphes | Structures linéaires telles que les tableaux |
Autres extensionsRécursion terminaleIl s'agit d'une forme spéciale de récursion dans laquelle l'appel récursif est la dernière opération exécutée dans le corps de la fonction. Certains compilateurs peuvent optimiser la récursion terminale en la convertissant en itération équivalente afin d'économiser l'espace de pile. Cependant, tous les compilateurs C n'activent pas cette optimisation par défaut.