當前位置：首頁 > 编程语言 > java >内容正文

java

java 递归堆栈_Java中的堆栈安全递归

發布時間：2023/12/3 java 29 豆豆

生活随笔收集整理的這篇文章主要介紹了 java 递归堆栈_Java中的堆栈安全递归小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

java 遞歸堆棧

在本文中，摘自《 Java中的函數編程》一書，我解釋了如何使用遞歸，同時避免了StackOverflow異常的風險。

Corecursion正在使用第一步的輸出作為下一步的輸入來構成計算步驟。遞歸是相同的操作，但是從最后一步開始。在這種情況下，我們必須延遲評估，直到遇到基本條件（與corecursion的第一步相對應）為止。

假設我們的編程語言中只有兩條指令：遞增（向值加1）和遞減（從值中減去1）。讓我們通過編寫這些指令來實現加法。

Corecursive和遞歸加法示例

為了將兩個數字x和y相加，我們可以執行以下操作：

如果y == 0 ，則返回x
否則，遞增x ，遞減y ，然后重新開始。

這可以用Java編寫為：

static int add(int x, int y) {while(y > 0) {x = ++x;y = --y;}return x; }

或更簡單：

static int add(int x, int y) {while(y-- > 0) {x = ++x;}return x; }

注意，直接使用參數x和y沒問題，因為在Java中，所有參數都是按值傳遞的。還要注意，我們使用后減量來簡化編碼。但是，我們可以通過稍微改變條件來使用預減量，從而將形式從y迭代為1到將y?1迭代為0 ：

static int add(int x, int y) {while(--y >= 0) {x = ++x;}return x; }

遞歸版本比較棘手，但仍然非常簡單：

static int addRec(int x, int y) {return y == 0? x: addRec(++x, --y); }

兩種方法似乎都可行，但是如果我們嘗試使用大量的遞歸版本，可能會感到驚訝。雖然

addRec(10000, 3);

生成期望結果10003，切換參數，如下所示：

addRec(3, 10000);

產生一個StackOverflowException 。

如何用Java實現遞歸？

要了解正在發生的事情，我們必須查看Java如何處理方法調用。調用方法時，Java會掛起當前正在執行的操作，并將環境壓入堆棧以為調用的方法執行留出空間。當此方法返回時，Java將彈出堆棧以恢復環境并恢復程序執行。如果我們依次調用一個方法，則堆棧將始終保存這些方法調用環境中的至少一個。

但是方法不僅是通過一個接一個地調用它們而構成的。方法調用方法。如果method1作為其實現的一部分調用method2 ，則Java會再次掛起method1執行，將當前環境壓入stack ，然后開始執行method2 。當method2返回時，Java從堆棧中彈出最后推送的環境并恢復執行（在本例中為method1 ）。 method1完成后，Java再次從堆棧中彈出，并恢復調用該方法之前的操作。

當然，方法調用可能嵌套得很深。方法嵌套深度是否有限制？是。限制是堆棧的大小。在當前情況下，該限制大約在幾千個級別，盡管可以通過配置堆棧大小來增加此限制。但是，所有線程都使用相同的堆棧大小，因此增加單個計算的堆棧大小通常會浪費空間。默認堆棧大小在320k和1024k之間變化，具體取決于Java版本和所使用的系統。對于具有最小堆棧使用率的64位Java 8程序，嵌套方法調用的最大數量約為7000。通常，除了非常特殊的情況外，我們不需要更多的嵌套方法調用。一種這樣的情況是遞歸方法調用。

消除尾調用（TCE）似乎有必要將環境推送到堆棧上，以便在被調用方法返回后繼續進行計算。但不總是。如果對方法的調用是調用方法中的最后一件事，則返回時沒有任何恢復操作，因此可以直接與當前方法的調用者而不是當前方法本身一起恢復。在最后一個位置發生的方法調用（即返回之前的最后一件事）稱為tail call 。避免在尾部調用后將環境壓入堆棧以恢復方法處理是一種稱為尾部調用消除（TCE）的優化技術。不幸的是，Java沒有實現TCE。

消除尾聲有時被稱為尾聲優化（TCO）。 TCE通常是一種優化，我們可能會沒有它。但是，當涉及到遞歸函數調用時，TCE不再是一種優化。這是一項強制性功能。因此，在處理遞歸時，TCE比TCO更好。

尾遞歸方法和功能

大多數功能語言都實現了TCE。但是，TCE不足以使每個遞歸調用成為可能。要成為TCE的候選者，遞歸調用必須是方法必須要做的最后一件事。考慮以下計算列表元素總和的方法：

static Integer sum(List<Integer> list) {return list.isEmpty()? 0: head(list) + sum(tail(list));}

此方法使用head()和tail()方法。請注意，遞歸調用sum方法并不是該方法要做的最后一件事。該方法的最后四件事是：

調用head方法
調用tail方法
調用sum方法
將head的結果和sum的結果sum

即使我們擁有TCE，我們也無法在10,000個元素的列表中使用此方法，因為遞歸被調用方不在尾部位置。但是，可以重寫此方法以便將求和的調用放在尾部位置：

