Récursion – Structures de Données Avancées

Objectifs

À la fin de ce chapitre, vous serez capables de :

Comprendre le concept de récursion et son fonctionnement
Écrire des fonctions récursives pour résoudre des problèmes courants
Faire la différence entre récursion et itération, et choisir la bonne approche selon le contexte

1 Rappels sur les fonctions

Une fonction est une suite d’instructions nommée qui permet de réaliser une tâche spécifique. En programmation, les fonctions sont utilisées pour structurer le code, le rendre réutilisable et plus facile à comprendre.

En particulier en C, une fonction est définie par son type de retour, son nom, et une liste de paramètres. Voici un exemple simple d’une fonction en C qui détermine et retourne le maximum de deux entiers :

int max2(int a, int b) {
    if (a < b) {
        return b;
    }
    return a;
}

Considérons maintenant une fonction max3 qui retourne le maximum de trois entiers. Étant donné la fonction max2 définie précédemment, on peut implémenter max3 en utilisant max2 comme suit :

int max3(int a, int b, int c) {
    return max2(max2(a, b), c);
}

En effet, pour un appel de return max3(2, 5, 3), la ligne d’instruction max2(max2(2, 5), 3) évaluera d’abord max2(2, 5), qui retourne 5, puis évalue max2(5, 3), qui retourne 5 également. Ainsi, max3(2, 5, 3) retourne bien 5.

On remarque alors qu’une fonction peut appeler une autre fonction pour accomplir sa tâche.

2 Réduction de problème

Toujours avec les exemples précédents, on fait l’observation suivante : à partir du moment où max2 retourne correctement le maximum de deux entiers, la définition proposée pour max3 est correcte. On parle alors de réduction de problème : pour résoudre un problème plus complexe (trouver le maximum de trois entiers), on le réduit à un problème plus simple (trouver le maximum de deux entiers).

En d’autres termes, si un problème Y se réduit à un problème X, et si on sait résoudre X, on peut en déduire une solution pour Y.

Exemple

Considérons la fonction selection_sort qui trie un tableau d’entiers en utilisant l’algorithme du tri par sélection. Pour rappel, cet algorithme fonctionne en trouvant l’élément minimum dans le tableau non trié, en l’échangeant avec le premier élément non trié, puis en répétant ce processus pour le reste du tableau.

void selection_sort(int * arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        int min_index = find_min_index(arr + i, size - i);
        swap(&arr[i], &arr[min_index + i]);
    }
}

Il n’est pas nécessaire de comprendre comment find_min_index et swap sont implémentées pour comprendre que selection_sort trie correctement le tableau si ces deux fonctions sont correctes.
Le problème de trier un tableau est réduit au problème de trouver le minimum dans une sous-partie du tableau et au problème d’échanger deux éléments.

3 Principe de la récursion

La récursion est une forme particulière de réduction de problème où une fonction s’appelle elle-même pour résoudre une version plus simple du même problème. Pour faire simple, une fonction est dite récursive si elle s’appelle elle-même : c’est-à-dire, que dans sa définition, elle contient un appel à elle-même.

Problems with recursion (smbc-comics.com)

Important

Afin d’écrire une fonction récursive, il faut absolument considérer les deux éléments suivants :

Le cas de base : il s’agit d’une condition qui permet d’arrêter la récursion. C’est une situation simple où la fonction peut retourner une valeur sans s’appeler elle-même.
L’appel récursif : c’est l’endroit où la fonction s’appelle elle-même avec des arguments modifiés, généralement plus simples ou plus proches du cas de base.

3.1 Premier exemple : Factorielle

La factorielle d’un entier naturel \(n\), notée \(n!\), est définie comme le produit de tous les entiers naturels de \(1\) à \(n\). C’est le produit : \[ n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1 \]

Et par convention, on définit \(0! = 1\). On remarque que le produit \((n - 1) \times (n - 2) \times ... \times 2 \times 1\) est en fait la factorielle de \((n - 1)\), c’est-à-dire \((n - 1)!\).

