什么是递归
一个函数直接或者间接的调用本身，这就是递归。典型案例斐波那契数列
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)
}
