尾递归要求递归调用是函数最后动作且直接返回其结果；改写需将回溯计算转为参数累积，新增累加器，单路径线性递归易改，多分支或需合并子结果的难改。

尾递归写法的核心原则是：递归调用必须是函数执行的最后一个动作，且返回值直接来自递归调用本身，中间不能夹杂任何计算、赋值或逻辑运算。

关键判断标准

看函数最后一行是不是形如 return f(...) —— 没有 n + f(...)，没有 if-else 分支后才调用，也没有把结果存进变量再返回。只要递归调用之后还做别的事，就不是尾递归。

改写普通递归的通用步骤

把隐式依赖调用栈的“回溯计算”，转为显式通过参数传递的“下探累积”：

• 识别原函数中每次递归后还要做的操作（比如乘法、加法、字符串拼接），把这些操作提前到递归调用前完成
• 新增一个累加器参数（常叫 acc、sum、a/b 等），用来携带当前已算出的部分结果
• 把原终止条件对应到新函数的出口，直接返回累加器值
• 原函数变成启动入口，只负责传入初始状态（如 acc=1、a=0, b=1）

典型例子对照

阶乘：
普通写法：return n * factorial(n-1) → 乘法在递归后，非尾递归
尾递归写法：return factorial(n-1, n * acc) → 乘法已在参数里算好，调用即最后一步

斐波那契：
普通写法：return fib(n-1) + fib(n-2) → 双分支+回溯相加，指数级且非尾
尾递归写法：return fib(n-1, b, a+b) → 用两个参数滚动记录前两项，每步只调一次，线性时间

哪些递归适合改？哪些难改？

适合改的通常满足：

• 单路径递归（不分支，不合并多个子结果）
• 可归纳出清晰的中间状态（如累计和、已处理字符、当前节点+计数）
• 原逻辑是线性推进的（如遍历链表、倒序打印、求和求积）

难改或不值得改的包括：

• 树的深度优先搜索中需回溯合并左右子树结果（如求最大路径和）
• 递归结构天然多分支且状态耦合紧密（如八皇后、部分回溯算法）
• 语言运行时根本不优化尾调用（如 CPython、现代 V8），改了也省不下栈空间，纯为逻辑清晰或后续转循环铺路