Docs C exécutables : récursion

Q: Qu'est-ce que la récursion en C ?

Une fonction qui s'appelle elle-même pour résoudre une version plus petite du même problème. Toute fonction récursive a besoin de deux choses : un cas de base qui retourne sans récursion, et un cas récursif qui s'en rapproche de façon mesurable. Sans le cas de base, les appels ne s'arrêtent jamais et le programme plante avec un débordement de pile.

Q: Comment écrit-on une fonction factorielle en C ?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Le cas de base traite 0 et 1, et chaque appel récursif réduit n de un jusqu'à l'atteindre. Notez qu'un int déborde à 13! - utilisez unsigned long long pour de plus grandes valeurs.

Q: Pourquoi le Fibonacci récursif est-il si lent en C ?

Parce que fib(n) appelle fib(n-1) et fib(n-2), qui recalculent encore et encore les mêmes sous-problèmes - le nombre d'appels croît exponentiellement, donc fib(50) prendrait des années. Le réécrire en boucle qui garde les deux dernières valeurs le rend linéaire et instantané.

Q: Qu'est-ce qui cause un débordement de pile dans une récursion C ?

Chaque appel prend une trame de mémoire de pile pour ses paramètres et ses variables locales, et la pile ne fait que quelques mégaoctets. Un cas de base manquant ou inatteignable signifie une récursion infinie et un plantage immédiat ; même une récursion correcte descendant des centaines de milliers de niveaux peut épuiser la pile.

Une fonction qui s'appelle elle-même

Rien n'empêche une fonction C de s'appeler elle-même. Son propre nom est visible dans son corps, donc ceci est légal :

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* s'appelle elle-meme - mais ne s'arrete jamais ! */
}

C'est aussi cassé. Cela affiche indéfiniment, jusque dans les négatifs, jusqu'à ce que le programme plante. Ce qui manque, c'est un cas de base : une condition sous laquelle la fonction retourne sans s'appeler.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* cas de base : on s'arrete */
        printf("Decollage !\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* cas recursif : un probleme plus petit */
}

int main(void) {
    countdown(5);
    return 0;
}

Toute fonction récursive a exactement ces deux parties :

Un cas de base - la plus petite entrée, répondue directement, sans nouvel appel.
Un cas récursif - résout le problème en fonction d'une version strictement plus petite de lui-même.

« Strictement plus petite » est ce que les gens ratent. countdown(n - 1) se rapproche de 0 à chaque appel. countdown(n) non, et countdown(n / 2) non plus si n pouvait rester 1 pour toujours. Chaque chemin doit rétrécir le problème, sinon le cas de base n'est jamais atteint.

La factorielle

Le premier exemple standard. n! vaut n × (n-1) × ... × 1, et 0! est défini comme 1. Cette définition est déjà récursive : n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* cas de base : 0! et 1! valent tous deux 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* cas recursif */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Déroulez factorial(4) pour voir comment la réponse s'assemble. Les appels descendent, et les multiplications se font sur le chemin du retour :

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (cas de base)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Rien n'est multiplié tant que le cas de base n'a pas retourné. Chaque appel en attente patiente en gardant son propre n, et c'est le point à intégrer : ces appels en attente occupent de la mémoire.

Notez le type de retour. Un int déborde vers 13!, produisant silencieusement un mauvais nombre - le C ne vérifie pas. unsigned long long vous mène à 20! et pas plus loin, car 21! dépasse 64 bits. La récursion n'est pas le facteur limitant ici ; c'est le type.

Le cas de base utilise n <= 1 plutôt que n == 1 délibérément : factorial(0) doit valoir 1, et <= s'en charge. Avec n == 1, appeler factorial(0) descendrait vers -1, -2, et ne se terminerait jamais - une bonne illustration de la façon dont un cas de base « évidemment correct » peut rater une entrée.

Fibonacci, et pourquoi la version naïve est un piège

Fibonacci est l'autre classique : chaque nombre est la somme des deux précédents, en partant de 0 et 1. La définition récursive s'écrit d'elle-même.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld appels)\n", n, result, calls);
    }
    return 0;
}

Regardez les nombres d'appels. fib(10) prend 177 appels ; fib(35) en prend près de 30 millions. Chaque pas de 5 multiplie le travail par environ onze.

La raison est visible dans l'arbre d'appels. fib(5) appelle fib(4) et fib(3) ; fib(4) appelle fib(3) encore ; et chacun d'eux recalcule fib(2) de zéro. Rien n'est mémorisé, donc les mêmes sous-problèmes sont résolus encore et encore, et le nombre d'appels croît à peu près comme 1,6ⁿ. fib(50) de cette façon tournerait des jours ; fib(100) survivrait à l'univers.

La version en boucle garde les deux dernières valeurs et est linéaire :

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) retourne instantanément. La leçon n'est pas « la récursion est lente » - c'est que la récursion avec des sous-problèmes qui se chevauchent est lente si vous ne mémorisez pas les réponses. Stockez les résultats dans un tableau au fur et à mesure (mémoïsation) et la version récursive devient linéaire elle aussi.

La pile d'appels et le débordement de pile

Chaque appel de fonction a besoin d'un endroit où garder ses paramètres, ses variables locales et l'adresse de retour. Ce stockage est une trame de pile, empilée au début de l'appel et dépilée au retour. La récursion empile les trames les unes sur les autres - factorial(1000) a mille trames vivantes en même temps, chacune avec son propre n.

La pile n'est pas grande. Une valeur par défaut typique est de 1 à 8 Mo, donc quelques dizaines de milliers de trames est la limite réaliste, et bien moins si chaque trame contient un gros tableau local. Dépassez-la et le programme meurt :

