C++ 函数的递归实现：如何使用备忘录技术优化递归？

优化递归的备忘录技术：使用备忘录存储已计算结果，避免重复计算。在 c++++ 中使用 unordered_map 作为备忘录，在计算前检查是否存在结果。存储计算结果后返回，提高遍历目录等计算密集型任务的性能。

C++ 函数的递归实现：使用备忘录技术优化

递归是一个强大的技术，它允许函数调用自身。然而，当递归函数解决相同的问题时，它可能会导致大量的重复计算，从而降低运行时性能。备忘录技术是一种优化递归算法的常用技术，它可以显著提高效率。

什么是备忘录技术？

备忘录技术涉及创建和维护一个表，称为备忘录。该表存储已经计算过的函数调用的结果。当一个相同的函数调用再次出现时，我们首先检查备忘录以查看它是否已经计算过。如果已经计算过，我们直接返回存储的结果，从而避免重复计算。

实施

在 C++ 中实现备忘录优化非常简单。下面是一个示例函数，它使用备忘录来计算斐波那契数：

#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;
}