Scala：尾递归的跟踪调用及其局限

在7.2节中，我们提到过想要把更新var的while循环转换成仅使用val的更函数式风格的话，有时候你 可以使用递归。下面的例子是通过不断改善猜测数字来逼近一个值的递归函数：

def　approximate(guess:　Double):　Double　=　if　(isGoodEnough(guess))　guess

　else　approximate(improve(guess))

这样的函数，带合适的isGoodEnough和improve的实现，经常用在查找问题中。如果想要approximate 函数执行得更快，你或许会被诱惑使用while循环编写以尝试加快它的速度，如：

def　approximateLoop(initialGuess:　Double):　Double　=　{　var　guess　=　

initialGuess　while　(!isGoodEnough(guess))　　guess　=　improve(guess)　

guess}

两种approximate版本哪个更好？就简洁性和避免var而言，第一个，函数式的胜出。但是否指令式的 方式或许会更有效率呢？实际上，如果我们测量执行的时间就会发现它们几乎完全相同！这可能很令人 惊奇，因为递归调用看上去比简单的从循环结尾跳到开头要更花时间。

然而，在上面approximate的例子里，Scala编译器可以应用一个重要的优化。注意递归调用是 approximate函数体执行的最后一件事。像approximate这样，在它们最后一个动作调用自己的函数，被 称为尾递归：tail recursive。Scala编译器检测到尾递归就用新值更新函数参数，然后把它替换成一个 回到函数开头的跳转。

道义上你不应羞于使用递归算法去解决你的问题。递归经常是比基于循环的更优美和简明的方案。如 果方案是尾递归，就无须付出任何运行期开销。

跟踪尾递归函数

尾递归函数将不会为每个调用制造新的堆栈框架；所有的调用将在一个框架内执行。这可能会让检查 程序的堆栈跟踪并失败的程序员感到惊奇。例如，这个函数调用自身若干次之后抛出一个异常：

def　boom(x:　Int):　Int　=　if　(x　==　0)　throw　new　Exception("boom!")　

else　boom(x　-　1)　+　1

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索递归
， 函数
， 循环
， 尾调用
， 堆栈
， double
， 递归调用
， 函数跟踪
， 一个
， 递归指令
， 尾递归
， 递归效率
递归执行
，以便于您获取更多的相关知识。