Comment fonctionne la récursion terminale en C ?

La récursion terminale en C

La récursion terminale est une forme particulière de récursion dans laquelle l’appel récursif est la dernière opération effectuée dans la fonction. Autrement dit, une fonction est dite récursive terminale si l’appel récursif se trouve en queue (ou à la fin) de la fonction, sans aucune opération à réaliser après cet appel. Cela permet aux compilateurs d’optimiser la récursion en remplaçant celle-ci par une boucle pour économiser de l’espace mémoire, en particulier sur la pile d’exécution.

Pourquoi est-ce important ?

Dans une récursion classique, chaque appel récursif crée un nouveau cadre d’exécution (stack frame) sur la pile. Cela peut entraîner une consommation excessive de mémoire lorsque le nombre d’appels récursifs devient important, ce qui peut provoquer un dépassement de pile (stack overflow). Avec la récursion terminale, certaines optimisations de compilateur permettent de réutiliser le même cadre d’exécution, ce qui réduit la profondeur de la pile et prévient ces problèmes.

Fonctionnement de la récursion terminale

Dans une fonction récursive classique, le résultat d’un appel récursif doit souvent être manipulé ou utilisé avant d’être renvoyé. Par exemple, le calcul de la factorielle ci-dessous est un cas de récursion non terminale :

Récursion non terminale (Factorielle) :

#include <stdio.h>

int factorielle(int n) {
    if (n == 0) {
        return 1;  // Cas de base
    }
    return n * factorielle(n - 1);  // Multiplication après l'appel récursif
}

int main() {
    int n = 5;
    printf("La factorielle de %d est %d\n", n, factorielle(n));
    return 0;
}

Explication :

Ici, l’appel récursif factorielle(n - 1) doit être effectué, puis le résultat est multiplié par n. Cela signifie que chaque appel récursif doit attendre le retour de la fonction pour effectuer l’opération de multiplication, ce qui nécessite de garder chaque appel en mémoire sur la pile.

Récursion terminale : Optimisation

Dans la récursion terminale, l’appel récursif est la dernière opération effectuée, et aucun traitement supplémentaire n’est effectué après l’appel. Cela permet au compilateur de réutiliser le cadre d’exécution de la fonction actuelle au lieu d’en créer un nouveau.

Pour transformer la fonction factorielle en une fonction récursive terminale, on utilise un accumulateur pour stocker le résultat intermédiaire, ce qui permet de passer le travail restant comme argument dans l’appel récursif.

Récursion terminale (Factorielle) :

#include <stdio.h>

// Fonction auxiliaire avec un accumulateur
int factorielle_acc(int n, int acc) {
    if (n == 0) {
        return acc;  // Cas de base : renvoyer l'accumulateur
    }
    return factorielle_acc(n - 1, acc * n);  // Appel récursif terminal
}

// Fonction principale
int factorielle(int n) {
    return factorielle_acc(n, 1);  // L'accumulateur commence à 1
}

int main() {
    int n = 5;
    printf("La factorielle de %d est %d\n", n, factorielle(n));
    return 0;
}

Explication :

factorielle_acc(n, acc) utilise un accumulateur acc pour stocker les résultats intermédiaires.
L’appel récursif factorielle_acc(n - 1, acc * n) est la dernière opération de la fonction. Cela signifie que dès que la fonction s’appelle, elle ne fait rien d’autre après l’appel récursif.
Ainsi, le compilateur peut optimiser cette récursion en remplaçant les appels successifs par une simple boucle interne.

Avantages de la récursion terminale

Efficacité mémoire : Comme la pile d’exécution n’est pas « empilée » avec chaque nouvel appel récursif, cela réduit la consommation de mémoire. La fonction récursive terminale réutilise le même cadre de pile, empêchant ainsi un dépassement de pile lors de récursions profondes.
Performances optimisées : La récursion terminale peut être aussi efficace que l’itération, car le compilateur peut transformer la récursion terminale en une boucle itérative, éliminant ainsi le coût des appels de fonction récursifs.

