前言
本篇介紹的不是什么新知識，而是對前面講解的一些知識的綜合運用。眾所周知，遞歸是解決復雜問題的一個很有效的方式，也是函數式語言的核心，在一些函數式語言中，是沒有迭代與while這種概念的，因為此類的循環通通可以用遞歸來實現，這類語言的編譯器都對遞歸的尾遞歸形式進行了優化，而Java的編譯器并沒有這樣的優化，本篇就要完成這樣一個對于尾遞歸的優化。
什么是尾遞歸
本篇將使用遞歸中最簡單的階乘計算來作為例子
遞歸實現
|
1
2
3
4
5
6
7
8
9
10
|
/*** 階乘計算 -- 遞歸解決** @param number 當前階乘需要計算的數值* @return number!*/public static int factorialRecursion(final int number) {if (number == 1) return number;else return number * factorialRecursion(number - 1);} |
這種方法計算階乘比較大的數很容易就棧溢出了，原因是每次調用下一輪遞歸的時候在棧中都需要保存之前的變量，所以整個棧結構類似是這樣的
5
4
3
2
1
------------------->
棧的深度
在沒有遞歸到底之前，那些中間變量會一直保存著，因此每一次遞歸都需要開辟一個新的棧空間
尾遞歸實現
任何遞歸的尾遞歸版本都十分簡單，分析上面棧溢出的原因就是在每次return的時候都會附帶一個變量，因此只需要在return的時候不附帶這個變量即可。說起來簡單，該怎么做呢?其實也很容易，我們使用一個參數來保存上一輪遞歸的結果，這樣就可以了，因此尾遞歸的階乘實現應該是這樣的代碼。
|
1
2
3
4
5
6
7
8
9
10
11
|
/*** 階乘計算 -- 尾遞歸解決** @param factorial 上一輪遞歸保存的值* @param number 當前階乘需要計算的數值* @return number!*/public static int factorialTailRecursion(final int factorial, final int number) {if (number == 1) return factorial;else return factorialTailRecursion(factorial * number, number - 1);} |
使用一個factorial變量保存上一輪階乘計算出的數值,這樣return的時候就無需保存變量,整個的計算過程是
(5*4)20 -> (20*3) 60 -> (60*2) 120 -> return 120
這樣子通過每輪遞歸結束后刷新當前的棧空間，復用了棧，就克服了遞歸的棧溢出問題，像這樣的return后面不附帶任何變量的遞歸寫法，也就是遞歸發生在函數最尾部,我們稱之為'尾遞歸'。
使用lambda實現編譯器的優化
很顯然，如果事情這么簡單的話，這篇文章也就結束了，和lambda也沒啥關系 :) 然而當你調用上文的尾遞歸寫法之后，發現并沒有什么作用，該棧溢出的還是會棧溢出，其實原因我在開頭就已經說了，尾遞歸這樣的寫法本身并不會有什么用，依賴的是編譯器對尾遞歸寫法的優化，在很多語言中編譯器都對尾遞歸有優化，然而這些語言中并不包括java，因此在這里我們使用lambda的懶加載(惰性求值)機制來延遲遞歸的調用，從而實現棧幀的復用。
設計尾遞歸的接口
因此我們需要設計一個這樣的函數接口來代替遞歸中的棧幀，通過apply這個函數方法(取名叫apply是因為該方法的參數是一個棧幀，返回值也是一個棧幀,類比function接口的apply)完成每個棧幀之間的連接，除此之外，我們棧幀還需要定義幾個方法來豐富這個尾遞歸的接口。
apply（連接棧幀，惰性求值）
判斷遞歸是否結束
得到遞歸最后的結果
執行遞歸(及早求值)
根據上面的幾條定義,設計出如下的尾遞歸接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
/** * 尾遞歸函數接口 * @author : martrix */@FunctionalInterfacepublic interface TailRecursion<T> { /** * 用于遞歸棧幀之間的連接,惰性求值 * @return 下一個遞歸棧幀 */ TailRecursion<T> apply(); /** * 判斷當前遞歸是否結束 * @return 默認為false,因為正常的遞歸過程中都還未結束 */ default boolean isFinished(){ return false; } /** * 獲得遞歸結果,只有在遞歸結束才能調用,這里默認給出異常,通過工具類的重寫來獲得值 * @return 遞歸最終結果 */ default T getResult() { throw new Error("遞歸還沒有結束,調用獲得結果異常!"); } /** * 及早求值,執行者一系列的遞歸,因為棧幀只有一個,所以使用findFirst獲得最終的棧幀,接著調用getResult方法獲得最終遞歸值 * @return 及早求值,獲得最終遞歸結果 */ default T invoke() { return Stream.iterate(this, TailRecursion::apply) .filter(TailRecursion::isFinished) .findFirst() .get() .getResult(); }} |
設計對外統一的尾遞歸包裝類
為了達到可以復用的效果,這里設計一個尾遞歸的包裝類,目的是用于對外統一方法,使得需要尾遞歸的調用同樣的方法即可完成尾遞歸,不需要考慮內部實現細節，因為所有的遞歸方法無非只有2類類型的元素組成,一個是怎樣調用下次遞歸,另外一個是遞歸的終止條件，因此包裝方法
設計為以下兩個
調用下次遞歸
結束本輪遞歸
代碼如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
/** * 使用尾遞歸的類,目的是對外統一方法 * * @author : Matrix */public class TailInvoke { /** * 統一結構的方法,獲得當前遞歸的下一個遞歸 * * @param nextFrame 下一個遞歸 * @param <T> T * @return 下一個遞歸 */ public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) { return nextFrame; } /** * 結束當前遞歸，重寫對應的默認方法的值,完成狀態改為true,設置最終返回結果,設置非法遞歸調用 * * @param value 最終遞歸值 * @param <T> T * @return 一個isFinished狀態true的尾遞歸, 外部通過調用接口的invoke方法及早求值, 啟動遞歸求值。 */ public static <T> TailRecursion<T> done(T value) { return new TailRecursion<T>() { @Override public TailRecursion<T> apply() { throw new Error("遞歸已經結束,非法調用apply方法"); } @Override public boolean isFinished() { return true; } @Override public T getResult() { return value; } }; }} |
完成階乘的尾遞歸函數
通過使用上面的尾遞歸接口與包裝類,只需要調用包裝了call與done就可以很輕易的寫出尾遞歸函數,代碼如下
|
1
2
3
4
5
6
7
8
9
10
11
12
|
/*** 階乘計算 -- 使用尾遞歸接口完成* @param factorial 當前遞歸棧的結果值* @param number 下一個遞歸需要計算的值* @return 尾遞歸接口,調用invoke啟動及早求值獲得結果*/public static TailRecursion<Integer> factorialTailRecursion(final int factorial, final int number) {if (number == 1) return TailInvoke.done(factorial);else return TailInvoke.call(() -> factorialTailRecursion(factorial + number, number - 1));} |
通過觀察發現,和原先預想的尾遞歸方法幾乎一模一樣,只是使用包裝類的call與done方法來表示遞歸的調用與結束
預想的尾遞歸
|
1
2
3
4
5
6
7
8
9
10
11
|
/** * 階乘計算 -- 尾遞歸解決 * * @param factorial 上一輪遞歸保存的值 * @param number 當前階乘需要計算的數值 * @return number! */ public static int factorialTailRecursion(final int factorial, final int number) { if (number == 1) return factorial; else return factorialTailRecursion(factorial * number, number - 1); } |
測試尾遞歸函數
這里作一個說明,因為階乘的計算如果要計算到棧溢出一般情況下Java的數據類型需要使用BigInteger來包裝,為了簡化代碼，這里的測試僅僅是是測試棧會不會溢出的問題,因此我們將操作符的*改成+這樣修改的結果僅僅是結果變小了,但是棧的深度卻沒有改變。測試代碼如下
首先測試 深度為10W的普通遞歸
測試代碼
|
1
2
3
4
|
@Testpublic void testRec() {System.out.println(factorialRecursion(100_000));} |
理所當然的棧溢出了
|
1
2
3
4
5
6
7
|
java.lang.StackOverflowError at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20) at test.Factorial.factorialRecursion(Factorial.java:20)Process finished with exit code -1 |
這里我們測試1000W棧幀的尾遞歸
尾遞歸代碼
|
1
2
3
4
5
6
|
public static TailRecursion<Long> factorialTailRecursion(final long factorial, final long number) {if (number == 1) return TailInvoke.done(factorial);else return TailInvoke.call(() -> factorialTailRecursion(factorial + number, number - 1));} |
測試代碼
|
1
2
3
4
|
@Testpublic void testTailRec() {System.out.println(factorialTailRecursion(1,10_000_000).invoke());} |
發現結果運轉良好
|
1
2
|
50000005000000Process finished with exit code 0 |
由于階乘的計算一般初始值都為1,所以再進一步包裝一下,將初始值設置為1
|
1
2
3
|
public static long factorial(final long number) {return factorialTailRecursion(1, number).invoke();} |
最終調用代碼如下,完全屏蔽了尾遞歸的實現細節
|
1
2
3
4
|
@Testpublic void testTailRec() {System.out.println(factorial(10)); //結果為 3628800} |
總結
本文講解了利用lambda懶加載的特性完成了遞歸中棧幀的復用,實現了函數式語言編譯器的'尾遞歸'優化,雖然上面的例子很簡單，但是設計的接口和包裝類都是通用的，可以說任何需要使用尾遞歸的都可以使用上面的代碼來實現尾遞歸的優化，這也算是為編譯器幫了點忙吧。
以上所述是小編給大家介紹的Java8使用lambda實現Java的尾遞歸，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對服務器之家網站的支持！
原文鏈接：http://www.cnblogs.com/invoker-/p/7723420.html
