摘要:前言一般地對于語言而言普通的遞歸調用是在虛擬機棧上完成的假如是一個遞歸方法那么在其內部再調用自己的時候假設為那么方法變量表將創建在方法棧幀之上從而形成了一個新的棧幀因此容易發現在遞歸思想中遞歸簡化了問題的表達但犧牲了虛擬機棧中的內存空間普通
前言
一般地,對于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);
}
}
總體而言參數的書寫分為兩部分
前部分為計數,后部分為計算,例如計算階乘時候只需要兩個參數,第一個計數,第二個存結果.
尾遞歸將全部信息放入了參數里,因此也就巧妙地避免了需要上一棧幀保存信息.
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/109066.html
摘要:尾遞歸優化一般遞歸與尾遞歸一般遞歸執行可以看到一般遞歸每一級遞歸都產生了新的局部變量必須創建新的調用棧隨著遞歸深度的增加創建的棧越來越多造成爆棧尾遞歸尾遞歸基于函數的尾調用每一級調用直接返回遞歸函數更新調用棧沒有新局部變量的產生類似迭代的 Python尾遞歸優化 一般遞歸與尾遞歸 一般遞歸: def normal_recursion(n): if n == 1: ...
摘要:根據該規則,返回第個斐波那契數。尾遞歸函數調用自身,稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事 斐波那契數列是以下一系列數字: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...
閱讀 1865·2021-10-09 09:44
閱讀 3395·2021-09-28 09:35
閱讀 1385·2021-09-01 10:31
閱讀 1675·2019-08-30 15:55
閱讀 2716·2019-08-30 15:54
閱讀 939·2019-08-29 17:07
閱讀 1385·2019-08-29 15:04
閱讀 2012·2019-08-26 13:56