Exemple : Calcul de la somme d’un tableau

Prenons un autre exemple avec la somme des éléments d’un tableau.

Version non terminale (Récursion classique) :

#include <stdio.h>

int somme(int tableau[], int taille) {
    if (taille == 0) {
        return 0;  // Cas de base
    }
    return tableau[taille - 1] + somme(tableau, taille - 1);  // Appel récursif non terminal
}

int main() {
    int tableau[] = {1, 2, 3, 4, 5};
    int taille = sizeof(tableau) / sizeof(tableau[0]);

    printf("La somme des éléments du tableau est : %d\n", somme(tableau, taille));
    return 0;
}

Version terminale (Optimisée avec récursion terminale) :

#include <stdio.h>

// Fonction auxiliaire avec un accumulateur
int somme_acc(int tableau[], int taille, int acc) {
    if (taille == 0) {
        return acc;  // Retourner l'accumulateur
    }
    return somme_acc(tableau, taille - 1, acc + tableau[taille - 1]);  // Appel terminal
}

// Fonction principale
int somme(int tableau[], int taille) {
    return somme_acc(tableau, taille, 0);  // L'accumulateur commence à 0
}

int main() {
    int tableau[] = {1, 2, 3, 4, 5};
    int taille = sizeof(tableau) / sizeof(tableau[0]);

    printf("La somme des éléments du tableau est : %d\n", somme(tableau, taille));
    return 0;
}

Explication :

somme_acc() utilise un accumulateur acc qui stocke la somme des éléments du tableau jusqu’à présent.
L’appel récursif est la dernière opération, permettant ainsi une optimisation par récursion terminale.

Comparaison avec l’itération

Dans certains cas, la récursion terminale peut être aussi efficace qu’une solution itérative, car le compilateur peut optimiser la récursion terminale pour la transformer en une simple boucle.

Version itérative :

#include <stdio.h>

int somme_iterative(int tableau[], int taille) {
    int somme = 0;
    for (int i = 0; i < taille; i++) {
        somme += tableau[i];
    }
    return somme;
}

int main() {
    int tableau[] = {1, 2, 3, 4, 5};
    int taille = sizeof(tableau) / sizeof(tableau[0]);

    printf("La somme des éléments du tableau est : %d\n", somme_iterative(tableau, taille));
    return 0;
}

Explication :

L’approche itérative fonctionne sans appels récursifs, en utilisant simplement une boucle pour calculer la somme. En comparaison avec la récursion terminale, cette approche ne crée pas de cadre d’appel supplémentaire.
La récursion terminale peut être transformée par le compilateur en une boucle, produisant ainsi un résultat similaire en termes d’efficacité.

Récursion terminale vs récursion non terminale

Caractéristique	Récursion Terminale	Récursion Non Terminale
Position de l’appel	L’appel récursif est la dernière opération	L’appel récursif n’est pas la dernière opération
Efficacité mémoire	Réutilise le cadre de la pile (optimisable par le compilateur)	Nécessite un nouveau cadre à chaque appel
Performance	Souvent aussi efficace que l’itération	Moins performante pour de profondes récursions
Risque de dépassement de pile	Réduit le risque de dépassement de pile	Peut provoquer un dépassement de pile si trop d’appels
Exemples typiques	Calculs cumulés (factorielle, somme, etc.)	Tri, traitement des arbres, parcours complexes

La récursion terminale est une technique puissante qui permet de résoudre des problèmes récursifs tout en optimisant l’utilisation de la mémoire et des performances. En transformant une fonction récursive en récursion terminale, le compilateur peut potentiellement optimiser la fonction pour la transformer en boucle, réduisant ainsi le risque de dépassement de pile et améliorant l’efficacité.

L’utilisation de la récursion terminale est particulièrement utile dans des algorithmes où chaque appel ne nécessite pas de garder en mémoire le contexte des appels précédents, comme le