首页 > 代码库 > scala tail recursive优化，复用函数栈

scala tail recursive优化，复用函数栈

2024-07-27 21:54:24   212人阅读

在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 nottail recursive, an error would be issued.*/import scala.annotation.tailrecobject 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优化，复用函数栈


联系
我们