Python中递归是什么？请求详解递归核心概念

递归的本质很简单：函数自己调用自己，但要让它能正常工作，必须满足两个核心条件：

1. 递归的两个核心要素 #

• 基线条件：函数停止调用自己的终止条件，没有它就会无限递归直到报错。
• 递归条件：函数调用自身的触发条件，且每次调用都要让问题规模向基线条件靠近。

2. 经典例子：阶乘计算 #

先看最直观的阶乘实现，一步步拆解执行过程：

def factorial(n):
    # 基线条件：0的阶乘是1，停止递归
    if n == 0:
        return 1
    # 递归条件：n的阶乘 = n * (n-1)的阶乘，问题规模每次减1
    else:
        return n * factorial(n - 1)

手动模拟执行（以factorial(3)为例）： #

1. 调用factorial(3)，n=3≠0，执行3 * factorial(2)
2. 调用factorial(2)，n=2≠0，执行2 * factorial(1)
3. 调用factorial(1)，n=1≠0，执行1 * factorial(0)
4. 调用factorial(0)，触发基线条件，返回1
5. 回溯计算：1*1=1 → 2*1=2 → 3*2=6，最终返回6

3. 另一个常见例子：斐波那契数列 #

斐波那契数列的递归实现能帮你理解问题拆分的思路：

def fibonacci(n):
    # 基线条件：n=0返回0，n=1返回1
    if n <= 1:
        return n
    # 递归条件：第n项 = 第n-1项 + 第n-2项
    else:
        return fibonacci(n-1) + fibonacci(n-2)

不过这个实现有个问题：会重复计算大量子问题（比如计算fibonacci(5)时会重复计算fibonacci(3)两次）。可以用Python的lru_cache装饰器缓存结果，优化效率：

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

4. 递归常见误区 #

• 忘记基线条件：比如去掉阶乘里的if n==0，函数会无限调用自己，直到触发Python的递归深度限制（默认约1000层），抛出RecursionError。
• 递归条件不向基线靠近：如果把阶乘里的factorial(n-1)写成factorial(n)，同样会无限递归。
• 栈溢出风险：每次递归调用都会被存入调用栈，深度太大时会超出栈容量。Python默认不支持尾递归优化（尾递归是指递归调用是函数最后一步操作），所以深递归问题建议用迭代替代。

5. 练习递归的正确姿势 #

• 从简单问题入手：先练阶乘、数组求和、反转字符串这类逻辑简单的问题，手动画出调用栈的每一步。
• 对比递归与迭代：把递归实现改成迭代版本（比如阶乘的循环实现），理解递归其实是用调用栈自动管理了问题的拆分与回溯。
• 分析复杂度：搞清楚每个递归实现的时间、空间复杂度，明白为什么有些递归需要优化（比如斐波那契的缓存优化）。

内容的提问来源于stack exchange，提问作者ABEL