Récursivité en C

La récursivité est une technique selon laquelle une fonction s’appelle elle-même pour résoudre un problème.

Dans cette leçon, vous apprendrez :

• Ce qu’est la récursivité et comment elle fonctionne.
• Comment implémenter des fonctions récursives.
• La différence entre la récursivité et l’itération.

Qu’est-ce que la récursivité ?

La récursivité intervient lorsqu’une fonction s’appelle elle-même pour résoudre une partie plus petite d’un problème.

Exemple de syntaxe :

void function() { function(); // Recursive call }

Toute fonction récursive doit comporter un cas de base afin d’éviter une récursivité infinie.

Exemple : récursivité

Ce programme illustre la récursivité en affichant les nombres de 5 à 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Cas de base de la récursivité

Une fonction récursive doit comporter un cas de base pour arrêter la récursivité.

Exemple :

if (n == 0) return;

Sans cas de base, la fonction s’appellera indéfiniment, ce qui provoquera un débordement de pile.

Exemple : factorielle avec la récursivité

Ce programme calcule la factorielle d’un nombre à l’aide de la récursivité.

#include <stdio.h>

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

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Récursivité et itération

La récursivité et l’itération (les boucles) peuvent produire les mêmes résultats, mais elles fonctionnent différemment.

Différences :

• La récursivité utilise des appels de fonctions et nécessite davantage de mémoire.
• L’itération utilise des boucles et est généralement plus efficace.
• La récursivité simplifie le code pour des problèmes tels que le parcours d’un arbre.

Exemple : suite de Fibonacci (récursive)

Ce programme calcule la suite de Fibonacci à l’aide de la récursion.

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Quand utiliser la récursion ?

La récursion est utile pour les problèmes qui impliquent :

• Le parcours d’arbres.
• Le retour sur trace (par exemple, pour résoudre des labyrinthes).
• Des problèmes mathématiques comme la factorielle et la suite de Fibonacci.

Récapitulatif

Dans cette leçon, vous avez appris :

• Ce qu’est la récursion et comment elle fonctionne.
• L’importance d’un cas de base.
• La différence entre la récursion et l’itération.

Vous découvrirez ensuite les tableaux et les chaînes de caractères en C !