JVM 中的循环与递归：Scala 函数式编程实践

1. 概述

在本教程中，我们将深入探讨 JVM 中的循环与递归机制。我们会重点关注常见的编程陷阱以及优化技巧，帮助你写出更简洁、更安全的代码。

2. 栈与栈帧

理解 Scala 中函数式循环的前提是搞清楚栈（Stack）的工作原理。

2.1. 栈（Stack）

栈，也被称为调用栈（call stack），根据 JVM 官方文档的定义，是一种用于存储局部变量和部分运算结果的数据结构，同时控制方法的调用与返回。

✅ 每个 JVM 线程都有一个私有的 JVM 栈，在线程创建时一同创建。

✅ JVM 对栈的两个主要操作是 入栈（push） 和 出栈（pop）。

栈的默认大小因平台而异，详见文档。虽然可以手动增加栈大小，但更好的做法是优化代码，使其栈安全（stack-safe）。

⚠️ 栈中保存了线程当前执行点的所有方法调用链信息。调用栈随着程序执行动态变化。

⚠️ 每个方法的局部变量都存储在其对应的栈帧中。线程只能访问自己的栈，局部变量对其他线程不可见。

即使两个线程执行相同的代码，它们的局部变量也会分别保存在各自的线程栈中，互不影响。

2.2. 栈帧（Stack Frame）

栈帧构成 Java 栈的基本单位。每个栈帧对应一次方法调用，包含以下三部分：

局部变量数组
操作数栈（Operand Stack）
常量池引用（Constant Pool Reference）

栈帧的大小取决于方法中局部变量和操作数栈的大小，单位是“word”。

每当 JVM 调用一个方法时，它会根据方法所需的局部变量和操作数栈空间创建一个适当大小的栈帧并压入栈中。

每个方法调用都会生成一个新的栈帧。执行期间，代码只能访问当前栈帧中的变量。

3. 循环（Loops）

Scala 作为一门多范式语言，支持命令式和函数式的循环写法。下面我们以求 List[Int] 的和为例进行对比。

3.1. 命令式写法

def getSumOfList(list: List[Int]): Int = {
  var sum = 0
  for (i <- 0 until list.length) {
    sum += list(i)
  }
  sum
}
assert(getSumOfList((1 to 10).toList) == 55)

❌ 虽然逻辑正确，但使用了 var，不推荐。特别是在并发场景下，容易引发竞态条件。

3.2. 递归写法

递归是一种函数调用自身的编程技术。它将大问题拆解为小问题，直到达到终止条件。

def getSumOfListRecursive(list: List[Int]): Int = {
  list match {
    case Nil => 0
    case head :: tail =>
      head + getSumOfListRecursive(tail)
  }
}
assert(getSumOfListRecursive((1 to 10).toList) == 55)

✅ 没有 var，代码更干净。

❌ 但递归会不断创建栈帧，导致在大数据集上容易触发 StackOverflowError。

getSumOfListRecursive((1 to 10000).toList)
// java.lang.StackOverflowError

⚠️ 递归深度与栈帧数量成正比，容易耗尽栈空间。

3.3. 尾递归优化（Tail Recursion）

尾递归是一种特殊的递归形式，其函数的最后一步操作是调用自身。

✅ Scala 编译器会对尾递归进行优化，将其转换为等价的 while 循环，只使用一个栈帧。

def getSumOfListTailRecursive(numbers: List[Int]): Int = {
  def innerFunction(list: List[Int], accumulator: Int): Int = {
    list match {
      case Nil => accumulator
      case head :: tail => innerFunction(tail, head + accumulator)
    }
  }
  innerFunction(numbers, 0)
}
assert(getSumOfListTailRecursive((1 to 1000000).toList) == 1784293664)

✅ 使用尾递归后，即使是百万级别的数据也不会爆栈。

3.4. 如何确认尾递归？

你可以使用 @scala.annotation.tailrec 注解来强制编译器校验是否为尾递归：

import scala.annotation.tailrec

@tailrec
def sumTailRec(list: List[Int], acc: Int): Int = {
  list match {
    case Nil => acc
    case head :: tail => sumTailRec(tail, acc + head)
  }
}

❌ 如果不是尾递归，编译器会报错。

3.5. 栈帧数量对比验证

我们可以通过打印当前线程的栈帧数量来验证普通递归和尾递归的区别。

普通递归：

val length = Thread.currentThread().getStackTrace.length + 1
def getSumOfListRecursive(list: List[Int]): Int = {
  list match {
    case Nil =>
      println(Thread.currentThread().getStackTrace.length - length) // 输出 100（递归100层）
      0
    case h :: t =>
      h + getSumOfListRecursive(t)
  }
}
assert(getSumOfListRecursive((1 to 100).toList) == 5050)

尾递归：

val length = Thread.currentThread().getStackTrace.length + 1
def getSumOfListTailRecursive(numbers: List[Int]): Int = {
  @tailrec
  def innerFunction(list: List[Int], accumulator: Int): Int = {
    list match {
      case Nil =>
        println(Thread.currentThread().getStackTrace.length - length) // 输出 1（只有一层栈帧）
        accumulator
      case head :: tail =>
        innerFunction(tail, head + accumulator)
    }
  }
  innerFunction(numbers, 0)
}
assert(getSumOfListTailRecursive((1 to 1000000).toList) == 1784293664)

✅ 尾递归无论数据量多大，始终只占用一个栈帧。

4. 总结

本文带你了解了 Scala 中的循环与递归机制，重点讲解了：

栈与栈帧的基本概念
普通递归的栈溢出问题
尾递归的优势与实现方式
如何通过注解验证尾递归
通过栈帧数量对比验证尾递归优化效果

✅ 推荐在处理大数据结构时优先使用尾递归，避免栈溢出。

📌 本文代码示例可在 GitHub 获取。

Persistence

REST

Security