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

Question

编写一个Python函数，使用递归方式计算斐波那契数列的第n项。然后对这个递归函数进行优化，减少重复计算，提高执行效率，并阐述优化的思路和方法。

Answer 1

1. 递归方式计算斐波那契数列

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

2. 优化递归函数（使用记忆化）

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

3. 优化思路和方法

• 思路：在原始递归实现中，会有大量重复计算。例如计算 fibonacci_recursive(5) 时，fibonacci_recursive(3) 会被计算两次。优化的思路是避免重复计算，将已经计算过的结果保存起来，下次需要时直接从保存的结果中获取。
• 方法：这里采用记忆化（Memoization）技术，通过一个字典（memo）来存储已经计算过的斐波那契数。每次计算前先检查字典中是否已经存在该结果，如果存在则直接返回，否则计算并将结果存入字典。这样就大大减少了重复计算，提高了执行效率。