Java递归优化_java 递归优化

一、经典递归

（注：本文例子只用于探讨，不考虑n<=0 等复杂情况。）

int factorial(int n){
    if(n==1){
        return 1;
    }else{
        return n*factorial(n-1);
    }
}
1
2
3
4
5
6
7

执行过程如下：

factorial（1）= 1
factorial（2）= 2*factorial（1）= 2*1 = 2
factorial（3）= 3*factorial（2）= 3*2 = 6
factorial（4）= 4*factorial（3）= 4*6 = 24
……
1
2
3
4
5

结论：这种递归方式实际是利用了大量的栈帧（每个栈帧都是一次函数计算），存放中间值，直到完成递归（递归必须保证有终止条件哦）。由于使用大量栈帧，因此空间消耗是比较大的。

二、尾递归优化

int factorial(int n，int result){
    if(n==1){
        return result;
    }else{
        return factorial(n-1,n*result);
    }
}
1
2
3
4
5
6
7

执行过程如下：

factorial（4,1）
= factorial（3,4*1）
= factorial（2,3*4*1）
= factorial（1,2*3*4*1）
= factorial（1,24）
= 24
1
2
3
4
5
6

结论：这种递归方式一般称为尾递归，实际只使用了一个栈帧，不停的进行返回值的计算，直到完成递归（递归必须保证有终止条件哦）。尾递归的好处是，复用了栈帧，空间消耗相对较小。