Segmentation fault (core dumped)

C'est un débordement de pile, et il y a deux façons d'en obtenir un :

La récursion infinie - un cas de base manquant ou inatteignable. C'est un bug, et le plantage est immédiat :

int bad(int n) {
    return bad(n - 1);      /* pas de cas de base - plante en une fraction de seconde */
}

Correcte mais trop profonde - une récursion par élément sur une liste d'un million d'entrées. La logique est juste ; l'approche ne tient pas dans la pile. Réécrivez-la en boucle, ou restructurez pour que la profondeur soit logarithmique (récursion sur des moitiés, comme la recherche dichotomique et le tri fusion, donne une profondeur d'environ 20 pour un million d'éléments).

Certains compilateurs peuvent transformer la récursion terminale - où l'appel récursif est la toute dernière chose que la fonction fait, sans travail en attente après lui - en boucle, réutilisant une seule trame. Le countdown ci-dessus est en récursion terminale ; factorial non, car la multiplication doit encore avoir lieu après le retour de l'appel. Mais le C n'exige pas cette optimisation, elle peut donc avoir lieu ou non selon le compilateur et les options. N'écrivez jamais du C qui ne fonctionne que parce que l'optimiseur a éliminé un appel terminal.

Là où la récursion gagne vraiment

Toute fonction récursive peut être réécrite en boucle, et pour un simple comptage, la boucle est manifestement meilleure. La récursion justifie sa place quand les données elles-mêmes sont récursives - quand une structure contient des copies plus petites d'elle-même.

La recherche dichotomique en est un exemple net : chercher dans une moitié, puis dans une moitié de celle-ci.

#include <stdio.h>

/* renvoie l'indice de la cible, ou -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* cas de base : plus rien */
    }
    int mid = low + (high - low) / 2;       /* evite le debordement sur de grands indices */

    if (a[mid] == target) {
        return mid;                         /* cas de base : trouve */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> indice %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Deux cas de base ici, ce qui est normal : un pour le succès et un pour l'épuisement. La profondeur est d'environ log₂(n), donc même un milliard d'éléments ne demandent que trente trames.

Autres endroits où la récursion s'impose naturellement : parcourir un arbre ou une liste chaînée, traverser des répertoires, analyser des expressions imbriquées, et les tris diviser-pour-régner comme le tri rapide et le tri fusion. Dans tous ces cas, le code récursif est plus court et plus clair que la boucle avec pile explicite qui le remplace.

Récursion ou boucle ?

Une boucle quand         le probleme est lineaire - compter, sommer, parcourir
La recursion quand       les donnees sont imbriquees - arbres, structures imbriquees, diviser pour regner
Reecrire la recursion    si la profondeur peut croitre sans limite avec la taille de l'entree
Jamais de recursion      quand les sous-problemes se chevauchent, sauf avec memoisation

Deux notes pratiques. Les appels récursifs coûtent un peu plus qu'une itération de boucle - une trame à empiler et dépiler à chaque fois - donc pour des boucles simples et très sollicitées, la version itérative gagne en vitesse comme en mémoire. Et le débogage est différent : une trace de pile issue d'une récursion profonde est composée de centaines de trames identiques, alors affichez le paramètre à l'entrée (comme le fait le compteur calls ci-dessus) quand quelque chose ne se termine pas.

Écrire une fonction récursive : un aide-mémoire

Trouvez le cas de base d'abord. Quelle est la plus petite entrée, et quelle est sa réponse ? Si vous ne pouvez pas la nommer, la fonction ne peut pas être écrite.
Supposez que l'appel récursif fonctionne. Ne le déroulez pas mentalement - faites confiance à factorial(n - 1) pour renvoyer (n-1)! et écrivez l'unique étape qui en fait la réponse.
Vérifiez que chaque chemin rétrécit. Chaque appel récursif doit se rapprocher du cas de base pour toute entrée possible, y compris 0 et les négatifs.
Vérifiez la profondeur. Combien de trames en gros cela descendra-t-il sur de vraies données ? Des milliers, c'est bien ; des millions, non.
Vérifiez les chevauchements. Si le même sous-problème est calculé deux fois, il vous faut de la mémoïsation ou une boucle.

Questions fréquentes

Qu'est-ce que la récursion en C ?

Une fonction qui s'appelle elle-même pour résoudre une version plus petite du même problème. Toute fonction récursive a besoin de deux choses : un cas de base qui retourne sans récursion, et un cas récursif qui s'en rapproche de façon mesurable. Sans le cas de base, les appels ne s'arrêtent jamais et le programme plante avec un débordement de pile.

Comment écrit-on une fonction factorielle en C ?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Le cas de base traite 0 et 1, et chaque appel récursif réduit n de un jusqu'à l'atteindre. Notez qu'un int déborde à 13! - utilisez unsigned long long pour de plus grandes valeurs.

Pourquoi le Fibonacci récursif est-il si lent en C ?

Parce que fib(n) appelle fib(n-1) et fib(n-2), qui recalculent encore et encore les mêmes sous-problèmes - le nombre d'appels croît exponentiellement, donc fib(50) prendrait des années. Le réécrire en boucle qui garde les deux dernières valeurs le rend linéaire et instantané.

Qu'est-ce qui cause un débordement de pile dans une récursion C ?

Chaque appel prend une trame de mémoire de pile pour ses paramètres et ses variables locales, et la pile ne fait que quelques mégaoctets. Un cas de base manquant ou inatteignable signifie une récursion infinie et un plantage immédiat ; même une récursion correcte descendant des centaines de milliers de niveaux peut épuiser la pile.

Concepts liés