list - 反向列表 Scala

Question

给出以下代码:

import scala.util.Random

object Reverser {

  // Fails for big list
  def reverseList[A](list : List[A]) : List[A] = {
    list match {
      case Nil => list
      case (x :: xs) => reverseList(xs) ::: List(x)
    }
  }

  // Works
  def reverseList2[A](list : List[A]) : List[A] = {
    def rlRec[A](result : List[A], list : List[A]) : List[A] = {
      list match {
        case Nil => result
        case (x :: xs) => { rlRec(x :: result, xs) }
      }
    }
    rlRec(Nil, list)
  }

  def main(args : Array[String]) : Unit = {
    val random = new Random
    val testList = (for (_ <- 1 to 2000000) yield (random.nextInt)).toList
    // val testListRev = reverseList(testList) <--- Fails
    val testListRev = reverseList2(testList)
    println(testList.head)
    println(testListRev.last)
  }
}

为什么该函数的第一个版本失败(对于大输入)，而第二个版本有效。我怀疑这与尾递归有关，但我不太确定。有人能给我“傻瓜式”的解释吗？

Answer 1

好吧，让我尝试一下傻瓜的尾递归

如果您遵循反向列表的操作，您将得到

reverseList(List(1,2,3, 4))
reverseList(List(2,3,4):::List(1)
(reverseList(List(3,4):::List(2)):::List(1)   
((reverseList(List(4):::List(3)):::List(2)):::List(1)
Nil:::List(4):::List(3):::List(2):::List(1)
List(4,3,2,1)

有了 rlRec，你就拥有了

rlRec(List(1,2,3,4), Nil)
rlRec(List(2,3,4), List(1))
rlREc(List(3,4), List(2,1))
rlRec(List(4), List(3,2,1))
rlRec(Nil, List(4,3,2,1))
List(4,3,2,1)

不同之处在于，在第一种情况下，重写会变得越来越长。您必须记住在对 reverseList 的最后一次递归调用完成后要做的事情:要添加到结果中的元素。堆栈就是用来记住这一点的。当这太过分时，就会出现堆栈溢出。相反，对于rlRec，重写始终具有相同的大小。当最后一个rlRec完成时，结果就可用了。没有什么可做的，没有什么可记住的，不需要堆栈。关键在于，在rlRec中，递归调用是return rlRec(something else)，而在reverseList中，递归调用是return f(reverseList (somethingElse))，其中 f 开头为 _::: List(x)。您需要记住，您必须调用 f (这意味着也要记住 x)(在 scala 中不需要 return，只是为了清楚起见而添加。另请注意 val a = recursiveCall(x); doSomethingElse() 与 doSomethingElseWith(recursiveCall(x)) 相同，因此它不是尾调用)

当您进行递归尾部调用时

def f(x1,...., xn)
    ...
    return f(y1, ...yn)
    ...

实际上不需要记住第一个 f 的上下文来判断第二个 f 何时返回。所以可以重写

def f(x1....xn)
start:
    ...
    x1 = y1, .... xn = yn
    goto start
    ...

这就是编译器所做的，因此可以避免堆栈溢出。

当然，函数f需要在不是递归调用的地方有一个返回。这是由 goto start 创建的循环将退出的地方，就像递归调用系列停止的地方一样。