退出條件。堆棧溢出錯誤

沒有退出條件的遞歸代碼示例

讓我們再來看一個遞歸問題。例如，考慮計算斐波那契數列。大家應該都記得，斐波那契數列是一個數列，其中前兩個數字是0和1，後面的每個數字都等於前兩個數字的和。

讓我們編寫代碼來計算和顯示這些數字：

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}

在第一次調用遞歸printFibonacci方法之前，打印序列的前兩個數字：零和一。我們需要這樣做，因為遞歸方法只顯示輸入參數的總和，而不是參數本身。

代碼看起來沒問題：我們得到兩個數字，計算它們的和，將其打印在控制台上，然後再次遞歸調用printFibonacci方法。我們將前一個數字 (previous) 和當前數字 (current) 作為參數傳遞。

實際上，代碼有兩個錯誤。如果您運行代碼，您可以看到它們。

第一個錯誤是long類型溢出。我們序列中的第 104 個數字是負數，表明long類型溢出了。

第二個錯誤是不同的。在計算了大約 12,000 個數字後，我們得到：

現在是時候回憶一下 Java 中的方法調用棧是什麼了。Java 機器保留所有函數調用的記錄。為此，它使用一種稱為堆棧的特殊集合。當一個函數調用另一個函數時，Java 機器會將一個新的 StackTraceElement 壓入堆棧。當函數結束時，這個元素從棧中移除。因此，堆棧始終存儲有關函數調用堆棧當前狀態的最新信息。StackTraceElement 的文檔說它“在由於應用程序遞歸太深而發生堆棧溢出時拋出”。運行中的 JVM 有一塊特殊的內存區域用於存儲方法調用堆棧。此內存區域的大小取決於操作系統和 JVM 設置。除了方法調用棧本身，原始變量（方法參數的具體值）和引用變量的地址（在稱為“堆”的內存區域中）存儲在這個特殊的內存區域中。調用堆棧的訪問遵循後進先出原則。

具有退出條件的更正示例

讓我們從修復代碼中的第二個問題開始。

讓我們嘗試正面解決問題：如果堆棧太小，那麼讓我們把它變大。為此，使用“-Xss”標誌啟動 JVM 並指定為堆棧分配多少內存。讓我們嘗試分配 5 兆字節。這就是它在 IDEA 中的樣子：

我們設法增加了輸出的長度。現在可以計算超過 49,000 個數字的序列而不是限於大約 12,000 個數字。但在某些時候，我們仍然會收到StackOverflowError。

您可以嘗試增加堆棧的大小，但這並不能解決根本問題。所以，讓我們從邏輯上尋找問題。遞歸停止時必須有一個點。換句話說，必須有一些條件來確定何時不再調用遞歸方法，從而允許調用堆棧展開。要定義這樣的條件，讓我們明確我們的目標：只要其數字小於Integer.MAX_VALUE就顯示斐波那契數列。

讓我們編寫一個新的printFibonacciWithCondition方法來考慮這個條件。我們將在 main 方法中調用新的更正方法。

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}

運行代碼後，我們看到輸出以數字1836311903結尾。這個數字之前的數字是1134903170。這些數字的總和是2_971_215_073，確實大於Integer.MAX_VALUE(2_147_483_647 )。

此更改自動修復了長溢出錯誤。如果您需要計算更多的系列，您將需要使用其他數據類型，例如BigInteger。

遞歸下降和展開

下面一步步分析一下我們的代碼是如何執行的。為此，我們將添加一個echo方法，並在遞歸調用printFibonacciWithCondition方法之前和之後調用它。

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}

該程序為我們提供了以下輸出：

這是正在發生的事情的可視化。

再說一遍：調用了printFibonacciWithCondition方法。它計算當前數字。如果它適合我們，那麼我們會顯示它並使用新參數再次調用printFibonacciWithCondition方法。

只要調用遞歸方法，就稱為“遞歸下降”。當遞歸終止並且方法調用返回時，我們說調用堆棧正在“展開”。

遞歸是編程中一個有趣的話題。為了更好地處理材料，讓我們稍微改變一下我們的任務。新任務是按降序輸出斐波那契數列中不超過Integer.MAX_VALUE的所有數字。我們已經編寫了此任務所需的所有代碼。剩下的就是交換顯示當前數字和調用遞歸方法的順序。也就是說，在第一個例子中，計算出的數字是在“下降”時顯示的，但現在我們需要“下降到最底部”，然後在“返回的途中”顯示數字。當然，在main方法中，我們在調用遞歸方法後顯示它們後交換序列的兩個初始數字（零和一）。為了可讀性，方法。

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}

輸出將是：