Scala 递归函数（长文讲解）

什么是 Scala 递归函数？

在编程的世界里，递归是一种让函数“自我调用”的技巧。听起来有点像镜子里照镜子，一个函数在执行过程中，自己又调用了自己。这听起来有点绕，但其实它非常强大，尤其在处理树状结构、列表遍历、数学计算等问题时，递归函数能写出简洁又优雅的代码。

Scala 递归函数，就是用 Scala 语言实现的递归逻辑。它不是什么神秘的黑科技，而是一种思维方式的体现。你可能会问：“为什么不用循环？” 答案是：有些问题天然适合递归表达，比如阶乘、斐波那契数列、二叉树遍历等。用递归写，代码更贴近问题的本质，也更容易理解。

想象一下，你正在拆一个俄罗斯套娃。每个娃娃里面都藏着一个更小的娃娃，直到最里面那个最小的。你每次打开一个，就去处理下一个。这个过程，就是递归的直观体现。Scala 递归函数，就像是你手里的那双手，一层层打开套娃，直到找到最核心的部分。

递归函数的基本结构

要写出一个正确的递归函数，必须满足两个核心条件：

1. 基础情况（Base Case）：递归的终点，也就是不再继续调用自己。如果没有基础情况，函数会无限调用下去，最终导致栈溢出（Stack Overflow）。
2. 递归情况（Recursive Case）：函数调用自身，但传入的参数要更接近基础情况。

我们来看一个最经典的例子：计算阶乘。

def factorial(n: Int): Int = {
  // 基础情况：0! = 1，1! = 1
  if (n <= 1) {
    1
  } else {
    // 递归情况：n! = n * (n-1)!
    n * factorial(n - 1)
  }
}

这段代码中，if (n <= 1) 就是基础情况。当 n 变成 1 或 0 时，函数直接返回 1，不再调用自己。

而 n * factorial(n - 1) 是递归情况。它把问题拆成“当前数乘上比它小 1 的数的阶乘”，然后让函数自己去算那个更小的问题。

比如你调用 factorial(4)，它会这样执行：

• factorial(4) → 4 * factorial(3)
• factorial(3) → 3 * factorial(2)
• factorial(2) → 2 * factorial(1)
• factorial(1) → 1（基础情况）

然后从下往上返回：2 * 1 = 2，3 * 2 = 6，4 * 6 = 24。最终结果是 24。

这种“先深入，再返回”的过程，就是递归的精髓。

常见应用场景：列表处理

在 Scala 中，列表（List）是不可变的，非常适合用递归来处理。因为列表的结构本身就是“头 + 尾”的递归结构。

我们来写一个函数，计算列表中所有元素的和。

def sumList(numbers: List[Int]): Int = {
  // 基础情况：空列表的和是 0
  if (numbers.isEmpty) {
    0
  } else {
    // 递归情况：第一个元素 + 剩下的列表的和
    numbers.head + sumList(numbers.tail)
  }
}

这里的关键是：

• numbers.isEmpty 判断是否为空，是基础情况。
• numbers.head 取列表第一个元素。
• numbers.tail 返回除了第一个元素以外的其余部分。

比如 sumList(List(1, 2, 3)) 的执行过程：

• head = 1，tail = List(2, 3)
• 1 + sumList(List(2, 3))
• → 1 + (2 + sumList(List(3)))
• → 1 + (2 + (3 + sumList(List())))
• → 1 + (2 + (3 + 0)) = 6

这个过程就像是“从头到尾，一个一个把数字加起来”，每一步都依赖于“剩下的部分”的结果。

递归 vs 循环：性能与可读性权衡

很多人会问：递归会不会比循环慢？会不会占用更多内存？

确实，递归每次调用都会在调用栈中保存上下文（如参数、返回地址等），所以它比循环占用更多内存。而且，如果递归太深，容易栈溢出。

但递归的优势在于：代码更清晰、更易理解。尤其在处理嵌套结构（如树、图）时，递归表达更自然。

比如，遍历一个二叉树：

// 定义二叉树节点
case class TreeNode(value: Int, left: Option[TreeNode], right: Option[TreeNode])

def inorderTraversal(node: Option[TreeNode]): List[Int] = {
  node match {
    case None => Nil
    case Some(n) =>
      // 左子树的遍历 + 根节点 + 右子树的遍历
      inorderTraversal(n.left) ++ List(n.value) ++ inorderTraversal(n.right)
  }
}

这个函数用递归实现中序遍历（左-根-右），结构清晰，逻辑一目了然。虽然性能上不如循环，但在可读性和表达力上，递归完胜。

递归不是万能的，但它在某些场景下，是“写得对”和“写得好”的完美结合。

如何避免递归陷阱？

递归虽然强大，但新手最容易犯的错误是忘记基础情况，导致无限递归。

比如下面这个错误代码：

def badFactorial(n: Int): Int = {
  // 缺少基础情况！
  n * badFactorial(n - 1)
}

调用 badFactorial(5) 会一直调用自己，n 从 5 → 4 → 3 → ... → -1 → -2 → ...，最终触发栈溢出错误。

另一个常见问题是：参数没有向基础情况靠拢。

比如：

def wrongCount(n: Int): Int = {
  if (n == 0) 0
  else 1 + wrongCount(n) // 没有变化！n 始终是 n
}

这里 wrongCount(n) 调用自己时，参数没有变化，永远无法到达基础情况。

所以记住：每次递归调用，参数必须“更接近”基础情况。

高级技巧：尾递归优化

在 Scala 中，有一个非常重要的优化机制：尾递归优化（Tail Recursion Optimization）。

什么是尾递归？就是递归调用是函数的最后一个操作。这样，编译器可以复用当前栈帧，避免栈增长。

我们把之前的 sumList 改成尾递归版本：

def sumListTailRecursive(numbers: List[Int]): Int = {
  // 使用累加器 acc 来保存中间结果
  def loop(remaining: List[Int], acc: Int): Int = {
    if (remaining.isEmpty) {
      acc // 最后一步返回 acc，是尾递归
    } else {
      loop(remaining.tail, acc + remaining.head)
      // 这里 loop 的调用是尾部的，可以优化
    }
  }
  loop(numbers, 0)
}

关键点：

• loop 是一个内部函数，接受两个参数：剩余列表和累加器。
• 递归调用 loop(remaining.tail, acc + remaining.head) 是函数的最后一步。
• 因此，编译器可以将其优化为循环，避免栈溢出。

要让 Scala 编译器识别尾递归，可以用 @scala.annotation.tailrec 注解：

import scala.annotation.tailrec

@tailrec
def factorialTailRecursive(n: Int, acc: Int = 1): Int = {
  if (n <= 1) acc
  else factorialTailRecursive(n - 1, n * acc)
}

这个版本的 factorialTailRecursive 是真正的尾递归，性能接近循环，同时保持了递归的清晰性。

总结

Scala 递归函数，是一种强大而优雅的编程范式。它不仅适用于数学计算，更在处理列表、树、图等递归结构时展现出天然优势。

我们学习递归，不只是为了写出“能运行的代码”，更是为了培养一种将复杂问题拆解为更小同类问题的思维方式。就像拆套娃，每打开一层，问题就变得更简单。

记住三个关键点：

1. 每个递归函数必须有基础情况。
2. 递归调用必须让参数向基础情况靠近。
3. 尽可能使用尾递归，以获得更好的性能。

当你能熟练写出简洁、无栈溢出风险的递归函数时，你就真正掌握了 Scala 的一种核心能力。这不仅是技术的提升，更是编程思维的跃迁。