首页 > 其他 > 详细

scala tail recursive优化,复用函数栈

时间:2014-10-18 20:56:26      阅读:325      评论:0      收藏:0      [点我收藏+]
在scala中如果一个函数在最后一步调用自己(必须完全调用自己,不能加其他额外运算子),那么在scala中会复用函数栈,这样递归调用就转化成了线性的调用,效率大大的提高。
If a function calls itself as its last action, the function‘s stack frame can be reused. This is called tail recursion.
=> Tail recursive functions are iterative process

这里实现了两个版本的阶乘函数,一个是普通的写法,另外一个使用了tail recursive的优化
/*
In Scala, only directly recursive call to the current function are optimized.
One can require that a function is tail-recursive using a @tailrec annotation:
   @tailrec
   def gcd(a: Int, b: Int): Int = ...
If the annotation is given, and the implementation of gcd were not
tail recursive, an error would be issued.
*/

import scala.annotation.tailrec

object exercise {

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

  //a tail recursive version of factorial
  def factorialTailRecursion(n: Int): Int = {
    @tailrec
    def loop(acc: Int, n: Int): Int =
      if (n == 0) acc
      else loop(acc * n, n-1)
      loop(1, n)
  }

  factorial(4)
  factorialTailRecursion(4) //optimized! the function‘s stack frame can be reused!
}

 

scala tail recursive优化,复用函数栈

原文:http://www.cnblogs.com/yanghuahui/p/4033563.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!