static Integer sum_(List<Integer> list) {return sumTail(list, 0); }static Integer sumTail(List<Integer> list, int acc) {return list.isEmpty()? acc: sumTail(tail(list), acc + head(list)); }

現在， sumTail方法是尾遞歸的，可以通過TCE進行優化。

抽象遞歸

到目前為止，一切都很好，但是由于Java不實現TCE，為什么還要煩惱所有這些呢？好吧，Java沒有實現它，但是我們可以不用它。我們需要做的是：

表示未評估的方法調用
將它們存儲在類似堆棧的結構中，直到遇到終端條件
以LIFO順序評估呼叫

遞歸方法的大多數示例都使用階乘函數作為示例。其他使用斐波那契數列示例。要開始研究，我們將使用更簡單的遞歸加法。

遞歸和核心遞歸函數都是函數，其中f(n)是f(n?1) ， f(n?2)和f(n?3) ，依此類推，直到遇到終止條件（通常為f(0)的f(1) 請記住，在傳統編程中，通常意味著合成評估結果。這意味著組成函數f(a)和g(a)包括對g(a)求值，然后將結果用作f的輸入。不必那樣做。您可以開發一個compose方法來組成函數，而higherCompose函數來完成相同的事情。此方法或此函數均不會評估所組成的函數。它們只會產生另一個功能，以后可以應用。

遞歸和核心遞歸相似，但有所不同。我們創建函數調用列表，而不是函數列表。使用corecursion，每個步驟都是最終步驟，因此可以對其進行評估以便獲得結果并將其用作下一步的輸入。通過遞歸，我們從另一端開始。因此，我們必須將未評估的調用放入列表中，直到找到終止條件為止，從中我們可以按相反的順序處理列表。換句話說，我們堆疊步驟（不評估它們）直到找到最后一個步驟，然后我們以相反的順序處理堆疊（后進先出），評估每個步驟并將結果用作下一個輸入（實際上是前一個）。

我們遇到的問題是Java為此使用了線程堆棧，并且其容量非常有限。通常，堆棧將在6,000到7,000個步驟之間溢出。

我們要做的是創建一個返回未評估步驟的函數或方法。為了表示計算中的步驟，我們將使用一個名為TailCall的抽象類（因為我們希望表示對出現在尾部位置的方法的調用）。

這個TailCall抽象類將有兩個子類：一個代表中間調用，當暫停一個步驟的處理以調用用于評估下一步的新方法時。這將由名為Suspend的類表示。將使用Supplier<TailCall>>實例化它，它表示下一個遞歸調用。這樣，我們將把每個尾部調用與下一個尾部鏈接起來，而不是將所有的TailCalls放在列表中。這種方法的好處是，這樣的鏈表實際上是一個堆棧，可提供恒定的時間插入以及對最后插入的元素的恒定時間訪問，這對于LIFO結構是最佳的。

第二個實現將代表最后一個調用，假定將返回結果。因此，我們將其稱為Return 。它不會保存到下一個TailCall的鏈接，因為接下來沒有任何內容，但是它將保存結果。這是我們得到的：

import java.util.function.Supplier;public abstract class TailCall<T> {public static class Return<T> extends TailCall<T> {private final T t;public Return(T t) {this.t = t;}}public static class Suspend<T> extends TailCall<T> {private final Supplier<TailCall<T>> resume;private Suspend(Supplier<TailCall<T>> resume) {this.resume = resume;}} }

要處理這些類，我們將需要一些方法：一個返回結果，一個返回下一個調用，以及一個幫助程序方法，確定TailCall是Suspend還是Return 。我們可以避免使用最后一種方法，但是我們必須使用instanceof來完成這項工作，這很丑陋。這三種方法將是：

public abstract TailCall<T> resume();public abstract T eval();public abstract boolean isSuspend();

resume方法在Return中將沒有實現，只會拋出運行時異常。我們API的用戶不應處于調用此方法的情況，因此，如果最終調用該方法，則將是一個錯誤，并且我們將停止該應用程序。在Suspend類中，它將返回下一個TailCall 。

eval方法將返回存儲在Return類中的結果。在我們的第一個版本中，如果在Suspend類上調用它將拋出運行時異常。

isSuspend方法將在Suspend返回true ，在Return中Return false 。清單1顯示了第一個版本。

清單1： TailCall抽象類及其兩個子類

import java.util.function.Supplier;public abstract class TailCall<T> {public abstract TailCall<T> resume();public abstract T eval();public abstract boolean isSuspend();public static class Return<T> extends TailCall<T> {private final T t;public Return(T t) {this.t = t;}@Overridepublic T eval() {return t;}@Overridepublic boolean isSuspend() {return false;}@Overridepublic TailCall<T> resume() {throw new IllegalStateException("Return has no resume");}}public static class Suspend<T> extends TailCall<T> {private final Supplier<TailCall<T>> resume;public Suspend(Supplier<TailCall<T>> resume) {this.resume = resume;}@Overridepublic T eval() {throw new IllegalStateException("Suspend has no value");}@Overridepublic boolean isSuspend() {return true;}@Overridepublic TailCall<T> resume() {return resume.get();}} }

