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