尾递归函数的性能

Question

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

尾部递归很好地描述了尾部递归函数和非尾部递归函数之间的差异，以及如何将递归函数转换为尾部递归函数。对于这种重写来说什么是重要的-函数调用的数量是相同的（重写之前/之后），不同之处在于如何为尾部递归优化这些调用。

然而，并不总是可以用如此简单的技巧将函数转换为尾递归函数。我将这样的情况分类如下

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

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

示例任务：打印长度为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

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

最后，问题是

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

高度赞赏学术研究论文的链接。

PS。锡拉已经提出了一些相关的问题，下面的链接可能非常有用

将线性递归函数重写为尾部递归函数

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

更新

快速性能测试

尾部递归函数可以简化为在每个步骤上只存储辅助序列。这就足够打印结果了。让我去掉打印结果的picture函数，并提供尾部递归方法的修改版本。

  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开销限制

这让我认为，由于递归调用及其优化的数量较少，为尾部递归方法管理辅助数据结构的开销超过了性能增益。

我可能没有选择最优化的实现和/或数据结构，也可能是由于语言特定的挑战，但即使对于这个特定的任务，尾部递归方法看起来也不是绝对的最佳解决方案（在执行时间/资源方面）。




Answer 1

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

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

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

Answer 2

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

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