Python 中带备忘录的递归（记忆化搜索）

带备忘录的递归，也被称为记忆化搜索，是一种优化递归算法的方法。这种方法的核心思想是将递归函数的结果缓存起来，以避免重复计算。这样可以大大减少递归算法的时间复杂度。

Python 中实现带备忘录的递归，一般需要使用字典作为缓存。具体操作步骤如下：

1. 创建一个字典 memo，用于缓存中间结果。
2. 在递归函数中，首先检查当前参数是否已经被计算过，如果是，则直接返回缓存中的结果。
3. 如果当前参数没有被计算过，则继续递归计算，并将结果保存到 memo 中。
4. 最后返回计算结果。

下面是一个示例代码：

memo = {}

def fibonacci(n):
    if n in memo:
        return memo[n]

    if n <= 2:
        result = 1
    else:
        result = fibonacci(n-1) + fibonacci(n-2)

    memo[n] = result
    return result

在这个例子中，我们将斐波那契数列的递归求解过程进行了优化。memo 字典用于缓存中间结果，避免重复计算。如果 n 已经在 memo 中存在了，我们直接返回 memo[n]；如果 n 还没有被计算过，则继续递归计算，并将结果保存到 memo 中。最后返回计算结果。

使用带备忘录的递归算法，可以大大提高递归算法的效率。对于斐波那契数列等需要重复计算的问题，带备忘录的递归能够将时间复杂度降为线性或者线性对数级别。