Leçon 25 : Bases de la récursivité

La récursivité est le processus par lequel une fonction s'appelle elle-même, directement ou indirectement.

Les trois règles de la récursivité

1. Cas de base : Il doit y avoir une condition qui arrête la récursion. Sans cela, la fonction s'appellerait indéfiniment (entraînant un dépassement de pile ou stack overflow).
2. Étape récursive : La fonction doit s'appeler elle-même.
3. Progression : L'appel récursif doit se rapprocher du cas de base (ex: réduction de la taille de l'entrée).

Exemple : Calcul de la factorielle

La factorielle de $N$ ($N!$) est le produit de tous les entiers positifs inférieurs ou égaux à $N$. ($5! = 5 \times 4 \times 3 \times 2 \times 1$).

Cas de base : $0! = 1$. Étape récursive : $N! = N \times (N-1)!$

c #include <stdio.h>

long int factorielle(int n) { // 1. Cas de base : Arrête la récursion if (n == 0 || n == 1) { return 1; } // 2. Étape récursive (se rapprochant du cas de base) return n * factorielle(n - 1); }

int main() { printf("La factorielle de 5 est %ld\n", factorielle(5)); // Résultat : 120 return 0; }

Avantages et inconvénients de la récursivité

• Avantages : Solutions élégantes et concises pour les problèmes naturellement définis de manière récursive (comme le parcours d'arbres ou certaines séquences mathématiques).
• Inconvénients : Consommation de mémoire et de temps plus élevée par rapport aux solutions itératives en raison de la gestion de la pile d'appels de fonctions.