递归函数是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"键的树形菜单）、读取文件系统目录树等场景。
立即学习“Python免费学习笔记（深入）”；
小心陷阱：重复计算与栈溢出
斐波那契数列是递归入门例子，但朴素实现效率极低：
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)、正则表达式引擎内部匹配逻辑
递归的价值在于让代码更贴近问题本质，而不是追求形式上的“简洁”。能清晰表达“怎么分解”和“何时停止”，递归就立住了。
