Scala尾递归
yuanged 人气:2
# 递归函数应用
首先，我们来对比两个递归方法的求值步骤。
假设有方法`gcd`，用来计算两个数的最大公约数。下面是欧几里得算法的实现:
```
def gcp(a: Int, b: Int): Int =
if (b == 0) a else gcp(b, a % b)
```
`gcp(14, 21)`的求解过程如下:
```
gcp(14, 21)
if (21 == 0) 14 else gcd(21, 14 % 21)
if (false) 14 else gcd(21, 14 % 21)
gcd(21, 14 % 21)
gcd(21, 14)
if (14 == 0) 21 else gcp(14, 21 % 14)
if (false) 21 else gcp(14, 21 % 14)
gcp(14, 7)
gcd(7, 14 % 7)
gcd(7, 0)
if (0 == 0) 7 else gcd(0, 7 % 0)
if (true) 7 else gcd(0, 7 % 0)
7
```
再看数列阶乘问题:
```scala
def factorial(n: Int): Int =
if (n == 0) 1 else n * factorial(n - 1)
```
`factorial(4)`的求解过程如下:
```
factorial(4)
if (4 == 0) 1 else 4 * factorial(4 - 1)
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * (factorial(1)))
4 * (3 * (2 * (1 * factorial(0)))
4 * (3 * (2 * (1 * 1))
24
```
上面两种递归的执行顺序有什么区别呢？先看最大公约数的递归求解过程，每次递归调用的时候不需要记录其他的值，而是直接调用递归函数；再看阶乘的递归求解过程，我们发现每次递归调用的结果还需要乘上一个n才能得到结果，也就是说每次递归调用都需要维系调用之前的状态。
这就是递归的两种不同形式，首递归(head recursion)和尾递归(tail recursion)。上面的阶乘递归解法就是一种首递归，而最大公约数的球解则是一个尾递归。
对于首递归，递归函数调用之后，后续还有计算，因此在执行过程中需要不断的使用新的栈帧来保存临时状态。首递归在递归层数较少的情况下不会有问题，但是由于需要消耗栈帧来保存临时变量，当递归层数达到一定数量的时候会导致stack overflow的异常。
对于尾递归，所有的计算都在递归调用之前完成，因此不需要保存临时状态，也就是说完全可以复用当前栈帧。如果复用了栈帧，那么不管递归多少层都不会发生stack overflow。这种复用栈帧的优化本质其实就是迭代计算，可以说优化后的尾递归是迭代的一种表达方式，其执行效率和迭代一样。
广义上来说，只要一个递归函数的最后一个操作只由调用函数组成（不管是其他函数，还是其他函数），栈帧都可以复用，这这种递归形式都可以叫做尾递归。而Scala中并不是对所有的尾递归都做了优化，只有那些满足严格尾递归形式的递归函数才会被优化而服用栈帧。
# 尾递归栈帧
为了不引起歧义，这里的尾递归指的是scala中能够进行栈帧复用优化的递归。我们先来看看非尾递归函数的堆栈，定义如下非尾递归函数`headRecStackFrame`,并调用`headRecStackFrame(10)`,:
```scala
@tailrec
def headRecStackFrame(n: Int): Int =
if (n == 0) throw new Exception("boom!")
else n * headRecStackFrame(n - 1)
headRecStackFrame(5)
```
我们得到的异常堆栈如下：
```scala
java.lang.Exception: boom!
at cc.databus.tailrecur.TailRecursionStackFrame$.headRecStackFrame(TailRecursionStackFrame.scala:13)
at cc.databus.tailrecur.TailRecursionStackFrame$.headRecStackFrame(TailRecursionStackFrame.scala:14)
at cc.databus.tailrecur.TailRecursionStackFrame$.headRecStackFrame(TailRecursionStackFrame.scala:14)
at cc.databus.tailrecur.TailRecursionStackFrame$.headRecStackFrame(TailRecursionStackFrame.scala:14)
at cc.databus.tailrecur.TailRecursionStackFrame$.headRecStackFrame(TailRecursionStackFrame.scala:14)
at cc.databus.tailrecur.TailRecursionStackFrame$.headRecStackFrame(TailRecursionStackFrame.scala:14)
at cc.databus.tailrecur.TailRecursionStackFrame$.main(TailRecursionStackFrame.scala:26)
at cc.databus.tailrecur.TailRecursionStackFrame.main(TailRecursionStackFrame.scala)
```
可以看到6个`headRecStackFrame`调用的栈帧。
再来看看尾递归函数的堆栈。定义尾递归函数`tailRecStackFrame`，并调用`tailRecStackFrame(5)`:
```scala
@tailrec
def tailRecStackFrame(n: Int): Int =
if (n == 0) throw new Exception("boom!")
else tailRecStackFrame(n - 1)
tailRecStackFrame(5)
```
得到如下异常堆栈:
```scala
java.lang.Exception: boom!
at cc.databus.tailrecur.TailRecursionStackFrame$.tailRecStackFrame(TailRecursionStackFrame.scala:9)
at cc.databus.tailrecur.TailRecursionStackFrame$.main(TailRecursionStackFrame.scala:18)
at cc.databus.tailrecur.TailRecursionStackFrame.main(TailRecursionStackFrame.scala)
```
这里我们看到只有一个`tailRecStackFrame`的调用栈帧。
对比`headRecStackFrame`和`tailRecStackFrame`的异常堆栈，可以明显发现`tailRecStackFrame`尾递归函数服用了调用栈帧。
# Scala中的尾递归
前面提到，Scala中的只对严格形式的尾递归进行了优化，对于严格形式的尾递归，我们可以放心使用，不用担心栈溢出的问题。为了帮助我们判断一个递归函数是否是满足scala的尾递归优化策略，scala提供了`@tailrec`注解，这个注解一方面可以方便我们识别尾递归，同事编译器会自动检测该函数是否是尾递归，若不是，会导致如下编译错误:
```scala
Error:(15, 10) could not optimize @tailrec annotated method headRecStackFrame: it contains a recursive call not in tail position
else n * headRecStackFrame(n - 1)
```
在scala中，下面情况下scala不会优化:
* 通过函数值实现递归
* 不是直接调用递归函数，而是嵌套在其他函数中调用
通过函数值实现递归的例子:
```scala
object NonTailRecursionExample {
val fun = funcValRecursion _
def funcValRecursion(a: Int): Int =
if(a == 0) throw new Exception("Boom!")
else fun(a - 1)
def main(args: Array[String]): Unit = {
funcValRecursion(3)
}
}
```
嵌套函数调用实现递归的:
```scala
object NonTailRecursionExample {
def anotherFunc(a: Int): Int =
nestFunRecursion(a)
def nestFunRecursion(a: Int): Int =
if (a == 0) throw new Exception("Boom!")
else anotherFunc(a - 1)
def main(args: Array[String]): Unit = {
nestFunRecursion(3)
}
}
```
加载全部内容