退出条件。堆栈溢出错误

没有退出条件的递归代码示例

让我们再来看一个递归问题。例如，考虑计算斐波那契数列。大家应该都记得，斐波那契数列是一个数列，其中前两个数字是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);
    }
}
    

输出将是：