尾递归优化

1.什么是递归？

程序调用自身的编程技巧称为递归（ recursion），就好像你做了一个梦，梦里面梦到梦到自己又做了一个梦，梦中梦。下面看一个例子：

public class JavaTest {

    public static int method(int num) {
        if (num > 1)
            return num + method(num - 1);
        else
            return num;
    }

    public static  void main(String[] args){
        int sum =method(100);//从一加到一百的和
        System.out.println(sum);
    }
}

这样递归的话呢，看上去代码很简洁，但是递归是存在缺点的，就是在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。举个栗子，就是打开一扇门，然后又进去了一扇门，等到return的时候，会从里向外一个一个的return，一个一个的出来，所以之前的这些“门”是占要地方的，递归层级过深就会造成堆栈溢出。那么怎么解决这个问题呢？答案就是尾递归优化。

2.什么是尾递归？

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

public class JavaTest {
    public static int method(int num,int sum) {
        if (num > 1) {
            sum += num;
            return method(num - 1,sum);
        }
        else {
            return sum+1;
        }
    }
    public static int method(int num) {
        return method(num,0);
    }
    public static  void main(String[] args){
        int sum =method(100);
        System.out.println(sum);
    }
}

如上，使用了一个变量sum保存了递归调用的结果，并传到下一次递归调用中，这就是尾递归。到递归的结尾的时候，就可以直接return，不需要一层一层的出来。这样的话，就不用保存前面那些函数的堆栈，也就不会堆栈溢出了。

3.编译器的优化

虽然手写成了尾递归的形式，但是编译成字节码的时候，优不优化得看编译器的心情，所以很蛋疼。编译器如果支持尾递归优化，那么就会利用尾递归特点来进行优化，在递归调用的时候重复使用同一个函数栈帧，效率很高，however，java还没有实现尾递归优化的支持，官方是推荐使用循环，迭代，不使用递归。