深度遞歸的尾調(diào)用(Lambda)-魔扣目錄

引導(dǎo)語(yǔ)

本文從一個(gè)遞歸棧溢出說(shuō)起，像大家介紹一下如何使用尾調(diào)用解決這個(gè)問(wèn)題，以及尾調(diào)用的原理，最后還提供一個(gè)解決方案的工具類，大家可以在工作中放心用起來(lái)。

遞歸-發(fā)現(xiàn)棧溢出

現(xiàn)在我們有個(gè)需求，需要計(jì)算任意值階乘的結(jié)果，階乘我們用 n！表示，它的計(jì)算公式是：n! = 123……(n-1)n，比如說(shuō) 3 的階乘就是 123。

對(duì)于這個(gè)問(wèn)題，我們首先想到的應(yīng)該就是遞歸，我們立馬寫了一個(gè)簡(jiǎn)單的遞歸代碼：

// 階乘計(jì)算
public static String recursion(long begin, long end, BigDecimal total) {
 // begin 每次計(jì)算時(shí)都會(huì)遞增，當(dāng) begin 和 end 相等時(shí)，計(jì)算結(jié)束，返回最終值
 if (begin == end) {
 return total.toString();
 }
 // recursion 第三個(gè)參數(shù)表示當(dāng)前階乘的結(jié)果
 return recursion(++begin, end, total.multiply(new BigDecimal(begin)));
}

遞歸代碼很簡(jiǎn)單，我們寫了一個(gè)簡(jiǎn)單的測(cè)試，如下：

 @Test
 public void testRecursion() {
 log.info("計(jì)算 10 的階乘，結(jié)果為{}",recursion(1, 10, BigDecimal.ONE));
 }

運(yùn)行結(jié)果很快就出來(lái)了，結(jié)果為：3628800，是正確的。

因?yàn)樾枨笫悄軌蛴?jì)算任意值，接著我們把 10 換成 9000，來(lái)計(jì)算一下 9000 的階乘，可這時(shí)卻突然報(bào)錯(cuò)了，報(bào)錯(cuò)的信息如下：

StackOverflowError 是棧溢出的異常，jvm 給棧分配的大小是固定的，方法本身的定義、入?yún)ⅰ⒎椒ɡ锏木植孔兞窟@些都會(huì)占內(nèi)存，隨著遞歸不斷進(jìn)行，遞歸的方法就會(huì)越來(lái)越多，每個(gè)方法都能從棧中得到內(nèi)存，漸漸的，棧的內(nèi)存就不夠了，報(bào)了這個(gè)異常。

我們首先想到的辦法是如何讓棧的內(nèi)存大一點(diǎn)呢？JVM 有個(gè)參數(shù)叫做 -Xss，這個(gè)參數(shù)就規(guī)定了要分配給棧多少大小的內(nèi)存，于是我們?cè)?idea 里面配置一下 Xss 的參數(shù)，配置如下：

圖中我們給棧分配 200k 大小內(nèi)存，再次運(yùn)行仍然報(bào)錯(cuò)，說(shuō)明我們分配的棧還是太小了，于是我們修改 Xss 值到 100M 試一下，配置如下：

再次運(yùn)行，成功了，運(yùn)行結(jié)果如下：

雖然通過(guò)修改棧的大小暫時(shí)解決了這個(gè)問(wèn)題，但這種解決方案在線上是完全行不通的，主要問(wèn)題如下：

我們不可能修改線上棧的大小，一般來(lái)說(shuō)，線上棧的大小一般都是 256k，不可能為了一個(gè)遞歸程序把棧大小修改成很大。
因?yàn)槲覀冃枰?jì)算任意值的階乘，所以棧的大小是動(dòng)態(tài)的，即使我們修改成 100m 的話，也難以保證遞歸時(shí)一定不會(huì)超出棧的深度。

那該怎么辦呢，有木有其他辦法可以解決這個(gè)問(wèn)題呢？在想其他辦法之前，我們先思考下問(wèn)題的根源在那里。

每次遞歸時(shí)，棧都會(huì)給遞歸的方法分配內(nèi)存，遞歸深度越深，方法就會(huì)越多，內(nèi)存分配就會(huì)越多，而且遞歸執(zhí)行的時(shí)候，是遞歸到最后一層的時(shí)候，遞歸才會(huì)真正執(zhí)行，也就是說(shuō)在沒(méi)有遞歸到最后一層時(shí)，所有被分配的遞歸方法都無(wú)法執(zhí)行，所有棧內(nèi)存也都無(wú)法被釋放，這樣就導(dǎo)致棧的內(nèi)存很快被消耗完，我們畫一個(gè)圖簡(jiǎn)單釋義一下：