On peut donc réécrire la définition de la factorielle de la manière suivante : \[ n! = \begin{cases} 1 & \text{si } n = 0 \\ n \times (n - 1)! & \text{sinon} \end{cases} \] Cette définition est récursive car elle exprime la factorielle de \(n\) en termes de la factorielle de \((n - 1)\).

Le cas de base est lorsque \(n = 0\), où la fonction retourne simplement \(1\).
Pour tout autre entier naturel \(n\), la fonction s’appelle elle-même avec l’argument \((n - 1)\).

La fonction récursive en C pour calculer la factorielle d’un entier naturel peut être implémentée comme suit :

int factorial(int n) {
    if (n == 0) {
        return 1; // Cas de base
    } else {
        return n * factorial(n - 1); // Appel récursif
    }
}

Mais pourquoi ça marche ?

Si on peut se convaincre que la fonction factorial(n - 1) retourne correctement la factorielle de \((n - 1)\), alors on peut en déduire que n * factorial(n - 1) retourne correctement la factorielle de \(n\).

Plus formellement, tentons de voir si la fonction factorial(4) retourne bien \(4! = 24\) :

factorial(4) retourne 4 * factorial(3), puisque \(4 \neq 0\). (on appelle factorial(3))
- factorial(3) retourne 3 * factorial(2), puisque \(3 \neq 0\). (on appelle factorial(2))
  - factorial(2) retourne 2 * factorial(1), puisque \(2 \neq 0\). (on appelle factorial(1))
    - factorial(1) retourne 1 * factorial(0), puisque \(1 \neq 0\). (on appelle factorial(0))
      - factorial(0) retourne 1, puisque \(0 = 0\).
    - factorial(1) retourne alors 1 * 1 = 1.
  - factorial(2) retourne alors 2 * 1 = 2.
- factorial(3) retourne alors 3 * 2 = 6.
factorial(4) retourne alors 4 * 6 = 24.

Ainsi, factorial(4) retourne bien \(24\), ce qui est correct.

Il est facile d’observer que \(n! = n \times (n - 1)!\) pour tout entier naturel \(n > 0\). Notre fonction factorial reflète exactement cette définition récursive.

3.2 Deuxième exemple : Somme d’un tableau

Considérons un tableau d’entiers arr de taille n. On souhaite écrire une fonction récursive sum_array qui calcule la somme des éléments de ce tableau. Dans un premier temps, il va falloir définir le problème de manière récursive.

Question ?

Pour quelle valeur de n la somme des éléments du tableau peut-elle être calculée directement ?

La somme des éléments d’un tableau peut être calculée directement lorsque la taille du tableau n est égale à 0. Dans ce cas, la somme est simplement 0, car il n’y a pas d’éléments à additionner. C’est notre cas de base.

Pour tout autre taille n > 0, on peut alors calculer la somme comme étant la somme du premier élément du tableau arr[0] et de la somme des éléments restants du tableau arr[1] à arr[n-1]. C’est notre appel récursif. On a donc la définition récursive suivante :

\[ \text{sum\_array}(arr, n) = \begin{cases} 0 & \text{si } n = 0 \\ arr[0] + \text{sum\_array}(arr + 1, n - 1) & \text{sinon} \end{cases} \]

La fonction récursive en C pour calculer la somme des éléments d’un tableau peut être implémentée comme suit :

int sum_array(int * arr, int n) {
    if (n == 0) {
        return 0;
    } else {
        return arr[0] + sum_array(arr + 1, n - 1); 
        // arr + 1 correspond au sous tableau qui commence
        //  à arr[1] et fait de taille n - 1
    }
}

Mais pourquoi ça marche ?

Essayons de voir si la fonction sum_array retourne bien la somme des éléments du tableau {2, 4, 6}, c’est-à-dire 12 :

sum_array({2, 4, 6}, 3) retourne 2 + sum_array({4, 6}, 2).
- sum_array({4, 6}, 2) retourne 4 + sum_array({6}, 1).
  - sum_array({6}, 1) retourne 6 + sum_array({}, 0).
    - sum_array({}, 0) retourne 0, puisque n = 0.
  - sum_array({6}, 1) retourne alors 6 + 0 = 6.
- sum_array({4, 6}, 2) retourne alors 4 + 6 = 10.
sum_array({2, 4, 6}, 3) retourne alors 2 + 10 = 12.

