前言
一般地,對(duì)于java語(yǔ)言而言,普通的遞歸調(diào)用是在java虛擬機(jī)棧上完成的.加入a()是一個(gè)遞歸方法,那么在其內(nèi)部再調(diào)用自己的時(shí)候,假設(shè)為a1(),那么a1()這個(gè)方法變量表將創(chuàng)建在a()方法棧幀之上,從而形成了一個(gè)新的棧幀.因此容易發(fā)現(xiàn),在遞歸思想中,遞歸簡(jiǎn)化了問(wèn)題的表達(dá),但犧牲了虛擬機(jī)棧中的內(nèi)存空間.
普通遞歸
斐波那契遞歸法
public static int fib(int num){
if(num<2)
return num;
else
return fib(num-2)+fib(num-1);
}
- 對(duì)于上面的解法,很容易就會(huì)發(fā)現(xiàn),不但屬于普通遞歸,而且在計(jì)算fib(num-1)是重復(fù)了fib(num-2)的計(jì)算量,因此代碼效率大打折扣.因此效率較高的寫(xiě)法可以用for循環(huán)計(jì)算,
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;
}
}
斐波那契尾遞歸優(yōu)化
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);
}
}
性能對(duì)比
public static void main(String[] args) {
long time = new Date().getTime();
int num=40;
System.out.println(fib(num));
System.out.println("普通遞歸調(diào)用用時(shí):" + (new Date().getTime() - time) + "毫秒");
time = new Date().getTime();
System.out.println(fib2(num, 0, 1));
System.out.println("尾遞歸優(yōu)化調(diào)用用時(shí):" + (new Date().getTime() - time) + "毫秒");
time = new Date().getTime();
System.out.println(fib3(num));
System.out.println("for循環(huán)法調(diào)用用時(shí):" + (new Date().getTime() - time) + "毫秒");
}
//輸出
/*
102334155
普通遞歸調(diào)用用時(shí):674毫秒
102334155
尾遞歸優(yōu)化調(diào)用用時(shí):0毫秒
102334155
for循環(huán)法調(diào)用用時(shí):0毫秒
*/
- 可以看出有明顯差異,即使普通遞歸法計(jì)算量多了一半,時(shí)間除以2也是387毫秒,這也遠(yuǎn)遠(yuǎn)高于for循環(huán)和遞歸尾優(yōu)化法.
尾遞歸優(yōu)化思想
- 即遞歸方法return 直接返回方法,注意是直接返回方法,不能是方法加1個(gè)值等形式.這樣在遞歸調(diào)用時(shí),新方法會(huì)覆蓋當(dāng)前棧幀,達(dá)到節(jié)省椪虿荩空間的目的.因此也就不會(huì)有遞歸調(diào)用產(chǎn)生的棧溢出問(wèn)題.
尾遞歸寫(xiě)法
斐波那契例:
//count作為計(jì)數(shù),表示遞歸層次,
//pre代表前一個(gè)值
//result 表示當(dāng)前值
public static int fib2(int count, int pre, int result) {
//層次減到1時(shí)返回計(jì)算結(jié)果
if (count == 1)
return result;
else{
//遞歸調(diào)用時(shí),層次減1,前一項(xiàng)更新為當(dāng)前項(xiàng),所以填result,第三個(gè)參數(shù)即實(shí)現(xiàn)了倒數(shù)第二個(gè)參數(shù)加倒數(shù)第一個(gè)參數(shù).
return fib2(--count, result, result + pre);
}
}
- 總體而言參數(shù)的書(shū)寫(xiě)分為兩部分
- 前部分為計(jì)數(shù),后部分為計(jì)算,例如計(jì)算階乘時(shí)候只需要兩個(gè)參數(shù),第一個(gè)計(jì)數(shù),第二個(gè)存結(jié)果.
- 尾遞歸將全部信息放入了參數(shù)里,因此也就巧妙地避免了需要上一棧幀保存信息.
