尾递归函数性能分析及可转换性、效率对比相关技术咨询

目前大量书籍、技术文章、博客都认为将递归函数改写为尾递归函数可以提升运行速度，该结论在生成斐波那契数列、计算阶乘等简单场景下确实成立，这类场景通常采用「辅助函数+存储中间结果的额外参数」的通用改写方案。改写前后函数调用次数一致，性能差异来源于尾递归的调用优化机制。

通用改写方案的局限性 #

并非所有递归函数都可以通过上述简单方法转换为尾递归，这类场景可分为两类：

• 函数可改写为尾递归，但需要引入额外数据结构，对实现逻辑做大幅调整
• 函数无法通过任何手段改写为尾递归，但可通过循环+模拟栈的方式避免递归（目前无法确认是否存在完全无法实现尾递归的场景，也不了解这类场景的识别方法）

典型场景示例 #

任务要求：打印所有长度为n、仅包含0和1、且不存在相邻1的序列
最直观的非尾递归实现逻辑如下：每一步中若当前值为0，则生成两个长度为n-1的序列；若当前值为1，则仅生成以0开头的长度为n-1的序列，代码实现：

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. 是否存在一类递归函数，其尾递归实现的效率（如内存使用率）无法达到非尾递归实现的水平？若存在，如何识别这类函数？（上述示例中的函数似乎属于该类别）

补充性能测试结果 #

尾递归函数可简化为仅存储每一步的辅助序列，足够用于打印结果。以下为剔除打印逻辑后的修改版尾递归实现性能测试：

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错误。可见尾递归方案管理辅助数据结构的开销超过了递归调用优化带来的性能收益。可能存在实现、数据结构选型或语言特性层面的优化空间，但即使在该示例场景下，尾递归也并非绝对最优的解决方案。

内容的提问来源于stack exchange，提问作者Dr Y Wit