Ainsi, sum_array({2, 4, 6}, 3) retourne bien 12, ce qui est correct.

Le cas n == 1 peut également être utilisé comme cas de base. Qu’aurait-on retourné dans ce cas ?

4 Récursion vs Itération

On aurait totalement pu écrire les fonctions factorial et sum_array sans utiliser la récursion. On aurait utilisé des boucles à la place. Cette approche est appelée itération ou méthode itérative. Ce constat nous amène à nous poser la question suivante :

Question ?

Si un même problème peut être résolu à la fois de manière récursive et itérative, quels sont les avantages et les inconvénients de chaque approche ?

Pour répondre à cette question, il est nécessaire de comprendre ce qu’il se passe sous le capot (en mémoire) lors de l’appel d’une fonction récursive.

Chaque fois qu’une fonction est appelée, que ce soit de manière récursive ou non, une partie de la mémoire appelée pile d’appels (call stack) est utilisée pour stocker des informations sur l’état actuel de l’exécution de la fonction. Cela inclut les paramètres de la fonction, les variables locales et l’adresse de retour (l’endroit où le programme doit reprendre après l’exécution de la fonction).

Dans le cas de la récursion, chaque appel de fonction crée une nouvelle entrée dans la pile d’appels, ce qui peut entraîner une consommation de mémoire importante si la profondeur de récursion est élevée. En revanche, l’itération utilise une seule entrée dans la pile d’appels, ce qui la rend généralement plus efficace en termes de mémoire.

Résumé

La récursion est souvent plus élégante et plus facile à comprendre, mais elle peut être moins efficace en termes de mémoire et de performances par rapport à l’itération.
Certains problèmes sont naturellement récursifs et difficiles à résoudre de manière itérative, comme les structures de données arborescentes (arbres, graphes). Le choix entre récursion et itération dépend souvent du contexte, des contraintes de performance et de la lisibilité du code.

Il existe des techniques pour optimiser la récursion, comme la récursion terminale (tail recursion), qui permet de réduire l’utilisation de la pile d’appels dans certains langages de programmation.

4.1 Exemple de conversion : récursion → itération

Pour mieux comprendre la différence entre récursion et itération, comparons les deux approches pour le calcul de la factorielle.

Version récursive (vue précédemment) :

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

Version itérative :

int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

Note

Comparaison des deux approches :

Récursive : Plus proche de la définition mathématique, élégante, mais utilise plus d’appels de fonction (mémoire supplémentaire).
Itérative : Plus efficace en mémoire, utilise une simple boucle, mais peut être moins intuitive pour certains problèmes.

Pour factorial(5) :

Version récursive : 5 appels de fonction empilés en mémoire
Version itérative : 1 seul niveau de fonction, une variable result mise à jour

Pour avoir un aperçu visuel, allez ici pour visualiser l’exécution des deux versions.

De même, voici la version itérative de sum_array :

