scala尾递归

什么是递归

一个函数直接或者间接的调用本身，这就是递归。典型案例斐波那契数列

def fib(n: Int): Int = {
  if (n == 1)  0
  else if (n == 2)  1
  else {
    fib(n - 1) + fib(n - 2)
  }
 }

以上的方法中当n>3时,就是典型的递归了。
递归一般符合人们的思维模式，但是缺点就是

1、递归由于是函数调用自身，而函数调用是有时间和空间的消耗的
2、递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算
3、调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。

针对于上面三点，尾递归就出现了

尾递归

尾递归是指递归调用是函数的最后一个语句，而且其结果被直接返回。由于递归结果总是直接返回，尾递归比较方便转换为循环，因此编译器容易对它进行优化。
针对上面的斐波那契改成尾递归

def fib(n: Int): Int = {
  @tailrec
  def _loop(n: Int, acc1: Int, acc2: Int): Int =
    if(n <= 2)
      acc2
     else
       _loop(n-1, acc2, acc1+acc2)

   _loop(n, 1, 1)
}

尾递归版本最重要的就是找到合适的累加器，该累加器可以保留最后一次递归调用留在堆栈中的数据，积累之前调用的结果，这样堆栈数据就可以被丢弃，当前的函数栈可以被重复利用。
在这个例子中，变量acc就是累加器，每次递归调用都会更新该变量，直到递归边界条件满足时返回该值。
对于尾递归，Scala语言特别增加了一个注释@tailrec，该注释可以确保程序员写出的程序是正确的尾递归程序，如果由于疏忽大意，写出的不是一个尾递归程序，则编译器会报告一个编译错误，提醒程序员修改自己的代码。

局限

由于JVM的限制，对尾递归深层次的优化比较困难，因此，Scala对尾递归的优化很有限，它只能优化形式上非常严格的尾递归。也就是说，下列情况不在优化之列。

如果尾递归不是直接调用，而是通过函数值。
比如以上阶乘的尾递归版本，如果我们改写为不是直接调用它，而是将函数赋值给func，编译器将不会认为它是尾递归。

//call function value will not be optimized
val func = factorialTailrec _
def factorialTailrec(n: BigInt, acc: BigInt): BigInt = {
     if(n <= 1) acc
     else func(n-1, acc*n)
}

间接递归不会被优化
间接递归，指不是直接调用自身，而是通过其他的函数最终调用自身的递归。如下所示。

//indirect recursion will not be optimized
def foo(n: Int) : Int = {
    if(n == 0) 0;
    bar(n)
}
def bar(n: Int) : Int = {
    foo(n-1)
}

参考资料