我們知道了問(wèn)題根源后，突然發(fā)現(xiàn)有一種技術(shù)很適合解決這種問(wèn)題：尾調(diào)用。

尾調(diào)用

尾調(diào)用主要是用來(lái)解決遞歸時(shí)，棧溢出的問(wèn)題，不需要任何改造，只需要在代碼的最后一行返回?zé)o任何計(jì)算的遞歸代碼，編譯器就會(huì)自動(dòng)進(jìn)行優(yōu)化，比如之前寫的遞歸代碼，我們修改成如下即可：

public static BigDecimal recursion1(long begin, long end, BigDecimal total) {
 if (begin == end) {
 return total;
 }
 ++begin;
 total = total.multiply(new BigDecimal(begin));
 return recursion1(begin, end, total);//在方法的最后直接返回，叫做尾調(diào)用
}

上面代碼方法的最后一行直接返回遞歸的代碼，并且沒(méi)有任何計(jì)算邏輯，這樣子編譯器會(huì)自動(dòng)識(shí)別，并解決棧溢出的問(wèn)題。

但 JAVA 是不支持的，只有 C 語(yǔ)言才支持！！！

但我們立馬又想到了 Java 8 中的新技術(shù)可以解決這個(gè)問(wèn)題：Lambda。

尾調(diào)用的 Lambda 實(shí)現(xiàn)

首先我們必須先介紹一下 Lambda 的特性，Lambda 的方法分為兩種，懶方法和急方法，網(wǎng)上通俗的說(shuō)明是懶方法是不會(huì)執(zhí)行的，只有急方法才會(huì)執(zhí)行，本文用到的特性就是懶方法不執(zhí)行，懶方法不執(zhí)行的潛在含義是：方法只是申明出來(lái)了，棧不會(huì)給方法分配內(nèi)存，如果用到遞歸上，那么不管遞歸多少次，棧只會(huì)給每個(gè)遞歸遞歸分配一個(gè) Lambda 包裝的遞歸方法聲明變量而已，并不會(huì)給遞歸方法分配內(nèi)存。

我們畫一張圖釋義一下：

接著我們代碼實(shí)現(xiàn)以下：

首先我們實(shí)現(xiàn)了一個(gè)尾調(diào)用的接口，方便大家使用：

// 尾調(diào)用的接口，定義了是否完成，執(zhí)行等方法
public interface TailRecursion<T> {
 TailRecursion<T> Apply();
 default Boolean isComplete() {
 return Boolean.FALSE;
 }
 default T getResult() {
 throw new RuntimeException("遞歸還沒(méi)有結(jié)束，暫時(shí)得不到結(jié)果");
 }
 default T invoke() {
 return Stream.iterate(this, TailRecursion::apply)
 .filter(TailRecursion::isComplete)
 .findFirst()
 .get()//執(zhí)行急方法
 .getResult();
 }
}

接著實(shí)現(xiàn)了利用這個(gè)接口實(shí)現(xiàn) 9k 的階乘，代碼如下：

public class TestDTO {
 private Long begin;
 private Long end;
 private BigDecimal total;
}
public static TailRecursion<BigDecimal> recursion1(TestDTO testDTO) {
 // 如果已經(jīng)遞歸到最后一個(gè)數(shù)字了，結(jié)束遞歸，返回 testDTO.getTotal() 值
 if (testDTO.getBegin().equals(testDTO.getEnd())) {
 return TailRecursionCall.done(testDTO.getTotal());
 }
 testDTO.setBegin(1+testDTO.getBegin());
 // 計(jì)算本次遞歸的值
 testDTO.setTotal(testDTO.getTotal().multiply(new BigDecimal(testDTO.getBegin())));
 // 這里是最大的不同，這里每次調(diào)用遞歸方法時(shí)，使用的是 Lambda 的方式，這樣只是初始化了一個(gè) Lambda 變量而已，recursion1 方法的內(nèi)存是不會(huì)分配的
 return TailRecursionCall.call(()->recursion1(testDTO));
}

最后我們寫了一個(gè)測(cè)試方法，我們把棧的大小設(shè)定成 200k，測(cè)試代碼如下：

public void testRecursion1(){
 TestDTO testDTO = new TestDTO();
 testDTO.setBegin(1L);
 testDTO.setEnd(9000L);
 testDTO.setTotal(BigDecimal.ONE);
 log.info("計(jì)算 9k 的階乘，結(jié)果為{}",recursion1(testDTO).invoke());
}

最終運(yùn)行的結(jié)果如下：