递归函数正确需满足：边界条件完整且可达，每次递归必须缩小问题规模；否则将导致无限调用或逻辑错误。
递归函数写得对不对，关键看两点：边界条件是否完整、每次递归是否向边界靠近。缺一不可，否则就是无限调用或逻辑错误。
边界条件必须明确且可达
边界（也叫递归出口）是递归停止的唯一依据。它不能依赖外部变量，也不能靠概率触发，必须由参数直接判断、在有限步内必然满足。
常见错误：
- 漏写边界，比如斐波那契中忘了处理 n == 0 或 n == 1
- 边界写反，如把 if n 写成 if n >= 1:，导致永远进不去
- 边界无法到达，例如参数没变小，或每次减的是负数、零，造成死循环
每次递归必须缩小问题规模
递归调用自身时，传入的参数必须比当前更接近边界。这不是约定，是数学归纳的基础——没有“缩小”，就没有收敛保证。
立即学习“Python免费学习笔记（深入）”；
典型做法：
- 数值类问题：n → n-1、n → n//2 等
- 序列类问题：list → list[1:]、string → string[1:] 或用索引控制范围（更省内存）
- 树形结构：递归左右子树，节点数严格减少
注意：切片 list[1:] 会新建列表，时间空间开销大；用索引（如 helper(arr, left+1, right)）更高效。
性能隐患：栈深度与重复计算
Python 默认递归深度限制约 1000 层，超过就报 RecursionError。深层递归不仅容易越界，还带来显著调用开销。
更要警惕的是“指数级重复计算”，比如朴素递归求斐波那契：
def fib(n):
if n return fib(n-1) + fib(n-2)
算 fib(5) 时，fib(3) 被算两次，fib(2) 被算三次……时间复杂度 O(2ⁿ)。加个记忆化（@lru_cache）或改用迭代，立刻降到 O(n)。
什么情况适合递归？什么该换思路？
递归天然适合“自相似结构”：树遍历、分治算法（归并、快排）、回溯（全排列、N皇后）、语法解析等。这些场景逻辑清晰，代码简洁。
但以下情况建议优先考虑迭代：
- 线性问题能用循环干净解决（如累加、翻转字符串）
- 数据量大、深度可能超千层（如链表长度 10⁵）
- 需要精确控制资源，或做尾递归优化（Python 不支持尾递归优化，写了也没用）
不复杂但容易忽略。