現在，要使我們的遞歸方法可以在任意數量的步驟中工作（在可用內存大小的限制之內！），我們幾乎不需要做任何更改。從我們的原始方法開始：

static int add(int x, int y) {return y == 0? x: add(++x, --y) ; }

我們只需要進行清單2中所示的修改即可。

清單2：修改后的遞歸方法

static TailCall<Integer> add(int x, int y) { // #1return y == 0? new TailCall.Return<>(x) // #2: new TailCall.Suspend<>(() -> add(x + 1, y – 1)); // #3 }

＃1方法現在返回一個TailCall
＃2在終端條件下，返回Return
＃3在非終止條件下，返回掛起

現在，我們的方法返回TailCall<Integer>而不是int（＃1）。如果已經達到終止條件，則此返回值可以是Return<Integer> （＃2），如果尚未達到，則可以是Suspend<Integer> （＃3）。 Return用計算的結果實例化（因為y為0，所以x是x），而Suspend則用Supplier<TailCall<Integer>>實例化，后者是根據執行順序進行下一步的計算，或者就調用順序而言，前一個。重要的是要了解，Return對應于方法調用的最后一步，但對應于評估的第一步。另請注意，我們對評估進行了少許更改，用x + 1和y – 1替換了++x和--y 。這是必要的，因為我們使用的是閉包，僅當對變量的閉包實際上是最終的時才起作用。這是騙人的，但沒有那么多。我們可以使用原始運算符創建并調用dec和inc這兩個方法。

此方法返回的是一系列TailCall實例，所有實例均為Suspend實例，最后一個實例為Return。

到目前為止，還算不錯，但是顯然，這種方法并不能代替原始方法。沒什么大不了的！原始方法用于：

System.out.println(add(x, y))

我們可以這樣使用新方法：

TailCall<Integer> tailCall = add(3, 100000000);while(tailCall .isSuspend()) {tailCall = tailCall.resume();}System.out.println(tailCall.eval());

看起來不是很好嗎？好吧，如果您感到沮喪，我可以理解。您認為我們將以透明的方式使用新方法代替舊方法。我們似乎離這很遠。但是，我們可以毫不費力地使事情變得更好。

直接替換堆?；A遞歸方法

在上一節的開頭，我們說過，遞歸API的用戶將沒有機會通過在Return上調用resume或在Suspend上調用eval來弄亂TailCall實例。通過將評估代碼放在Suspend類的eval方法中，可以輕松實現：

public static class Suspend<T> extends TailCall<T> {...@Overridepublic T eval() {TailCall<T> tailRec = this;while(tailRec.isSuspend()) {tailRec = tailRec.resume();}return tailRec.eval();}

現在，我們可以以更簡單，更安全的方式獲得遞歸調用的結果：

add(3, 100000000).eval()

但這還不是我們想要的。我們想要擺脫對eval方法的調用。這可以通過一個輔助方法來完成：

import static com.fpinjava.excerpt.TailCall.ret; import static com.fpinjava.excerpt.TailCall.sus;. . .public static int add(int x, int y) {return addRec(x, y).eval(); }private static TailCall<Integer> addRec(int x, int y) {return y == 0? ret(x): sus(() -> addRec(x + 1, y - 1)); }

現在，我們可以完全像原始方法一樣調用add方法。請注意，通過提供靜態工廠方法實例化Return和Suspend，我們使遞歸API更易于使用：

public static <T> Return<T> ret(T t) {return new Return<>(t); }public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) {return new Suspend<>(s); }

清單3顯示了完整的TailCall類。我們添加了一個私有的no arg構造函數，以防止被其他類擴展。

清單3：完整的TailCall類

package com.fpinjava.excerpt;import java.util.function.Supplier;public abstract class TailCall<T> {public abstract TailCall<T> resume();public abstract T eval();public abstract boolean isSuspend();private TailCall() {}public static class Return<T> extends TailCall<T> {private final T t;private Return(T t) {this.t = t;}@Overridepublic T eval() {return t;}@Overridepublic boolean isSuspend() {return false;}@Overridepublic TailCall<T> resume() {throw new IllegalStateException("Return has no resume");}}public static class Suspend<T> extends TailCall<T> {private final Supplier<TailCall<T>> resume;private Suspend(Supplier<TailCall<T>> resume) {this.resume = resume;}@Overridepublic T eval() {TailCall<T> tailRec = this;while(tailRec.isSuspend()) {tailRec = tailRec.resume();}return tailRec.eval();}@Overridepublic boolean isSuspend() {return true;}@Overridepublic TailCall<T> resume() {return resume.get();}}public static <T> Return<T> ret(T t) {return new Return<>(t);}public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) {return new Suspend<>(s);} }

既然您有了堆棧安全的尾部遞歸方法，那么可以對函數執行相同的操作嗎？在我的《 Java中的函數式編程》一書中，我談到了如何做到這一點。

翻譯自: https://www.javacodegeeks.com/2015/10/stack-safe-recursion-in-java.html