关键在于用尾递归实现不可变性与显式状态传递：如阶乘改写为fact(n, acc = 1) = if n == 0 then acc else fact(n - 1, n * acc)，所有中间结果均通过参数传递，无副作用、可组合、声明性强。
把递归函数改写成符合函数式风格的结构，关键不是简单去掉return f(...)，而是让整个逻辑体现不可变性、无副作用、组合性和声明性。函数式风格不排斥递归，但要求递归是“干净”的——尤其是尾递归，且状态全部显式传递。
用尾递归替代普通递归
普通递归（如 fib(n) = fib(n-1) + fib(n-2)）在每次调用后还需做加法，无法被编译器优化，也违背函数式中“计算即值传递”的直觉。改成尾递归后，所有中间结果都作为参数带入下一层：
- 引入辅助参数承载累积值，例如阶乘：
fact(n, acc = 1) = if n - 确保递归调用是函数体中**最后一个操作**，后面不接任何计算或条件分支
- 在支持尾调用优化（TCO）的语言（如 Scala、Kotlin）中，加上
@tailrec注解可触发编译期循环替换；在 JavaScript 或 Python 中虽无原生 TCO，但结构本身已更接近函数式语义
用高阶函数和组合代替递归展开
很多递归场景本质是对数据结构做“分解–处理–合并”，这恰好对应函数式中的映射、折叠、展开等原语：
- 遍历列表求和？直接用
foldLeft(0)(_ + _)或reduce(_ + _)，无需手写递归 - 树的前序遍历？可用
root :: left.traverse ++ right.traverse（若类型支持 concat），把递归逻辑封装进traverse方法内部 - 对嵌套结构做变换？优先考虑
map、flatMap等组合子，它们天然递归友好且可链式调用
用代数数据类型（ADT）明确递归结构
函数式语言中，递归往往与数据定义耦合。比如二叉树不是靠指针模拟，而是明确定义为：
-
sealed trait Tree[+A]case object Leaf extends Tree[Nothing]case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] - 所有操作（size、sum、map）都基于模式匹配 + 递归调用，结构清晰、类型安全、易于推导
- 这种写法把“递归在哪里发生”从控制流移到了数据形态上，更符合函数式“数据驱动行为”的理念
避免隐式状态，把“变化”转为“新值”
函数式拒绝在递归中修改变量或外部状态。例如 DFS 搜索路径，不要用全局 path.push() + path.pop()，而应：
- 把当前路径作为参数传入：
dfs(node, currentPath: List[A]) - 每次进入子节点时生成新路径：
dfs(child, node.value :: currentPath) - 返回结果自然携带完整上下文，无需回溯，也没有副作用
