亲宝软件园·资讯

展开

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) } } ```

加载全部内容

相关教程
猜你喜欢
用户评论