面试题：Python自定义函数的递归与优化

Question

使用Python编写一个递归函数来计算斐波那契数列的第n项。然后，优化这个函数，使其能够更高效地计算（提示：可以使用记忆化技术）。请详细解释你优化的思路以及优化前后函数的时间复杂度变化。

Answer 1

1. 普通递归实现

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

2. 记忆化（Memoization）优化实现

def fibonacci_memoized(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    return memo[n]

3. 优化思路

• 普通递归：每次计算fibonacci(n)时，都会重复计算fibonacci(n - 1)和fibonacci(n - 2)，存在大量的重复计算。例如计算fibonacci(5)，fibonacci(3)会被计算两次，fibonacci(2)会被计算三次等。随着n的增大，重复计算量呈指数级增长。
• 记忆化优化：使用一个字典memo来存储已经计算过的斐波那契数。每次计算前先检查字典中是否已有结果，如果有则直接返回，避免重复计算。这样就将许多重复的子问题计算次数减少到1次。

4. 时间复杂度变化

• 普通递归：时间复杂度为$O(2^n)$。因为每次调用函数都会产生两个新的递归调用，形成一个高度为n的二叉树结构，节点数（即计算次数）约为$2^n$。
• 记忆化优化：时间复杂度为$O(n)$。因为每个n只被计算一次，计算过的结果被存储在memo中，之后再次计算时直接从memo获取，总共需要计算n次，所以时间复杂度为线性。