递归的缺点

递归函数用栈来储存函数的运行状态，函数在进行一层层递归的同时，也在一层层压栈（入栈），当该函数返回时才会出栈。由于栈的储存空间是有限的，当调用的层数过多时，栈就会爆掉（溢出），从而函数也不能成功运行。

尾递归

递归的本质是某个方法调用了自身，每次调用将问题变小，直到能够直接解决
尾递归 是递归中的一种特殊形式，其要求为：某个方法调用自身这件事，一定是该方法做的最后一件事

当有需要返回值的时候会是return f(n)，没有返回的话就直接是f(n)了

return f(n)外不能加其他东西，否则就不是最后一件事了
比如有返回值的，你不能乘个常数n 如 return n*f(n)；甚至是 f(n)+f(n-1)

object test {
def main(args: Array[String]): Unit = {
 //递归形式
 def fact(n: Int): Int = {
   if (n == 0) return 1
   fact(n - 1) * n
 }
 //尾递归形式
 def tailFact(n: Int): Int = {
   def loop(n: Int, currRes: Int): Int = {
     if (n == 0) return 1
     loop(n - 1, currRes * n)
   }
   loop(n, 1)
 }
}
}

尾递归的局限

在Scala中使用尾递归是比较受限的，因为用JVM指令集实现更高级形式的尾递归非常困难。Scala只能对那些直接尾递归调用自己的函数做优化。如果递归调用是间接的，Scala便没法优化；如果最后一步调用的是一个函数值（而不是发起调用的那个函数自己），也无法享受到尾递归优化。

object test {
  def main(args: Array[String]): Unit = {
    //间接调用
    def isEven(n: Int): Boolean = {
      if (n == 0) true
      else isOdd(n - 1)
    }
    def isOdd(n: Int): Boolean = {
      if (n == 0) false
      else isEven(n - 1)
    }
    //最后一步调用的是函数值
    val funValue = nestdFun _
    def nestdFun(x: Int): Unit = {
      if (x != 0) {
        println(x);
        funValue(x - 1)
      }
    }
  }
}

Scala笔记——尾递归

递归的缺点

尾递归

尾递归的局限