理解递归：在Python中的问题及解决方案-向日葵屋

理解递归：在Python中的问题及解决方案

原创短命女 2025-03-06 01:54 20阅读 0赞

递归是一种解决问题的方法，它通过将复杂的问题分解成相似的子问题来解决。在 Python 中，递归通常伴随着一个或多个基本情况。

问题定义：
假设我们正在编写一个函数，用于计算斐波那契数列中的某个项。原始递归实现可能如下：

def fibonacci(n):
    if n <= 0:
        return "Invalid input"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

解决方案：
在上述递归实现中，虽然它能正确计算斐波那契数列的项，但是随着n值的增长，效率会急剧下降。这主要是因为递归会重复计算很多子问题。

解决方案通常是采用“记忆化”或“动态规划”的方式来优化递归过程，避免重复计算：

def fibonacci(n, memo={}):
    if n <= 0:
        return "Invalid input"
    elif n in memo:
        return memo[n]
    else:
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
        return memo[n]
# 计算斐波那契数列的第10项
fib_10 = fibonacci(10)
print(fib_10)  # 输出：55