Récursion en C

XTI102 - Structures de Données Avancées

Rado Rakotonarivo – EFREI Paris

Objectifs du cours

  • 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
  • Choisir la bonne approche selon le contexte

Rappels : Fonctions en C

Définition d’une fonction

Une fonction est une suite d’instructions nommée pour accomplir une tâche spécifique.

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

Les fonctions permettent de :

  • Structurer le code
  • Réutiliser du code
  • Faciliter la compréhension

Une fonction peut en appeler une autre

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

Pour max3(2, 5, 3) :

  1. max2(2, 5) → 5
  2. max2(5, 3) → 5
  3. Résultat final : 5 ✓

Réduction de problème

Principe

Note

Réduction de problème : résoudre un problème complexe en le ramenant à un problème plus simple.

Si le problème Y se réduit au problème X, et qu’on sait résoudre X, alors on peut résoudre Y.

Exemple : Tri par sélection

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]);
    }
}

Le problème “trier un tableau” est réduit à :

  • Trouver le minimum → find_min_index()
  • Échanger deux éléments → swap()

La Récursion

Définition

Important

Une fonction est récursive si elle s’appelle elle-même dans sa propre définition.

Les deux éléments essentiels

Pour écrire une fonction récursive :

1. Cas de base

Condition d’arrêt qui permet de stopper la récursion

2. Appel récursif

La fonction s’appelle avec des arguments simplifiés

Exemple 1 : Factorielle

Définition mathématique

La factorielle de \(n\) :

\[ n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1 \]

Par convention : \(0! = 1\)

On peut réécrire :

\[ n! = \begin{cases} 1 & \text{si } n = 0 \\ n \times (n - 1)! & \text{sinon} \end{cases} \]

Implémentation en C

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

Trace d’exécution : factorial(4)

factorial(4) → 4 * factorial(3)

factorial(3) → 3 * factorial(2)

factorial(2) → 2 * factorial(1)

factorial(1) → 1 * factorial(0)

factorial(0) → 1 ✓ Cas de base atteint

Remontée : 1 → 1 → 2 → 6 → 24 ✓

Exemple 2 : Somme d’un tableau

Définition récursive

Pour un tableau arr de taille n :

\[ \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} \]

  • Cas de base : tableau vide → somme = 0
  • Réduction : premier élément + somme du reste

Implémentation

int sum_array(int * arr, int n) {
    if (n == 0) {
        return 0;  // Cas de base
    } else {
        return arr[0] + sum_array(arr + 1, n - 1);
        // arr + 1 : sous-tableau à partir de arr[1]
    }
}

Exemple : sum_array({2, 4, 6}, 3)

sum_array({2, 4, 6}, 3) → 2 + sum_array({4, 6}, 2)

sum_array({4, 6}, 2) → 4 + sum_array({6}, 1)

sum_array({6}, 1) → 6 + sum_array({}, 0)

sum_array({}, 0) → 0 ✓

Remontée : 6 → 10 → 12 ✓

Récursion vs Itération

Les deux approches

Récursive

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

Itérative

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

Pile d’appels (Call Stack)

Chaque appel de fonction crée une entrée dans la pile :

  • Paramètres
  • Variables locales
  • Adresse de retour

Warning

Récursion : une entrée par appel → consommation mémoire importante

Itération : une seule entrée → plus efficace en mémoire

Comparaison

Critère Récursion Itération
Élégance ✓ Plus proche de la définition mathématique Peut être moins intuitive
Lisibilité ✓ Plus facile à comprendre Dépend du contexte
Mémoire ✗ Utilise la pile d’appels ✓ Plus efficace
Performance ✗ Plus lente (appels) ✓ Plus rapide
Cas d’usage Structures arborescentes Boucles simples

Tip

Le choix dépend du contexte, des contraintes de performance et de la lisibilité du code.

Récursion multiple

Suite de Fibonacci

Définition :

\[ 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} \]

Suite : 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Implémentation

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

Note

La fonction s’appelle deux fois elle-même → récursion multiple

Arbre des appels : fibonacci(4)

---
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

Warning

fibonacci(2), fibonacci(1) et fibonacci(0) sont calculés plusieurs fois !

Problème de complexité

Important

Complexité exponentielle : le nombre d’appels croît exponentiellement avec \(n\)

Pour \(n = 40\) → des milliards d’appels !

Solutions :

  • Mémoïsation (sauvegarder les résultats)
  • Approche itérative
  • Programmation dynamique

Pièges courants

1. Oublier le cas de base

// ❌ INCORRECT - Récursion infinie !
int factorial_wrong(int n) {
    return n * factorial_wrong(n - 1);
}

Important

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

2. Cas de base inaccessible

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

3. Stack Overflow

Dépassement de la pile d’appels quand :

  • Récursion trop profonde
  • Récursion infinie

Symptômes :

  • “Segmentation fault”
  • Programme qui plante
  • Programme “figé”

Conseils de débogage

  1. Tester avec de petites valeurs : n = 0, 1, 2
  2. Ajouter des printf pour visualiser les appels
  3. Vérifier les cas limites : négatifs, 0, grandes valeurs
  4. Tracer sur papier l’arbre des appels

Résumé

Points clés

  • La récursion est une fonction qui s’appelle elle-même
  • Toujours définir un cas de base clair
  • L’appel récursif doit progresser vers le cas de base
  • Plus élégante mais consomme plus de mémoire
  • Privilégier l’itération pour les performances
  • Attention à la récursion multiple (complexité)

Quand utiliser la récursion ?

Tip

Utilisez la récursion quand :

  • Le problème est naturellement récursif (arbres, graphes)
  • La solution récursive est plus claire et lisible
  • La profondeur de récursion reste raisonnable

Évitez la récursion quand :

  • Performance critique
  • Grandes profondeurs de récursion
  • Solution itérative simple existe

Questions ?

Merci pour votre attention !