Comment peut-on optimiser les appels récursifs pour améliorer leur efficacité?

Pour optimiser les appels récursifs, on utilise souvent les méthodes suivantes :

1. Mémorisation — sauvegarder les résultats des appels déjà effectués pour éviter les recalculs. Particulièrement utile pour les problèmes avec des sous-problèmes qui se chevauchent, comme le calcul des nombres de Fibonacci.

2. Recursion de queue — si l'appel récursif est la dernière opération dans la fonction, le compilateur peut optimiser l'appel en le transformant en boucle, ce qui réduit la consommation de mémoire de la pile.

3. Transformation de la récursion en itération — parfois, un algorithme récursif peut être réécrit sous forme de boucle, éliminant ainsi complètement les coûts liés aux appels de fonctions.

Exemple de mémorisation en C++ pour le calcul des nombres de Fibonacci :

#include <unordered_map>

std::unordered_map<int, long long> memo;

long long fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Cette approche accélère considérablement les calculs par rapport à la récursion naïve.