<p>关键在于用尾递归实现不可变性与显式状态传递：如阶乘改写为fact(n, acc = 1) = if n == 0 then acc else fact(n - 1, n * acc)，所有中间结果均通过参数传递，无副作用、可组合、声明性强。</p>

把递归函数改写成符合函数式风格的结构，关键不是简单去掉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)
• 返回结果自然携带完整上下文，无需回溯，也没有副作用