int sum_array_iterative(int * arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

5 Récursion multiple : Suite de Fibonacci

Jusqu’à présent, nous avons vu des exemples où une fonction récursive ne s’appelle elle-même qu’une seule fois. Il existe des cas où une fonction s’appelle plusieurs fois de manière récursive. C’est ce qu’on appelle la récursion multiple.

Un exemple classique est la suite de Fibonacci, définie comme suit : \[ F(n) = \begin{cases} 0 & \text{si } n = 0 \\ 1 & \text{si } n = 1 \\ F(n-1) + F(n-2) & \text{si } n \geq 2 \end{cases} \]

Cette suite commence par \(0, 1, 1, 2, 3, 5, 8, 13, 21, ...\)

La fonction récursive en C pour calculer le n-ième terme de Fibonacci est :

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Observation

Pour calculer fibonacci(4), la fonction effectue les appels suivants :

---
config:
    look: 'handDrawn'
---
graph TD
    F4["fibonacci(4)"]
    F3_1["fibonacci(3)"]
    F2_1["fibonacci(2)"]
    F2_2["fibonacci(2)"]
    F1_1["fibonacci(1) → 1"]
    F1_2["fibonacci(1) → 1"]
    F1_3["fibonacci(1) → 1"]
    F0_1["fibonacci(0) → 0"]
    F0_2["fibonacci(0) → 0"]
    
    F4 --> F3_1
    F4 --> F2_2
    
    F3_1 --> F2_1
    F3_1 --> F1_2
    
    F2_1 --> F1_1
    F2_1 --> F0_1
    
    F2_2 --> F1_3
    F2_2 --> F0_2
    
    style F1_1 fill:#90EE90
    style F1_2 fill:#90EE90
    style F1_3 fill:#90EE90
    style F0_1 fill:#ADD8E6
    style F0_2 fill:#ADD8E6

Remarquez que fibonacci(2), fibonacci(1) et fibonacci(0) sont calculés plusieurs fois ! Cela rend cette implémentation très inefficace.

Important

La récursion multiple peut entraîner une complexité exponentielle. Pour Fibonacci, le nombre d’appels croît exponentiellement avec \(n\), rendant le calcul extrêmement lent pour des valeurs élevées de \(n\) (même à 30 ou 40).

Il existe des techniques d’optimisation comme la mémoïsation (sauvegarder les résultats déjà calculés) ou l’utilisation d’une approche itérative pour résoudre ce problème.

6 Pièges courants et débogage

Lorsqu’on débute avec la récursion, certaines erreurs sont fréquentes. Voici les principaux pièges à éviter.

6.1 Oublier le cas de base

L’erreur la plus courante est d’oublier le cas de base ou d’avoir une condition d’arrêt incorrecte.

Important

Sans cas de base, la récursion ne s’arrête jamais !

// ❌ INCORRECT - Pas de cas de base
int factorial_wrong(int n) {
    return n * factorial_wrong(n - 1);  // Ne s'arrête jamais !
}

// ❌ INCORRECT - Cas de base inaccessible
int factorial_wrong2(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial_wrong2(n - 2);  // Si n est impair, n'atteint jamais 0
}

6.2 Stack overflow (Dépassement de pile)

Lorsqu’une récursion est trop profonde ou infinie, elle provoque un dépassement de la pile d’appels (stack overflow). Chaque appel de fonction consomme de la mémoire dans la pile, et si cette pile est pleine, le programme plante.

// Ce code va provoquer un stack overflow
int main() {
    int result = factorial_wrong(10);  // Récursion infinie !
    return 0;
}

Note

Symptômes d’un stack overflow :

Message d’erreur du type : “Segmentation fault” ou “Stack overflow”
Programme qui plante après un certain temps
Parfois, le programme semble “figé” pendant l’exécution

Comment éviter :

Toujours vérifier que le cas de base est correct et atteignable
Pour de grandes valeurs de \(n\), privilégier l’itération si possible
Tester avec de petites valeurs d’abord

6.3 Modification incorrecte des paramètres

Il faut s’assurer que les paramètres de l’appel récursif progressent vers le cas de base.

// ❌ INCORRECT - n ne diminue jamais
int count_down_wrong(int n) {
    if (n == 0) {
        return 0;
    }
    return 1 + count_down_wrong(n);  // Devrait être count_down_wrong(n - 1)
}

// ✅ CORRECT
int count_down(int n) {
    if (n == 0) {
        return 0;
    }
    return 1 + count_down(n - 1);
}

6.4 Conseils pour déboguer une fonction récursive

Tip

Stratégies de débogage :

Tester avec des petites valeurs : Commencez par tester avec n = 0, n = 1, n = 2 pour vérifier le comportement.

Ajouter des affichages : Insérez des printf pour visualiser les appels :

int factorial_debug(int n) {
    printf("Appel de factorial(%d)\n", n);
    if (n == 0) {
        printf("Cas de base atteint, retour 1\n");
        return 1;
    }
    int result = n * factorial_debug(n - 1);
    printf("factorial(%d) retourne %d\n", n, result);
    return result;
}

Vérifier les cas limites : Que se passe-t-il avec des valeurs négatives ? Avec 0 ? Avec de très grandes valeurs ?
Tracer sur papier : Pour de petites valeurs, dessinez l’arbre des appels récursifs comme nous l’avons fait pour fibonacci(5).