Java-递归-爆栈问题

一、递归时出现的错误

现使用单路递归的方法进行n到一的求和，用Java代码实现如下：

//递归求和 n + (n-1) + ... + 1
public class E06Sum {

    public static void main(String[] args) {
        long s = sum(15000);
        System.out.println(s);
    }

    //f(n) = f(n - 1) + 1
    //简单的单路递归
    public static long sum(long n){
        if(n == 1){
            return 1;
        }
        return sum(n-1) + n;
    }
}

当n较小时没有问题可以正常跑，但是当我这里设置n = 15000 的时候报错了，Exception in thread "main" java.lang.StackOverflowError StackOverflowError栈内存耗尽，俗称爆栈。 

二、对错误进行分析

用伪代码来分析错误：

/*
     用伪代码说明以下执行过程：
       long sum(long n = 15000){
        return 15000 + long sum(long n = 14999){
        return 14999 + sum(14998){
        。。。。。。。。。。。。。。
        return 2 + long sum(long n = 1){
           if(n == 1){
            return 1;
           }
         }
       }
    };
  }
     */

其中，若最内层的函数（如下所示）sum(long n = 1)没有完成，其他的函数是不会执行的，只有最内层的函数得到返回值了才能一层一层的向外归，也就是递的过程必须递到最深处才能归。

/*
return 2 + long sum(long n = 1){
           if(n == 1){
            return 1;
           }
         }
*/

每个方法调用时需要消耗一定的内存，因为方法调用时需要存储方法相关的信息比如方法的参数信息，局部变量的信息，方法的返回地址等信息，这些信息都要储存到栈内存中。最内层sum(n = 1)这个方法没有结束之前，前面的14999个sum方法都要等待，它们占用的内存也不能得到释放，只有当方法执行完毕时这个方法占用的内存才能释放，故我们占用得内存是一点一点释放的。

所以我们刚刚出现StackOverflowError栈内存耗尽 这个错误是因为方法调用得太多了，层级太深，导致栈内存耗尽。

三、爆栈问题解决方法

1.尾调用的概念

如果函数的最后一步是调用一个函数，那么就称为尾调用，例如：

function a(){
	return b();//函数a的最后一步是调用函数b
}

下面三段代码不能称之为尾调用：

• 最后一步并虽然调用了函数，但是又进行了运算：

function a(){
	return b() + 1;
}

• 最后一步并非调用函数:

function a(){
  const c = b();
	return c;
}

• 最后一步虽然调用了函数，但又用到了外层函数的变量x:

function a(x){
	return b() + x;
}

2.尾调用的用途

一些语言的编译器能够对尾调用做优化，例如：

没优化之前的代码：

//有以下三个函数a\b\c

//函数a尾调用了函数b
function a(){
  //前面的处理
	return b();
}
//函数b尾调用了函数c
function b(){
  //前面的处理
	return c();
}

function c(){
	return 1000;
}
//首先调用函数a
a();

当我们先调用函数a时的过程的伪代码：

function a(){
	return function b(){
  	return function c(){
    	return 1000;
    }
  }
}

可以看到，这种执行的过程是一种嵌套的关系。当函数c没有执行完之前，a、b都要等待c执行完，故c执行完之前a、b所占的内存并不能得到释放。

优化之后的代码：

a();
b();
c();

优化后的代码执行过程就从嵌套的关系变成一种平级的调用关系，内存也能够得到及时地释放。这就是某一些编译器能够对尾调用进行的优化。那么具体优化方法就是，例如在a函数前面的处理执行完了之后我们就不需要用到a了，就将a占用的内存释放释放，因为最后a的结果是由调用b来提供的，b函数也同理。这也是为什么尾调用才可以做这种优化的原因，若不是尾调用，例如最后的操作是 return b() + 1; 那么我们要先得到b返回的值，再进行运算，最后才能得到a的结果，所以此时无法将a释放，这种情况就不能做尾调用的优化了。

3.尾调用的一种特殊情况-尾递归

尾递归指的是函数最后调用的函数是他本身：

function a(){
	//前面的处理
  return a();
}

能对尾调用做优化的编译器肯定能对尾递归做优化。

4.什么语言能够对尾调用做优化

• c++
• scala

这里以scala为例来讲尾调用的优化，scala是Java的近亲，也是编译处理啊class类然后再JVM上运行，但是语法有些不同。scala可以使用java中的类，所以可以混用两种语言进行开发。

用scala进行n到1的求和：

object Main{

  def main(args: Array[String]): Unit = {
    println(sum(15000))
  }
  
  def sum(n: Long) : Long = {
		if(n == 1){
    	return 1
    }
    return n + sum(n - 1)//最后一步不是尾递归
  }
  
}

现在运行出来仍然是报栈内存溢出错误，因为注意看我们上面的代码，最后我们没有进行尾递归，因此scala的编译器没法进行优化，但是Scala给我们提供了一个注解，可以检查我们函数是不是用了尾递归这种写法。

@tailrec//tailrec就是尾递归的意思

该写代码，使用尾调用：

object Main{

  def main(args: Array[String]): Unit = {
    println(sum(15000,accumulator = 0))
  }
  
  @tailrec
  def sum(n: Long , accumulator : Long) : Long = {
		if(n == 1){
    	return 1 + accumulatior
    }
    return sum(n - 1, n + accumulator)//写一个参数计数器，把加法提前做。
  }
  
}

运行时候爆栈问题得到解决。

以n = 3为例，用伪代码来解释一下运行过程：

/*
sum (n = 3, accumulator = 0): Long = {
	return sum(2,3)//这时我们已经不需要用到外层的函数了，故外层函数的内存可以及时释放了。
}

sum (n = 2, accumulator = 3): Long = {
	return sum(1,5)//这时我们已经不需要用到外层的函数了，故外层函数的内存可以及时释放了。
}

sum (n = 1, accumulator = 5): Long = {
	if(n == 1){
    	return 1 + accumulatior//最终得到6
    }
}

*/

但是尾递归的优化限制比较大，不是所有语言都支持，所以我们的爆栈问题从根本上是不能由尾递归解决的，最终的解决方法是将代码改为循环的代码。

四、用循环解决爆栈问题

将递归代码改成循环代码，用循环来进行n到1的加法：

public class Sum {

    public static void main(String[] args) {
        long n = 100000000;
        long sum = 0;//设置一个变量用来存储最终的值
        for(long i = n; i >= 1; i--){
            sum += i;
        }
        System.out.println(sum);
    }
}

这样子就可以运行出来不出错，理论上所有的递归代码都可以改成循环代码，但是有些时候改起来不是那么容易。