8.9 尾递归
在7.2节，我们提到，如果要将一个不断更新var的while循环改写成只使用val的更加函数式的风格，可能需要用到递归。参考下面这个递归的函数例子，它通过反复改进猜测直到结果足够好的方式来取近似值：
有了合适的isGoodEnough和improve的实现，像这样的函数通常被用于搜索。如果你希望approximate函数跑得更快，你可能会想用while循环来尝试加快它的速度，就像这样：
这两个版本的approximate到底哪一个更好呢？从代码简洁和避免使用var的角度看，第一个函数式的版本胜出。不过指令式的方式是不是真的更高效呢？事实上，如果我们测量执行时间，这两个版本几乎完全一样！
这听上去有些出人意料，因为递归调用看上去比简单地从循环的末尾跳到开始要更“膨胀”。不过，在上面这个approximate的例子中，Scala编译器能够执行一个重要的优化。注意递归调用是approximate函数体在求值过程中的最后一步。像approximate这样在最后一步调用自己的函数，被称为尾递归（tail recursive）函数。Scala编译器能够检测到尾递归并将它替换成跳转到函数的最开始，并在跳转之前将参数更新为新的值。
这背后的意思是我们不应该回避使用递归算法来解决问题。通常，递归算法比基于循环的算法更加优雅、精简。如果解决方案是尾递归的，那么我们并不需要支付任何（额外的）运行时开销。
跟踪尾递归函数
尾递归函数并不会在每次调用时构建一个新的栈帧，所有的调用都会在同一个栈帧中执行。这一点可能会出乎检查某个失败程序的栈跟踪信息（stack trace）的程序员的意料。例如，下面这个函数调用自己若干次之后抛出异常：
该函数并不是尾递归的，因为它在递归调用之后还执行了一个递增操作。在执行这段代码时，你将看到预期的效果：
如果你把boom改成尾递归的：
尾递归优化
approximate编译后的代码本质上跟approximateLoop编译后的代码是一样的。两个函数都被编译成相同的13条指令的Java字节码。如果仔细检查Scala编译器对尾递归的approximate生成的字节码，你会看到，虽然isGoodEnough和improve是在方法体内被调用的，approximate自己并没有。Scala编译器已经将递归调用优化掉了：public double approximate(double);
将得到这样的结果：
这一次，你将只会看到一个bang的栈帧。你可能会想是不是bang在调用自己之前就崩溃了，但事实并非如此。如果你觉得在看尾递归优化后的栈跟踪信息时会困惑，可以把它关掉，做法是给scala命令或scalac编译器如下参数：
有了这个参数，你将得到一个更长的栈跟踪信息：
尾递归的局限
在Scala中使用尾递归是比较受限的，因为用JVM指令集实现更高级形式的尾递归非常困难。Scala只能对那些直接尾递归调用自己的函数做优化。如果递归调用是间接的，比如如下示例中的两个相互递归的函数，Scala就没法优化它们：
同样地，如果最后一步调用的是一个函数值（而不是发起调用的那个函数自己），也无法享受到尾递归优化。参考下面这段递归程序：
funValue变量指向一个本质上只是打包了对nestedFun调用的函数值。当你应用这个函数到某个入参时，它转而将nestedFun应用到这个入参上，然后返回结果。因此，你可能希望Scala编译器能执行尾递归优化，不过编译器在这个情况下并不会这样做。尾递归优化仅适用于某个方法或嵌套函数在最后一步操作中直接调用自己，并且没有经过函数值或其他中间环节的场合（如果你还没有完全理解尾递归，参考8.9节）。