Implémentation récursive de fonctions C++ : Comment optimiser la récursion à l'aide de la technique de mémorisation ?

Technologie de mémo récursif optimisée : utilisez des mémos pour stocker les résultats calculés afin d'éviter des calculs répétés. Utilisez unordered_map en C++ comme rappel pour vérifier si le résultat existe avant de le calculer. Stockez les résultats du calcul et renvoyez-les pour améliorer les performances des tâches gourmandes en calcul telles que le parcours de répertoires.

Implémentation récursive de fonctions C++ : Optimisation à l'aide de la technique du mémo

La récursion est une technique puissante qui permet aux fonctions de s'appeler elles-mêmes. Cependant, lorsqu'une fonction récursive résout le même problème, elle peut entraîner de nombreux calculs répétés, réduisant ainsi les performances d'exécution. La technique de mémorisation est une technique courante pour optimiser les algorithmes récursifs et peut améliorer considérablement l'efficacité.

Qu'est-ce que la technologie mémo ?

La technique du mémo consiste à créer et à maintenir un tableau appelé mémo. Ce tableau stocke les résultats des appels de fonction qui ont été calculés. Lorsqu'un appel de fonction identique se produit à nouveau, nous vérifions d'abord le mémo pour voir s'il a déjà été évalué. S'il a déjà été calculé, nous renvoyons directement le résultat stocké pour éviter un double calcul.

Implémentation

La mise en œuvre de l'optimisation des mémos en C++ est très simple. Voici un exemple de fonction qui utilise des mémos pour calculer les nombres de Fibonacci :

#include <unordered_map>

using namespace std;

// 创建备忘录
unordered_map<int, int> memo;

int fibonacci(int n) {
  // 检查备忘录中是否存在结果
  if (memo.find(n) != memo.end()) {
    return memo[n]; // 返回存储的结果
  }

  // 计算结果并存储在备忘录中
  int result;
  if (n <= 1) {
    result = 1;
  } else {
    result = fibonacci(n - 1) + fibonacci(n - 2);
  }
  memo[n] = result;
  return result;
}

Dans le code ci-dessus, le résultat de memo 无序映射用作备忘录。fibonacci 函数首先检查 memo 中是否存在指定数字 n. Si elle est présente, la fonction renvoie directement le résultat stocké. Sinon, il calcule le résultat, le stocke dans le mémo et le renvoie.

Cas pratique

Prenons un exemple concret : compter le nombre de fichiers dans un répertoire. Nous pouvons utiliser un algorithme récursif, qui parcourt le répertoire et traite tous les sous-répertoires de manière récursive. Sans l’utilisation de mémos, l’algorithme rencontrerait de graves doubles comptages lors du parcours de grandes structures de répertoires.

En utilisant les mémos, nous pouvons améliorer considérablement les performances. Lorsqu'on accède à un répertoire, nous pouvons stocker son chemin dans un souvenir et également connaître son nombre de fichiers. Lorsque le même répertoire est consulté ultérieurement, nous pouvons récupérer le décompte directement à partir du mémo, évitant ainsi le double comptage.

Conclusion

La technique du mémo est un moyen efficace d'optimiser les fonctions récursives en C++. En stockant les résultats déjà calculés, nous évitons les calculs répétés, améliorant ainsi les performances d'exécution. L'optimisation des mémos est particulièrement bénéfique lors de la résolution d'algorithmes contenant un grand nombre de sous-problèmes répétés.

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!