Les Fonctions Récursives en C

Une fonction récursive est une fonction qui s’appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus petits. C’est une technique courante en programmation, souvent utilisée pour des problèmes tels que les algorithmes de recherche, le calcul de factorielle, le tri, ou les arbres binaires.

Principe de la récursivité

L’idée principale de la récursivité est de diviser un problème complexe en plusieurs sous-problèmes plus simples. Une fonction récursive doit avoir deux parties :

Cas de base (ou condition d’arrêt) : Il s’agit d’une condition qui permet de mettre fin à l’exécution de la récursion, en retournant une valeur simple sans effectuer d’appel récursif.
Appel récursif : C’est l’étape où la fonction s’appelle elle-même avec des paramètres modifiés, pour avancer vers la solution finale.

Structure générale d’une fonction récursive

Voici la structure d’une fonction récursive typique en C :

type fonction_recursive(paramètres) {
    if (condition d'arrêt) {
        // Cas de base
        return valeur;
    } else {
        // Appel récursif
        return fonction_recursive(paramètres modifiés);
    }
}

Exemple simple : Calcul de la factorielle

La factorielle d’un nombre entier n (notée n!) est définie comme le produit de tous les entiers de 1 à n. Par exemple, 5! = 5 * 4 * 3 * 2 * 1 = 120. La factorielle peut être calculée de manière récursive, car :

Cas de base : 0! = 1
Appel récursif : n! = n * (n - 1)!

Code en C :

#include <stdio.h>

// Fonction récursive pour calculer la factorielle
int factorielle(int n) {
    if (n == 0) {
        return 1;  // Cas de base : 0! = 1
    } else {
        return n * factorielle(n - 1);  // Appel récursif
    }
}

int main() {
    int nombre = 5;
    printf("La factorielle de %d est %d\n", nombre, factorielle(nombre));
    return 0;
}

Explication :

Cas de base : Lorsque n == 0, la fonction retourne 1 (ce qui termine la récursion).
Appel récursif : Si n > 0, la fonction s’appelle elle-même avec n - 1, et la multiplication continue jusqu’à atteindre le cas de base.

Fonctionnement étape par étape pour `factorielle(3)` :

factorielle(3) appelle factorielle(2)
factorielle(2) appelle factorielle(1)
factorielle(1) appelle factorielle(0) (cas de base)
factorielle(0) retourne 1
factorielle(1) retourne 1 * 1 = 1
factorielle(2) retourne 2 * 1 = 2
factorielle(3) retourne 3 * 2 = 6

Avantages et inconvénients de la récursivité

Avantages :

Simplicité : Les fonctions récursives peuvent rendre un algorithme plus facile à comprendre et plus concis, en particulier pour des problèmes qui ont une structure récursive naturelle (comme les arbres binaires ou le calcul de factorielle).
Approche élégante : La récursion est élégante pour des problèmes qui peuvent être naturellement décomposés en sous-problèmes similaires.

Inconvénients :

Efficacité : Les appels récursifs nécessitent un espace supplémentaire pour chaque appel sur la pile (stack), ce qui peut causer une surcharge mémoire ou une erreur de dépassement de pile (stack overflow) si le nombre d’appels récursifs est trop élevé.
Performance : La récursion peut parfois être moins efficace que les boucles pour certains problèmes, en raison du coût des appels de fonction et des retours successifs.

Autres Exemples de Fonctions Récursives

Exemple 1 : Somme des éléments d’un tableau

Écrivez une fonction récursive pour calculer la somme des éléments d’un tableau.

Code en C :

#include <stdio.h>

int somme(int tableau[], int taille) {
    if (taille == 0) {
        return 0;  // Cas de base : un tableau vide a une somme de 0
    } else {
        return tableau[taille - 1] + somme(tableau, taille - 1);  // Appel récursif
    }
}

int main() {
    int tableau[] = {1, 2, 3, 4, 5};
    int taille = sizeof(tableau) / sizeof(tableau[0]);

    printf("La somme des éléments du tableau est : %d\n", somme(tableau, taille));
    return 0;
}

Explication :

Cas de base : Si la taille du tableau est 0, la somme est 0.
Appel récursif : Ajoute le dernier élément du tableau à la somme des éléments précédents.

Exemple 2 : Série de Fibonacci

La série de Fibonacci est définie de la manière suivante :

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

Code en C :

#include <stdio.h>

// Fonction récursive pour calculer le n-ième terme de Fibonacci
int fibonacci(int n) {
    if (n == 0) {
        return 0;  // Cas de base : F(0) = 0
    } else if (n == 1) {
        return 1;  // Cas de base : F(1) = 1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);  // Appel récursif
    }
}

int main() {
    int n = 5;
    printf("Le %d-ième terme de Fibonacci est %d\n", n, fibonacci(n));
    return 0;
}

Explication :

Cas de base : Si n est 0 ou 1, la fonction retourne respectivement 0 ou 1.
Appel récursif : Si n ≥ 2, la fonction retourne la somme des deux termes précédents (fibonacci(n-1) et fibonacci(n-2)).

Fonctionnement étape par étape pour `fibonacci(3)` :

fibonacci(3) appelle fibonacci(2) et fibonacci(1)
fibonacci(2) appelle fibonacci(1) et fibonacci(0)
fibonacci(1) retourne 1 et fibonacci(0) retourne 0
fibonacci(2) retourne 1 + 0 = 1
fibonacci(3) retourne 1 + 1 = 2

