Optimisation d’une Fonction Récursive

L’optimisation d’une fonction récursive consiste à améliorer ses performances, principalement en termes de temps d’exécution et d’utilisation de la mémoire. Voici les principales techniques d’optimisation utilisées pour les fonctions récursives en C :

1. Utiliser la Mémorisation (Memoization)

La mémorisation consiste à stocker les résultats intermédiaires des appels récursifs pour éviter de recalculer les mêmes résultats à plusieurs reprises. Cela est particulièrement utile pour des problèmes comme la suite de Fibonacci, où la récursion simple conduit à une répétition d’appels inutiles.

Exemple sans optimisation (récursion brute) :

Le calcul de Fibonacci récursif sans optimisation recalculera plusieurs fois les mêmes valeurs, ce qui est inefficace.

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 40;
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    return 0;
}

Problème :

Le nombre d’appels récursifs augmente de manière exponentielle, car les mêmes sous-problèmes sont résolus plusieurs fois.
Le temps d’exécution pour fibonacci(40) peut être extrêmement long.

Solution : Optimisation par mémorisation

En utilisant un tableau pour mémoriser les résultats déjà calculés, on évite de recalculer les mêmes sous-problèmes plusieurs fois. Cette technique améliore significativement les performances.

#include <stdio.h>

int memo[1000];  // Tableau pour mémoriser les résultats déjà calculés

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n];  // Si le résultat est déjà calculé, on le retourne
    }
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);  // Calcul et mémorisation
    return memo[n];
}

int main() {
    int n = 40;

    // Initialiser le tableau memo à -1 pour indiquer que rien n'a encore été calculé
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }

    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    return 0;
}

Amélioration :

Grâce à la mémorisation, chaque sous-problème est résolu une seule fois, transformant la complexité de l’algorithme de O(2^n) à O(n).
Cela évite le recalcul des valeurs déjà déterminées et réduit significativement le temps d’exécution.

2. Utiliser la Récursion Terminale (Tail Recursion)

La récursion terminale est une forme d’optimisation où l’appel récursif est la dernière instruction d’une fonction. Certains compilateurs optimisent automatiquement ce type de récursion, car ils peuvent remplacer l’appel récursif par une simple boucle, évitant ainsi l’accumulation d’appels récursifs sur la pile d’exécution.

Exemple : Calcul de la factorielle avec récursion non terminale

int factorielle(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorielle(n - 1);  // Appel récursif non terminal
}

Ici, l’appel récursif n’est pas optimisé car la multiplication n * doit être effectuée après le retour de l’appel récursif, donc chaque appel reste sur la pile jusqu’à la fin.

Optimisation avec récursion terminale

En transformant la fonction pour que l’appel récursif soit la dernière opération, la pile d’appels n’a plus besoin de conserver les états intermédiaires.

Code optimisé :

#include <stdio.h>

int factorielle_helper(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return factorielle_helper(n - 1, acc * n);  // Appel récursif terminal
}

int factorielle(int n) {
    return factorielle_helper(n, 1);
}

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

Explication :

factorielle_helper prend un argument supplémentaire acc (accumulateur) qui stocke le résultat intermédiaire. L’appel récursif est la dernière instruction dans la fonction, ce qui permet aux compilateurs de réduire les appels empilés.
Certains compilateurs optimisent les appels récursifs terminaux en les convertissant en boucles internes, ce qui économise de l’espace sur la pile.

3. Convertir la récursion en itération

Dans certains cas, il est possible de transformer une fonction récursive en une version itérative, en utilisant une boucle pour éviter les appels récursifs et économiser l’espace mémoire.

Exemple : Calcul de Fibonacci avec itération

Version récursive :

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Version itérative :

#include <stdio.h>

int fibonacci_iterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 40;
    printf("Fibonacci(%d) = %d\n", n, fibonacci_iterative(n));
    return 0;
}

Amélioration :

L’approche itérative économise de l’espace mémoire et est souvent plus rapide car elle évite les appels de fonction successifs.
Cette approche est particulièrement utile pour les algorithmes simples comme Fibonacci ou la factorielle, où l’itération est plus intuitive.

4. Limiter la profondeur de la récursion

Pour des problèmes où la profondeur de la récursion peut être très grande, comme le tri rapide (quicksort) sur des tableaux de grande taille, il est important de limiter la profondeur de la récursion pour éviter les erreurs de dépassement de pile (stack overflow).

Stratégie d’optimisation :

