為了賬號安全,請及時綁定郵箱和手機立即綁定

深度遞歸必須知道的尾調用(Lambda)

2019.09.08 12:36 9316瀏覽

本文從一個遞歸棧溢出說起,像大家介紹一下如何使用尾調用解決這個問題,以及尾調用的原理,最后還提供一個解決方案的工具類,大家可以在工作中放心用起來。

現在我們有個需求,需要計算任意值階乘的結果,階乘我們用 n!表示,它的計算公式是:n! = 123*……(n-1)n,比如說 3 的階乘就是 12*3。

對于這個問題,我們首先想到的應該就是遞歸,我們立馬寫了一個簡單的遞歸代碼:

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

遞歸代碼很簡單,我們寫了一個簡單的測試,如下:

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

運行結果很快就出來了,結果為:3628800,是正確的。

因為需求是能夠計算任意值,接著我們把 10 換成 9000,來計算一下 9000 的階乘,可這時卻突然報錯了,報錯的信息如下:
圖片描述
StackOverflowError 是棧溢出的異常,jvm 給棧分配的大小是固定的,方法本身的定義、入參、方法里的局部變量這些都會占內存,隨著遞歸不斷進行,遞歸的方法就會越來越多,每個方法都能從棧中得到內存,漸漸的,棧的內存就不夠了,報了這個異常。

我們首先想到的辦法是如何讓棧的內存大一點呢?JVM 有個參數叫做 -Xss,這個參數就規定了要分配給棧多少大小的內存,于是我們在 idea 里面配置一下 Xss 的參數,配置如下:
圖片描述
圖中我們給棧分配 200k 大小內存,再次運行仍然報錯,說明我們分配的棧還是太小了,于是我們修改 Xss 值到 100M 試一下,配置如下:
圖片描述
再次運行,成功了,運行結果如下:
圖片描述
雖然通過修改棧的大小暫時解決了這個問題,但這種解決方案在線上是完全行不通的,主要問題如下:

  1. 我們不可能修改線上棧的大小,一般來說,線上棧的大小一般都是 256k,不可能為了一個遞歸程序把棧大小修改成很大。

  2. 因為我們需要計算任意值的階乘,所以棧的大小是動態的,即使我們修改成 100m 的話,也難以保證遞歸時一定不會超出棧的深度。

那該怎么辦呢,有木有其他辦法可以解決這個問題呢?在想其他辦法之前,我們先思考下問題的根源在那里。

每次遞歸時,棧都會給遞歸的方法分配內存,遞歸深度越深,方法就會越多,內存分配就會越多,而且遞歸執行的時候,是遞歸到最后一層的時候,遞歸才會真正執行,也就是說在沒有遞歸到最后一層時,所有被分配的遞歸方法都無法執行,所有棧內存也都無法被釋放,這樣就導致棧的內存很快被消耗完,我們畫一個圖簡單釋義一下:
圖片描述
我們知道了問題根源后,突然發現有一種技術很適合解決這種問題:尾調用。

尾調用

尾調用主要是用來解決遞歸時,棧溢出的問題,不需要任何改造,只需要在代碼的最后一行返回無任何計算的遞歸代碼,編譯器就會自動進行優化,比如之前寫的遞歸代碼,我們修改成如下即可:

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);//在方法的最后直接返回,叫做尾調用
}

上面代碼方法的最后一行直接返回遞歸的代碼,并且沒有任何計算邏輯,這樣子編譯器會自動識別,并解決棧溢出的問題。

但 Java 是不支持的,只有 C 語言才支持!!!

但我們立馬又想到了 Java 8 中的新技術可以解決這個問題:Lambda。

尾調用的 Lambda 實現

首先我們必須先介紹一下 Lambda 的特性,Lambda 的方法分為兩種,懶方法和急方法,網上通俗的說明是懶方法是不會執行的,只有急方法才會執行,本文用到的特性就是懶方法不執行,懶方法不執行的潛在含義是:方法只是申明出來了,棧不會給方法分配內存,如果用到遞歸上,那么不管遞歸多少次,棧只會給每個遞歸遞歸分配一個 Lambda 包裝的遞歸方法聲明變量而已,并不會給遞歸方法分配內存。

我們畫一張圖釋義一下:
圖片描述

接著我們代碼實現以下:

  1. 首先我們實現了一個尾調用的接口,方便大家使用:
// 尾調用的接口,定義了是否完成,執行等方法
public interface TailRecursion<T> {

  TailRecursion<T> apply();

  default Boolean isComplete() {
    return Boolean.FALSE;
  }

  default T getResult() {
    throw new RuntimeException("遞歸還沒有結束,暫時得不到結果");
  }

  default T invoke() {
    return Stream.iterate(this, TailRecursion::apply)
        .filter(TailRecursion::isComplete)
        .findFirst()
        .get()//執行急方法
        .getResult();
  }
}
  1. 接著實現了利用這個接口實現 9k 的階乘,代碼如下:
public class TestDTO {
  private Long begin;
  private Long end;
  private BigDecimal total;
}
public static TailRecursion<BigDecimal> recursion1(TestDTO testDTO) {
  // 如果已經遞歸到最后一個數字了,結束遞歸,返回 testDTO.getTotal() 值
  if (testDTO.getBegin().equals(testDTO.getEnd())) {
  return TailRecursionCall.done(testDTO.getTotal());
  }
  testDTO.setBegin(1+testDTO.getBegin());
  // 計算本次遞歸的值
  testDTO.setTotal(testDTO.getTotal().multiply(new BigDecimal(testDTO.getBegin())));
  // 這里是最大的不同,這里每次調用遞歸方法時,使用的是 Lambda 的方式,這樣只是初始化了一個 Lambda 變量而已,recursion1 方法的內存是不會分配的
  return TailRecursionCall.call(()->recursion1(testDTO));
}
  1. 最后我們寫了一個測試方法,我們把棧的大小設定成 200k,測試代碼如下:
public void testRecursion1(){
  TestDTO testDTO = new TestDTO();
  testDTO.setBegin(1L);
  testDTO.setEnd(9000L);
  testDTO.setTotal(BigDecimal.ONE);
  log.info("計算 9k 的階乘,結果為{}",recursion1(testDTO).invoke());
}

最終運行的結果如下:
圖片描述
從運行結果可以看出,雖然棧的大小只有 200k,但利用 Lambda 懶加載的特性,卻能輕松的執行 9000 次遞歸。

我們寫遞歸的時候,最擔心的就是遞歸深度過深,導致棧溢出,而使用 Lambda 尾調用的機制卻可以完美解決這個問題,所以趕緊用起來吧。
歡迎關注我的新課:《面試官系統精講Java源碼及大廠真題》,和我一起學習源碼、練習場景,應對面試題吧。

點擊查看更多內容

本文原創發布于慕課網 ,轉載請注明出處,謝謝合作

9人點贊

若覺得本文不錯,就分享一下吧!

評論

相關文章推薦

正在加載中
意見反饋 幫助中心 APP下載
官方微信

舉報

0/150
提交
取消
TLC官网 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>