Scala尾递归

首先,我们来对比两个递归方法的求值步骤来看看递归函数应用。
假设有方法gcd,用来计算两个数的最大公约数。下面是欧几里得算法的实现:

1
2
def gcp(a: Int, b: Int): Int = 
if (b == 0) a else gcp(b, a % b)

gcp(14, 21)的求解过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
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

再看数列阶乘问题:

1
2
def factorial(n: Int): Int = 
if (n == 0) 1 else n * factorial(n - 1)

factorial(4)的求解过程如下:

1
2
3
4
5
6
7
8
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),:

1
2
3
4
5
6
@tailrec
def headRecStackFrame(n: Int): Int =
if (n == 0) throw new Exception("boom!")
else n * headRecStackFrame(n - 1)

headRecStackFrame(5)

我们得到的异常堆栈如下:

1
2
3
4
5
6
7
8
9
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):

1
2
3
4
5
6
@tailrec
def tailRecStackFrame(n: Int): Int =
if (n == 0) throw new Exception("boom!")
else tailRecStackFrame(n - 1)

tailRecStackFrame(5)

得到如下异常堆栈:

1
2
3
4
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的调用栈帧。

对比headRecStackFrametailRecStackFrame的异常堆栈,可以明显发现tailRecStackFrame尾递归函数服用了调用栈帧。

Scala中的尾递归

前面提到,Scala中的只对严格形式的尾递归进行了优化,对于严格形式的尾递归,我们可以放心使用,不用担心栈溢出的问题。为了帮助我们判断一个递归函数是否是满足scala的尾递归优化策略,scala提供了@tailrec注解,这个注解一方面可以方便我们识别尾递归,同事编译器会自动检测该函数是否是尾递归,若不是,会导致如下编译错误:

1
2
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不会优化:

  • 通过函数值实现递归
  • 不是直接调用递归函数,而是嵌套在其他函数中调用

通过函数值实现递归的例子:

1
2
3
4
5
6
7
8
9
10
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)
}
}

嵌套函数调用实现递归的:

1
2
3
4
5
6
7
8
9
10
11
12
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)
}
}

Scala字符串插值 Scala函数循环

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×