尾递归函数的性能

Question

各种书籍、文章、博客文章表明，将递归函数重写为尾递归函数可以使其更快。毫无疑问，对于生成斐波那契数或计算阶乘等琐碎的情况，它会更快。在这种情况下，有一种典型的重写方法 - 通过使用“辅助函数”和中间结果的附加参数。

TAIL RECURSION 很好地描述了尾递归函数和非尾递归函数之间的区别，以及如何将递归函数变成尾递归函数的可能方式。对于这种重写重要的是 - 函数调用的数量是相同的（before/after 重写），不同之处在于这些调用是如何针对尾递归进行优化的。

尽管如此，并不总是可以使用如此简单的技巧将函数转换为尾递归函数。我会将此类情况分类如下

函数仍然可以重写为尾递归，但这可能需要额外的数据结构和更实质性的实现更改
函数不能以任何方式重写为尾递归，但递归仍然可以通过使用循环和模仿堆栈来避免（我不是 100% 确定尾递归在某些情况下是不可能的，我无法描述如何识别此类案例，因此如果有关于此主题的任何学术研究 - link 将不胜感激)

现在让我考虑一个具体的例子，当函数可以通过使用额外的结构和改变算法的工作方式被重写为尾递归时。

示例任务：打印所有长度为 n 且包含 1 和 0 且没有相邻 1 的序列。

首先想到的明显实现如下（在每一步中，如果当前值为 0，则我们生成两个长度为 n-1 的序列，否则我们仅生成长度为 n-1 的序列，从 0 开始）

  def gen001(lvl: Int, result: List[Int]):Unit = {
    //println("gen001")
    if (lvl > 0) {
      if (result.headOption.getOrElse(0) == 0) {
        gen001(lvl - 1, 0 :: result)
        gen001(lvl - 1, 1 :: result)
      } else gen001(lvl - 1, 0 :: result)
    } else {
      println(result.mkString(""))
    }
  }

  gen001(5, List())

当当前元素为 0 时，避免两次函数调用并不是那么简单，但如果我们为中间序列中的每个值生成从级别 1 上的序列“01”开始的每个值，则可以做到这一点。在具有层次结构之后级别 1..n 的辅助序列我们可以从叶节点（或换句话说，从最后一次迭代的序列）开始重建结果（printResult）。

  @tailrec
  def g001(lvl: Int, current: List[(Int, Int)], result: List[List[(Int, Int)]]):List[List[(Int, Int)]] = {
    //println("g001")
    if (lvl > 1) {
      val tmp = current.map(_._1).zipWithIndex
      val next = tmp.flatMap(x => x._1 match {case 0 => List((0, x._2), (1, x._2)) case 1 => List((0, x._2))})
      g001(lvl - 1, next, next :: result)
    } else result
  }

  def printResult(p: List[List[(Int, Int)]]) = {
    p.head.zipWithIndex.foreach(x => 
      println(p.scanLeft((-1, x._2))((r1, r2) => (r2(r1._2)._1, r2(r1._2)._2)).tail.map(_._1).mkString("")))
  }

  val r = g001(5, List(0,1).zipWithIndex, List(List(0,1).zipWithIndex))

  println(r)

  printResult(r)

输出

List(List((0,0), (1,0), (0,1), (0,2), (1,2), (0,3), (1,3), (0,4), (0,5), (1,5), (0,6), (0,7), (1,7)), List((0,0), (1,0), (0,1), (0,2), (1,2), (0,3), (1,3), (0,4)), List((0,0), (1,0), (0,1), (0,2), (1,2)), List((0,0), (1,0), (0,1)), List((0,0), (1,1)))
00000
10000
01000
00100
10100
00010
10010
01010
00001
10001
01001
00101
10101

所以现在，如果我们比较两种方法，第一种方法需要更多的递归调用，但另一方面，它在内存方面效率更高，因为不需要额外的中间结果数据结构。

最后，问题是

是否有class的递归函数不能作为尾递归实现？如果是，如何识别它们？
是否有 class 递归函数，例如它们的尾递归实现不如非尾递归实现高效（例如在内存使用方面）。如果是这样，如何识别它们。（上面例子中的函数似乎属于这一类）

非常感谢指向学术研究论文的链接。

PS。 Thera 已经提出了一些相关问题，下面 links 可能非常有用

https://cs.stackexchange.com/questions/56867/why-are-loops-faster-than-recursion

更新

快速性能测试

尾递归函数可以简化为在每一步只存储辅助序列。这足以打印结果。让我去掉打印结果的图片函数并提供尾递归方法的修改版本。

  def time[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0)/1e9 + "s")
    result
  }

  @tailrec
  def gg001(lvl: Int, current: List[Int], result: List[List[Int]]):List[List[Int]] = {
    //println("g001")
    if (lvl > 1) {
      val next = current.flatMap(x => x match {case 0 => List(0, 1) case 1 => List(0)})
      gg001(lvl - 1, next, next :: result)
    } else result
  }

  time{gen001(30, List())}
  time{gg001(30, List(0,1), List(List(0,1)))}

  time{gen001(31, List())}
  time{gg001(31, List(0,1), List(List(0,1)))}

  time{gen001(32, List())}
  time{gg001(32, List(0,1), List(List(0,1)))}

输出

Elapsed time: 2.2105142s
Elapsed time: 1.2582993s
Elapsed time: 3.7674929s
Elapsed time: 2.4024759s
Elapsed time: 6.4951573s
Elapsed time: 8.6575108s

对于某些 N 尾递归方法开始比原始方法花费更多时间，如果我们继续增加 N，它将开始失败 java.lang.OutOfMemoryError: GC overhead limit exceeded

这让我认为管理尾递归方法的辅助数据结构的开销超过了性能提升，因为递归调用的数量较少以及它们的优化。

我可能没有选择最佳实现 and/or 数据结构，也可能是由于语言特定的挑战，但尾递归方法看起来并不是绝对最佳解决方案（就执行而言 time/resources) 即使对于这个特定任务。

Answer 1

1 中的 class 函数是空的：任何以递归方式编写的可计算函数都有一个等价的尾递归（在极限情况下，因为有图灵机的尾递归实现，你可以将任何可计算函数转换为图灵机定义，然后该函数的尾递归版本是运行通过图灵机的尾递归实现的定义）。

同样没有尾递归本质上比非尾递归效率低的函数。例如，在您的示例中，“它在内存方面效率更高，因为不需要额外的中间结果数据结构”是不正确的。中间结果所需的额外结构隐含在调用堆栈中（在尾递归版本中消失）。虽然调用堆栈可能是一个数组（比链表 space 更有效），但由于其通用性，它也存储了比所需更多的数据。

Answer 2

让我试着回答我自己的问题。

如果从函数体中调用的次数不超过一次，递归函数可以很容易地重写为尾递归函数。或者，任何函数都可以重写为循环，循环可以重写为尾递归函数，但这需要使用一些辅助数据结构 [至少用于] 堆栈。这样的实现可以比原来的方法稍微快一点（我相信这种差异可能因一种语言而异）但另一方面它会更麻烦且更难维护。

所以实际上，尾递归实现在不需要努力实现堆栈并且唯一的额外麻烦是存储中间结果时是有意义的。

尾递归函数的性能

Performance of the tail recursive functions

algorithm

recursion

performance

scala

tail-recursion