Comment fonctionne la récursion
Cas de base et pile d’appels.
Comment fonctionne la récursion est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que la récursion ?
La récursion consiste, pour une fonction, à s'appeler elle-même afin de résoudre un problème. Chaque appel traite une partie plus petite du problème initial.
En C, toute fonction peut s'appeler elle-même, à condition qu'un mécanisme permette aux appels de s'arrêter eventually.
Le cas de base
Toute fonction récursive a besoin d'un cas de base : une condition dans laquelle elle cesse de s'appeler elle-même et renvoie directement un résultat.
Sans cas de base, la fonction s'appellerait indéfiniment et ferait planter le programme.
int countdown(int n) {
if (n == 0) return 0; /* base case */
return countdown(n - 1);
}Le cas récursif
Le cas récursif est la partie où la fonction s'appelle elle-même avec un argument modifié.
Cet argument doit se rapprocher du cas de base, sinon la récursion ne se termine jamais.
int sum_to(int n) {
if (n == 0) return 0; /* base case */
return n + sum_to(n - 1); /* recursive case */
}Un premier programme complet
Exécutons un programme complet qui additionne les nombres de 1 à 5 avec la récursion.
Le résultat devrait être 15.
#include <stdio.h>
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
int main(void) {
printf("%d\n", sum_to(5));
return 0;
}Suivre les appels
Il est utile de suivre la récursion à la main. Pour sum_to(3) :
sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0
Les appels renvoient ensuite leurs résultats en remontant : 1, puis 3, puis 6.
La pile d'appels
Chaque appel de fonction reçoit son propre espace sur la pile d'appels, qui contient ses paramètres et ses variables locales.
En descendant plus profondément, les cadres s'empilent. Lorsqu'un appel renvoie son résultat, son cadre est supprimé et le contrôle revient à l'appelant.
Descente et remontée
La récursion comporte deux phases. La descente correspond au moment où les appels s'enchaînent vers le cas de base.
La remontée commence lorsque le cas de base renvoie son résultat et que chaque appel termine son travail en utilisant la valeur renvoyée.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main(void) {
printf("%d\n", factorial(4));
return 0;
}Les valeurs de retour remontent
La valeur renvoyée par un appel plus profond est utilisée par l'appel qui l'a effectué.
C'est pourquoi l'ordre est important : l'appel le plus profond se termine en premier, puis les résultats se combinent en remontant la pile.
int power(int base, int exp) {
if (exp == 0) return 1;
return base * power(base, exp - 1);
}Afficher pendant la récursion
Vous pouvez afficher une valeur avant ou après l'appel récursif. Un affichage avant l'appel montre les nombres en descendant ; un affichage après l'appel les montre en remontant.
#include <stdio.h>
void down(int n) {
if (n == 0) return;
printf("%d ", n);
down(n - 1);
}
int main(void) {
down(5);
printf("\n");
return 0;
}Afficher lors de la remontée
Déplacez le printf après l'appel récursif et l'ordre s'inverse. L'appel le plus profond affiche son résultat en premier.
Le programme affiche alors 1 2 3 4 5 au lieu de 5 4 3 2 1.
#include <stdio.h>
void up(int n) {
if (n == 0) return;
up(n - 1);
printf("%d ", n);
}
int main(void) {
up(5);
printf("\n");
return 0;
}Deux règles à retenir
Une fonction récursive correcte suit deux règles :
1. Elle possède au moins un cas de base qui renvoie un résultat sans récursion.
2. Chaque appel récursif rapproche l'argument d'un cas de base.
Si vous enfreignez l'une de ces règles, le programme boucle indéfiniment.
Vérification rapide
Testez votre compréhension des bases de la récursion.
Récapitulatif
La récursion résout un problème en s'appelant elle-même avec une valeur d'entrée plus petite. Vous avez toujours besoin d'un cas de base pour l'arrêter et d'un cas récursif qui s'en rapproche.
Chaque appel utilise un cadre de pile ; les résultats remontent lorsque les appels se terminent.
Questions Fréquemment Posées
La leçon « Comment fonctionne la récursion » est-elle gratuite ?
Oui — le texte complet de « Comment fonctionne la récursion » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Comment fonctionne la récursion » ?
Cas de base et pile d’appels. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Comment fonctionne la récursion » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Comment fonctionne la récursion
- Problèmes récursifs classiques
- Récursion ou itération
- Éviter le dépassement de pile