递归与尾递归 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、尾递归

    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的时候，我们通过断点可以得到下面的界面：

 

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

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方法，我么会得到

从上面的执行结果来看，我们可以看到每次执行并不会创建新的栈帧，而是复用了之前的栈帧。

我们将这个方法用java实现会发现：