在 Scala 中是否有创建尾递归函数的通用方法？

Question

在检查 Intel 的 BigDL repo 时，我偶然发现了这个方法：

private def recursiveListFiles(f: java.io.File, r: Regex): Array[File] = {
  val these = f.listFiles()
  val good = these.filter(f => r.findFirstIn(f.getName).isDefined)
  good ++ these.filter(_.isDirectory).flatMap(recursiveListFiles(_, r))
}

我注意到它不是尾递归的，所以决定写一个尾递归版本：

private def recursiveListFiles(f: File, r: Regex): Array[File] = {
@scala.annotation.tailrec def recursiveListFiles0(f: Array[File], r: Regex, a: Array[File]): Array[File] = {
  f match {
    case Array() => a
    case htail => {
      val these = htail.head.listFiles()
      val good = these.filter(f => r.findFirstIn(f.getName).isDefined)
      recursiveListFiles0(these.filter(_.isDirectory)++htail.tail, r, a ++ good)
    }
  }
}
recursiveListFiles0(Array[File](f), r, Array.empty[File])
}

与我习惯的相比，这变得困难的是文件可以转换为数组 [File] 的概念，这增加了另一个层次。

具有以下成员的数据类型的递归背后的理论是什么？

def listTs[T]: T => Traversable[T]

Answer 1

简答

如果您概括这个想法并将其视为 monad（适用于任意类型参数的多态事物），那么您将无法实现尾递归实现。

Trampolines 试图通过提供一种方法来评估递归计算而不会溢出堆栈来解决这个问题。总体思路是创建成对的（结果，计算）流。因此，在每一步中，您都必须 return 到该点的计算结果和创建下一个结果的函数（又名 thunk）。

来自 Rich Dougherty 的博客：

A trampoline is a loop that repeatedly runs functions. Each function, called a thunk, returns the next function for the loop to run. The trampoline never runs more than one thunk at a time, so if you break up your program into small enough thunks and bounce each one off the trampoline, then you can be sure the stack won't grow too big.

在 Scala 中是否有创建尾递归函数的通用方法？

Is there a universal method to create a tail recursive function in Scala?

scala

tail-recursion

简答

更多 + 参考资料