Réponse.

Historique de la question :

La récursivité est supportée en C depuis ses débuts - elle s'intègre naturellement dans la paradigme du langage, permettant de construire des solutions compactes, en particulier pour les problèmes liés aux arbres, aux listes, et aux algorithmes complexes de décomposition.

Problème :

Les principaux risques d'utilisation de la récursivité sont la consommation excessive de la pile, la possibilité de débordement de pile (stack overflow), ainsi qu'une influence non évidente sur la performance (comparé à une implémentation cyclique). En C, il n'existe pas de moyen standard pour contrôler automatiquement la profondeur d'imbrication des appels.

Solution :

Avant d'utiliser la récursivité, évaluer le niveau d'imbrication maximal possible, utiliser la récursivité terminale si possible (pour optimisation par le compilateur), et ajouter une protection contre le débordement, par exemple, un compteur explicite de profondeur de récursivité. Une méthode alternative consiste à remplacer les appels récursifs par des boucles pour des tâches simples.

Exemple de code :

#include <stdio.h>
#define MAX_DEPTH 1000

int factorial(int n, int depth) {
    if (depth > MAX_DEPTH) {
        printf("Erreur : profondeur maximale de récursivité atteinte !\n");
        return -1;
    }
    if (n == 0) return 1;
    return n * factorial(n - 1, depth + 1);
}

int main() {
    printf("%d\n", factorial(5, 0)); // 120
    return 0;
}

Caractéristiques clés :

Pas de garantie de limitation automatique de la profondeur de récursivité
La récursivité consomme la pile, qui peut être limitée
La récursivité terminale peut être optimisée par le compilateur, mais pas toujours

Questions pièges.

La pile sera-t-elle nettoyée si, à l'intérieur d'une fonction récursive, un return est exécuté avant la fin de tous les appels ?

Oui, la pile est libérée à la sortie de la fonction actuelle. Aucun "données pendantes" ne restera sur la pile si celle-ci n'a pas débordé.

Peut-on déclarer des variables locales statiques à l'intérieur du corps d'une fonction récursive, et quel sera leur comportement ?

Oui. Ces variables seront communes à tous les appels récursifs, leur valeur sera conservée entre les appels, ce qui entraîne souvent des erreurs si ce comportement n'est pas pris en compte.

Le compilateur C influence-t-il la profondeur de récursivité et peut-il la limiter ?

Le compilateur ne limite pas directement la récursivité. La profondeur de récursivité est limitée par la taille de la pile du système d'exploitation ou par des facteurs externes.

Erreurs courantes et anti-patterns

Récursivité illimitée sans vérification de profondeur
Variables locales non initialisées ou statiques dans le corps d'une fonction récursive
Utiliser la récursivité là où une boucle serait plus simple et plus efficace

Exemple de la vie réelle

Un parcours récursif d'un arbre de recherche sans limite de profondeur :

Avantages :

Le code est concis, se lit facilement

Inconvénients :

Lors d'une grande profondeur d'arbre, le programme se terminait avec une erreur de débordement de pile.

Dans la version améliorée, un compteur de profondeur a été introduit et un passage à un parcours basé sur la pile a été effectué pour de grandes tailles d'arbre :