尾遞迴優化小記
前言
一般地,對於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); } }
- 總體而言引數的書寫分為兩部分
- 前部分為計數,後部分為計算,例如計算階乘時候只需要兩個引數,第一個計數,第二個存結果.
- 尾遞迴將全部資訊放入了引數裡,因此也就巧妙地避免了需要上一棧幀儲存資訊.