Partage d'expériences pratiques de récursivité C++ : résumé de l'optimisation du code et des compétences

Techniques d'optimisation récursive : Optimisation de la récursion de queue : le compilateur effectue tous les calculs avant d'appeler la fonction elle-même pour améliorer l'efficacité. Mémoire : stocke les sorties précédemment calculées pour éviter les calculs répétés. Itération : utilisez un algorithme d'itération au lieu de la récursivité pour améliorer la lisibilité et éviter le débordement de pile.

Partage d'expérience pratique sur la récursivité C++ : résumé de l'optimisation du code et des compétences

Dans le développement réel, la récursivité est souvent utilisée pour résoudre des problèmes complexes. Il permet aux fonctions de s'appeler elles-mêmes, créant ainsi des piles d'appels imbriquées. Cependant, des appels récursifs excessifs peuvent provoquer un débordement de pile et un crash du programme.

Voici quelques conseils pour optimiser le code récursif, avec des cas pratiques :

1. Optimisation de la récursion de queue

La récursion de queue fait référence à tous les calculs effectués par une fonction avant de s'appeler, et s'appeler est la dernière action de la fonction. fonction . Pour les appels récursifs de fin, le compilateur peut l'optimiser en remplaçant le pointeur de fonction dans la pile d'appels au lieu de pousser un nouveau cadre de pile.

int factorial(int n) {
  return n == 0 ? 1 : n * factorial(n - 1);
}

En utilisant l'indicateur d'optimisation des appels de queue, le compilateur peut reconnaître cette récursion comme une récursion de queue et l'optimiser.

int factorial(int n) __attribute__ ((tailcall));

2. Mémoire

La mémoire est une technique utilisée pour stocker la sortie de la même entrée présentée précédemment. Lorsque la récursion continue de répéter le même calcul, la mémorisation peut améliorer considérablement les performances.

int fib(int n) {
  static std::map<int, int> memo;
  if (memo.count(n) > 0) {
    return memo[n];
  }
  return memo[n] = n < 2 ? n : fib(n - 1) + fib(n - 2);
}

Ce code utilise std::map4101e4c0559e7df80e541d0df514fd80 memo pour stocker les nombres de Fibonacci précédemment calculés.

3. Itération

Dans certains cas, les problèmes récursifs peuvent être remplacés par des algorithmes itératifs. Cela évite le risque de débordement de pile et améliore la lisibilité du code.

int factorial(int n) {
  int result = 1;
  while (n > 0) {
    result *= n--;
  }
  return result;
}

Ce code calcule la factorielle de manière itérative au lieu d'utiliser la récursivité.

Cas pratique

Séquence de Fibonacci

Le calcul du nombre de Fibonacci à un index donné peut être utilisé comme un cas pratique classique de récursion. L'implémentation récursive utilisant des techniques de mémoire est la suivante :

int fib(int n) {
  static std::map<int, int> memo;
  if (memo.count(n) > 0) {
    return memo[n];
  }
  return memo[n] = n < 2 ? n : fib(n - 1) + fib(n - 2);
}

En utilisant ce code, nous pouvons calculer efficacement de grands nombres de Fibonacci sans nous soucier du débordement de pile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!