递归与尾递归 recursive & tail recursive

1、什么是递归

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

或者这么说递归递归是为了细分一个任务，将任务拆解成为一个有规律的，有相同解法的问题

2、递归能解决什么问题

最常见的额一类算法题目就是求斐波那契数列

public static long factorial(long n){

if(n==1){

return 1;

}

return n*factorial(n-1);

}

类似这一类的问题，传统方法很难实现，但是通过递归很容易就能实现结果，但是递归程序有个很严重的问题，就是在程序执行中，递归其实就是不断调用自身，程序每次都会将一些变量和返回地址信息等压入栈中，这样在内存限定的情况下很容易发生内存溢出。还是完成后，还需要释放空间，在效率上也损耗极大。

使用递归是一个非常有效的解决特定问题的途径，但是递归的局限性很让程序员很苦恼，随着程序语言的发展，慢慢的，一种解决递归内存占用的解决方案出现了。那就是尾递归，tail recursive。

3、尾递归

当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，递归结果可以直接返回。编译器在处理尾递归的时候，不会不听的创建栈帧，而是去覆盖之前的栈帧，《算法精解》里面的原话就是："When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack.

将上面的斐波那契数列方法改成尾递归，

public static long factorial(long n,long a){

if(n==1){

return a;

}

return factorial(n-1, n*a);

}

然而如果你认为尾递归就解决这个问题的话，就打错特错了。据了解，老牌程序语言在编译器里，并不支持尾递归的优化，所以即使你在这一类的程序语言里使用了尾递归，也不会得到想要的结果，比如，JAVA，C。等等大佬。

下面的例子让你更直观了解尾递归优化和递归的处理方式，这里我们选择了scala

def main(args: Array[String]): Unit = {
  val result = stackOverFlow(1)
  println(result)
}


/**
  * recursive
  *
  * @param o
  * @return
  */
def stackOverFlow(o: Int): Int = {
  val result = o + 1
  if (result < 100000) stackOverFlow(result)
  result
}

/**
  * tail recursive
  *
  * @param o
  * @return
  */
def tailStack(o: Int): Int = {
  val result = o + 1
  if (result > 100000)
    result
  else
    tailStack(result)

}

这里涉及了两个简单的方法，一个stackOverFlow方法（递归），一个tailStack方法（尾递归），当我们在调用stackOverFlow的时候，我们通过断点可以得到下面的界面：

递归与尾递归 recursive & tail recursive插图

这里我们可以，每次执行，都会记录一次栈帧，最终结果自然是：

Exception in thread "main" java.lang.StackOverflowError
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)

然后我们在运行 tailStack方法，我么会得到

递归与尾递归 recursive & tail recursive插图1