递归函数是Python中通过自身调用解决可分解为更小同类子问题的编程方法，关键在于明确终止条件和问题规模缩减；如阶乘中n! = n × (n−1)!，base case为n==0或1，recursive case需确保输入趋近终止条件。

递归函数是Python中一种用函数自身调用自身来解决问题的编程技巧。它不是炫技，而是对“问题可分解为更小同类子问题”这一现实逻辑的自然表达。写好递归，关键不在语法，而在准确识别“分解规则”和“终止条件”。

递归的两个必要条件：终止条件与自我缩减

没有终止条件的递归会无限调用，最终触发RecursionError: maximum recursion depth exceeded。而每次递归调用，输入必须向终止条件靠近——也就是“问题规模变小”。比如计算阶乘：n! 可以拆成 n × (n−1)!，子问题 (n−1)! 的规模比原问题小1，且当 n == 0 或 n == 1 时直接返回1，这就是终止条件。

• 写递归前先问自己：这个问题最小、不可再分的情况是什么？（即 base case）
• 再问：当前问题怎么用一个更小的同类型问题表示？（即 recursive case）
• 避免在递归调用中修改全局变量或共享状态，否则容易逻辑错乱

经典实战：遍历嵌套列表与JSON-like结构

当数据存在任意深度的嵌套（如[1, [2, 3], [[4]], 5]），用循环逐层展开很麻烦；递归则简洁直观。核心思路是：遇到数字就收集，遇到列表就递归处理。

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))  # 递归处理子列表
        else:
            result.append(item)
    return result

这个模式同样适用于解析API返回的嵌套字典（如带"children"键的树形菜单）、读取文件系统目录树等场景。

小心陷阱：重复计算与栈溢出

斐波那契数列是递归入门例子，但朴素实现效率极低：

def fib(n):  # ❌ 指数级时间复杂度
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

因为fib(5)会重复计算fib(3)多次。实际项目中应改用记忆化（@lru_cache）或转为迭代。另外，默认递归深度限制约1000层，处理深层嵌套数据时需谨慎：

• 用sys.setrecursionlimit(3000)可临时提高限制（不推荐盲目调高）
• 对超深结构，优先考虑显式栈（list模拟）+ 循环的迭代写法
• 用try/except RecursionError做兜底，提示用户数据可能异常

适合递归的真实应用场景

不是所有循环都能/都应该改写成递归。以下场景天然契合递归思维：

• 树与图的遍历：二叉树的前/中/后序遍历、目录结构扫描、网页链接爬取（注意去重与深度控制）
• 分治算法：归并排序、快速排序、找数组最大值（分半递归求各自最大，再比较）
• 回溯搜索：八皇后、数独求解、全排列生成——每步试探，失败则退回上层继续尝试
• 数学定义直接映射：汉诺塔移动步骤、组合数 C(n,k)、正则表达式引擎内部匹配逻辑

递归的价值在于让代码更贴近问题本质，而不是追求形式上的“简洁”。能清晰表达“怎么分解”和“何时停止”，递归就立住了。