前言
一般地, 对于 java 语言而言, 普通的递归调用是在 java 虚拟机栈上完成的. 假如 a() 是一个递归方法, 那么在其内部再调用自己的时候, 假设为 a1(), 那么 a1() 方法变量表将创建在 a() 方法栈帧之上, 从而形成了一个新的栈帧. 因此容易发现, 在递归思想中, 递归简化了问题的表达, 但牺牲了虚拟机栈中的内存空间.
普通递归
斐波那契递归法
public static int fib(int num){
if(num<2)
return num;
else
return fib(num-2)+fib(num-1);
}
对于上面的解法, 很容易就会发现, 不但属于普通递归, 而且在计算 fib(num-1) 是重复了 fib(num-2) 的计算量, 因此代码效率大打折扣. 因此效率较高的写法可以用 for 循环计算,
public static int fib3(int n) {
if (n < 2)
return n;
else {
int pre = 0;
int suf = 1;
for (int i = 2; i <= n; i++) {
int temp = suf;
suf += pre;
pre = temp;
}
return suf;
}
}
斐波那契尾递归优化
public class Main {
public static void main(String[] args) {
System.out.print(fib2(3, 0, 1));
}
public static int fib2(int count, int pre, int result) {
if (count == 1)
return result;
else
return fib2(–count, result, result + pre);
}
}
性能对比
public static void main(String[] args) {
long time = new Date().getTime();
int num=40;
System.out.println(fib(num));
System.out.println(“ 普通递归调用用时:” + (new Date().getTime() – time) + “ 毫秒 ”);
time = new Date().getTime();
System.out.println(fib2(num, 0, 1));
System.out.println(“ 尾递归优化调用用时:” + (new Date().getTime() – time) + “ 毫秒 ”);
time = new Date().getTime();
System.out.println(fib3(num));
System.out.println(“for 循环法调用用时:” + (new Date().getTime() – time) + “ 毫秒 ”);
}
// 输出
/*
102334155
普通递归调用用时:674 毫秒
102334155
尾递归优化调用用时:0 毫秒
102334155
for 循环法调用用时:0 毫秒
*/
可以看出有明显差异, 即使普通递归法计算量多了一半, 时间除以 2 也是 387 毫秒, 这也远远高于 for 循环和递归尾优化法.
尾递归优化思想
即递归方法 return 直接返回方法, 注意是直接返回方法, 不能是方法加 1 个值等形式. 这样在递归调用时, 新方法会覆盖当前栈帧, 达到节省栈空间的目的. 因此也就不会有递归调用产生的栈溢出问题.
尾递归写法
斐波那契例:
//count 作为计数, 表示递归层次,
//pre 代表前一个值
//result 表示当前值
public static int fib2(int count, int pre, int result) {
// 层次减到 1 时返回计算结果
if (count == 1)
return result;
else{
// 递归调用时, 层次减 1, 前一项更新为当前项, 所以填 result, 第三个参数即实现了倒数第二个参数加倒数第一个参数.
return fib2(–count, result, result + pre);
}
}
总体而言参数的书写分为两部分
前部分为计数, 后部分为计算, 例如计算阶乘时候只需要两个参数, 第一个计数, 第二个存结果.
尾递归将全部信息放入了参数里, 因此也就巧妙地避免了需要上一栈帧保存信息.