Exemple 3 : Recherche binaire

La recherche binaire est un algorithme efficace pour trouver un élément dans un tableau trié. L’algorithme divise le tableau en deux parties à chaque étape et compare l’élément du milieu avec l’élément recherché.

Code en C :

#include <stdio.h>

// Fonction récursive pour la recherche binaire
int recherche_binaire(int tableau[], int gauche, int droite, int cible) {
    if (gauche > droite) {
        return -1;  // Cas de base : l'élément n'est pas trouvé
    }

    int milieu = gauche + (droite - gauche) / 2;  // Calculer l'indice du milieu

    if (tableau[milieu] == cible) {
        return milieu;  // L'élément est trouvé
    } else if (tableau[milieu] > cible) {
        return recherche_binaire(tableau, gauche, milieu - 1, cible);  // Recherche dans la partie gauche
    } else {
        return recherche_binaire(tableau, milieu + 1, droite, cible);  // Recherche dans la partie droite
    }
}

int main() {
    int tableau[] = {1, 3, 5, 7, 9, 11};
    int taille = sizeof(tableau) / sizeof(tableau[0]);
    int cible = 7;

    int resultat = recherche_binaire(tableau, 0, taille - 1, cible);

    if (resultat != -1) {
        printf("Élément trouvé à l'indice %d\n", resultat);
    } else {
        printf("Élément non trouvé\n");
    }

    return 0;
}

Explication :

Cas de base : Si gauche dépasse droite, l’élément n’est pas dans le tableau.

Appel récursif : La recherche est divisée en deux parties. Si l’élément cible est plus petit que l’élément au milieu du tableau, on appelle récursivement la fonction pour la partie gauche du tableau (recherche_binaire(tableau, gauche, milieu - 1, cible)). Sinon, on effectue l’appel récursif sur la partie droite du tableau (recherche_binaire(tableau, milieu + 1, droite, cible)).

Ce programme permet de rechercher efficacement un élément dans un tableau trié, en divisant l’espace de recherche à chaque étape.

Avantages et Inconvénients de la Récursion

Avantages :

Simplicité et élégance : Les fonctions récursives peuvent rendre certains algorithmes plus simples à comprendre et à implémenter, surtout lorsque le problème peut être naturellement décomposé en sous-problèmes similaires.
Réutilisation : La récursion permet de réutiliser la même fonction pour résoudre un problème plus petit, sans avoir à réécrire du code pour chaque cas.

Inconvénients :

Consommation de mémoire : Chaque appel récursif consomme de l’espace dans la pile d’exécution (stack). Si la récursion est profonde (beaucoup d’appels imbriqués), cela peut entraîner un dépassement de pile (stack overflow).
Performances : La récursion peut être inefficace pour des problèmes qui nécessitent beaucoup d’appels récursifs, car chaque appel nécessite un surcoût en mémoire et en temps de calcul.
Risque de boucles infinies : Si le cas de base n’est pas correctement défini ou si l’appel récursif ne progresse pas vers la condition d’arrêt, la fonction peut tomber dans une récursion infinie, bloquant le programme.

Comparaison entre récursion et itération

Récursion :

Convient bien pour des problèmes divisibles de manière récursive, comme les arbres, les graphes, les suites mathématiques (ex. : factorielle, Fibonacci).
Elle peut parfois être plus simple et élégante que l’itération, mais au prix de performances réduites (en raison des appels de fonction).

Itération :

Les boucles itératives (for, while) sont souvent plus efficaces en termes de mémoire et de temps d’exécution, car elles n’utilisent pas la pile d’appel.
Moins de risque de débordement de pile avec l’itération.
Les algorithmes itératifs sont souvent plus rapides pour les problèmes simples.

Exemple : Le calcul de la factorielle peut être fait de manière itérative ou récursive.

Itératif :

#include <stdio.h>

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

int main() {
    int n = 5;
    printf("La factorielle de %d est %d\n", n, factorielle_iterative(n));
    return 0;
}

Récursif :

#include <stdio.h>

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

int main() {
    int n = 5;
    printf("La factorielle de %d est %d\n", n, factorielle_recursive(n));
    return 0;
}

Différences :

L’approche itérative utilise une boucle for pour calculer la factorielle, tandis que l’approche récursive divise le problème en sous-problèmes plus petits jusqu’à atteindre le cas de base.
L’itération est généralement plus efficace en termes de mémoire.

Les fonctions récursives sont un outil puissant dans la boîte à outils d’un programmeur. Elles sont particulièrement utiles pour résoudre des problèmes où la solution peut être formulée en termes de sous-problèmes plus petits, comme le tri (quicksort, mergesort), la gestion des structures arborescentes (arbres binaires), ou la recherche dans des algorithmes divisant pour régner (recherche binaire).

Cependant, la récursion doit être utilisée avec soin. Il est essentiel de bien définir le cas de base pour éviter les appels récursifs infinis, et de comprendre les implications en termes de performances et de mémoire. Dans certains cas, une solution itérative peut être plus adaptée, en particulier lorsque la récursion pourrait entraîner un dépassement de pile.

En résumé, la récursion est une technique élégante et puissante pour résoudre certains problèmes, mais elle doit être appliquée de manière judicieuse et en tenant compte de ses limitations.