Passer à l’itération : Pour les appels récursifs sur des sous-problèmes très grands, il est souvent plus sûr de passer à une solution itérative après un certain niveau de profondeur.
Limiter la taille des sous-problèmes : Dans certains algorithmes (comme le tri), il peut être utile de limiter la taille des sous-problèmes et de gérer les petits cas avec des méthodes plus simples, comme l’algorithme insertion sort pour les tableaux très petits.

5. Diviser pour régner (Divide and Conquer)

La stratégie diviser pour régner est une méthode d’optimisation utilisée dans de nombreux algorithmes récursifs, comme quicksort et mergesort. Elle consiste à diviser un problème en sous-problèmes plus petits, à les résoudre de manière récursive, puis à combiner les résultats pour obtenir la solution finale.

Complément : Mergesort

Voici la suite de l’exemple de l’algorithme Mergesort avec la fonction de fusion complétée et la fonction récursive pour trier le tableau.

Fonction de fusion complète :

#include <stdio.h>

// Fonction pour fusionner deux sous-tableaux
void fusion(int tableau[], int gauche, int milieu, int droite) {
    int i, j, k;
    int n1 = milieu - gauche + 1;
    int n2 = droite - milieu;

    // Créer des tableaux temporaires pour stocker les deux moitiés
    int G[n1], D[n2];

    // Copier les données dans les tableaux temporaires
    for (i = 0; i < n1; i++)
        G[i] = tableau[gauche + i];
    for (j = 0; j < n2; j++)
        D[j] = tableau[milieu + 1 + j];

    // Fusionner les tableaux temporaires dans le tableau d'origine
    i = 0;  // Indice initial du premier sous-tableau (G)
    j = 0;  // Indice initial du second sous-tableau (D)
    k = gauche;  // Indice initial du tableau fusionné

    // Fusionner les deux sous-tableaux en ordre croissant
    while (i < n1 && j < n2) {
        if (G[i] <= D[j]) {
            tableau[k] = G[i];
            i++;
        } else {
            tableau[k] = D[j];
            j++;
        }
        k++;
    }

    // Copier les éléments restants du sous-tableau G[]
    while (i < n1) {
        tableau[k] = G[i];
        i++;
        k++;
    }

    // Copier les éléments restants du sous-tableau D[]
    while (j < n2) {
        tableau[k] = D[j];
        j++;
        k++;
    }
}

Fonction récursive pour tri avec Mergesort :

// Fonction récursive pour trier le tableau avec l'algorithme Mergesort
void mergesort(int tableau[], int gauche, int droite) {
    if (gauche < droite) {
        // Calculer l'indice du milieu
        int milieu = gauche + (droite - gauche) / 2;

        // Appliquer récursivement Mergesort aux deux moitiés
        mergesort(tableau, gauche, milieu);
        mergesort(tableau, milieu + 1, droite);

        // Fusionner les deux moitiés triées
        fusion(tableau, gauche, milieu, droite);
    }
}

Fonction principale pour tester le tri :

int main() {
    int tableau[] = {12, 11, 13, 5, 6, 7};
    int taille = sizeof(tableau) / sizeof(tableau[0]);

    printf("Tableau avant tri :\n");
    for (int i = 0; i < taille; i++) {
        printf("%d ", tableau[i]);
    }
    printf("\n");

    // Appliquer l'algorithme Mergesort
    mergesort(tableau, 0, taille - 1);

    printf("Tableau après tri par Mergesort :\n");
    for (int i = 0; i < taille; i++) {
        printf("%d ", tableau[i]);
    }
    printf("\n");

    return 0;
}

Explication :

Mergesort divise le tableau en deux moitiés, les trie récursivement, puis fusionne les deux moitiés triées.
La fonction fusion() s’occupe de fusionner deux sous-tableaux triés en un seul tableau trié.
Cet algorithme a une complexité O(n log n) et est très efficace pour trier de grands ensembles de données.

Conclusion

L’optimisation des fonctions récursives en C est essentielle pour améliorer les performances, surtout lorsque la profondeur de récursion devient grande ou que des sous-problèmes sont recalculés plusieurs fois. Les techniques d’optimisation incluent la mémorisation, la récursion terminale, la conversion en itération, et l’approche diviser pour régner.

Ces techniques permettent non seulement d’améliorer l’efficacité en termes de temps d’exécution, mais aussi de réduire la consommation de mémoire et d’éviter les problèmes tels que les erreurs de dépassement de pile. Le choix de la méthode d’optimisation dépend de la nature du problème que vous résolvez et des ressources disponibles.