Scala3中如何实现相互递归的尾调用优化？

我想编写一个完全迭代的程序，所有函数调用都处于尾位置（即调用后无需执行任何操作，不需要保留栈帧）。但下面的相互递归代码会触发栈溢出：

def foo(): Unit =
  bar()

def bar(): Unit =
  foo()

try
  foo()
catch
  case s: StackOverflowError =>
    println(" Stack overflow!")

原因很明确：每次foo调用bar、bar调用foo都会创建新的栈帧，JVM不会优化这种跨函数的尾调用。但像Scheme这类语言能让这段代码永久运行而不栈溢出，因为它们支持完整的尾调用优化。

对比单一递归的情况，这段代码却能永久运行无溢出：

def foo(): Unit = 
  foo()

foo()

我知道@tailrec注解，但它只适用于单一函数的尾递归，没法处理相互递归的场景。请问怎么修改第一个示例，让它像第二个示例一样无栈溢出地永久运行？

Scala本身的@tailrec不支持相互递归的尾调用优化，但可以通过以下两种方式解决：

1. 手动重构为单一递归函数 #

把原有的相互递归逻辑合并到一个函数中，用状态标记当前要执行的分支，转成单一函数的尾递归，就能被Scala编译器优化：

import scala.annotation.tailrec

@tailrec
def loop(isFoo: Boolean): Unit = {
  if (isFoo) {
    // 原foo的逻辑（此处为空，直接切换到bar分支）
    loop(isFoo = false)
  } else {
    // 原bar的逻辑（此处为空，直接切换到foo分支）
    loop(isFoo = true)
  }
}

loop(isFoo = true)

这种方式性能最优，直接利用Scala的尾递归优化，无额外运行开销。

2. 使用Trampoline（蹦床）模式 #

如果不想重构函数结构，可以用Scala标准库提供的scala.util.control.TailCalls工具，把每个尾调用包装成TailRec实例，通过堆上的调用展开替代栈上的栈帧累积：

import scala.util.control.TailCalls._

def foo(): TailRec[Unit] = tailcall(bar())
def bar(): TailRec[Unit] = tailcall(foo())

// 启动执行
foo().result()

蹦床模式会把每个尾调用转换成延迟计算，result()方法会不断执行这些计算直到完成。这种方式保留了原函数的拆分结构，但运行开销略高于单一递归。

内容的提问来源于stack exchange，提问作者Plegeus