给出以下代码:
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)
}
}
为什么该函数的第一个版本失败(用于大量输入),而第二个变量却起作用。我怀疑这与尾巴递归有关,但我不太确定。有人可以给我“假人”的解释吗?
最佳答案
好吧,让我尝试假人的尾递归
如果按照reverseList要做的事情,您将获得
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中不需要返回,只是为了清楚起见添加了它。请注意val a = recursiveCall(x); doSomethingElse()
与doSomethingElseWith(recursiveCall(x))
相同,因此它不是尾部调用)当您进行递归尾调用时
def f(x1,...., xn)
...
return f(y1, ...yn)
...
实际上,当第二个
f
返回时,无需记住它的上下文。所以可以改写def f(x1....xn)
start:
...
x1 = y1, .... xn = yn
goto start
...
那就是编译器所做的,因此可以避免堆栈溢出。
当然,函数
f
需要在某个地方返回,这不是递归调用。这就是goto start
创建的循环将退出的地方,就像递归调用系列停止的地方一样。