尾递归优化

今天在看设计模式时提到了尾递归优化,于是去网上搜索了一下,又重新让我认识了递归的另一种方式,由此记录下来.

之前写过一些算法题,相信大部分人在做算法题时都会避开用递归,为什么呢,因为递归的调用会让上一层的方法信息,和一些参数都保存在堆栈中,于是乎如果层数太多,堆栈就会溢出,抛出StackOverflowError这个异常,因为java虚拟机在运行方法时会给每个方法分配一个堆栈空间,方法过多,剩余空间不够了就会抛那个异常;但是尾递归就不太可能会有这个问题,先看一下代码

拿斐波那契数列举例,普通的递归会这么写:

    public static long recu(int n){
        if (n < 2){
            return n;
        }else {
            return recu(n-1)+recu(n-2);
        }
    }

可以看出方法内部的return会不断保留上一层方法的信息

再看一下尾递归:

    public static long tailRe(int n, long a, long b){
        if (n == 0){
            return a;
        }else {
            return tailRe(n-1, b,a+b);
        }
    }

尾递归在返回时不会积累上层方法的信息,因为在调用下一层方法时上层方法已经不起作用了,所以可以直接把上层方法去除掉,节省堆栈空间

比较一下结果:

尾递归