面试题：Python递归函数中如何避免栈溢出

Question

在Python中设计一个递归函数来计算斐波那契数列。请阐述在实现过程中，怎样做可以避免因递归过深导致栈溢出问题，并给出具体的代码示例及优化思路。

Answer 1

1. 普通递归实现斐波那契数列

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

2. 避免栈溢出的优化思路

• 使用记忆化（Memoization）：通过保存已经计算过的斐波那契数，避免重复计算。这样可以大大减少递归调用的次数，从而降低栈的深度。
• 使用迭代方式：迭代实现斐波那契数列不依赖于递归调用栈，也就不会出现栈溢出问题。

3. 记忆化递归实现

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

4. 迭代实现

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b