递归在 Java 中的工作原理

2023-01-05 小编

Java 开发人员经常使用算法将问题分解为更容易解决的较小块。这种分而治之的方法使得，为了解决每个损坏的问题，您可以多次调用同一函数来处理每个部分。

在编程中，递归在方法调用自身时发生，并在达到基本情况时终止。基本情况是一个条件语句，它执行 return 语句而不是再次调用相同的函数，从而结束循环。递归的典型用途包括分而治之算法和解决串联发生的问题，例如计算斐波那契数列或阶乘。

在这篇文章中，我们将讨论 Java 中的递归，以及如何编写计算数字阶乘的递归方法。您将了解如何在 Java 中使用递归，当它比其他方法更好时，以及实现递归函数时的最佳实践。

立即下载：Java & JavaScript 简介

在 Java 中使用递归

Java 中用于递归的代码相对简单，尤其是与迭代方法相比。递归可帮助您编写使用更少内存的软件，因为变量会在函数返回后立即删除。递归函数是纯函数，这意味着它们的输出仅取决于它们的输入参数。

递归和阶乘

在 Java 中理解递归的最简单方法之一是检查打印数字阶乘的函数。

通过将一个数字与小于自身的所有正整数相乘来计算阶乘。在本节中，您将看到递归代码和基于循环的代码之间的比较。

例如，5 的阶乘是 120，您可以这样表示：

阶乘（5） = 5 * （4 * （3 * （2 * 1）））

请注意这是如何形成一个序列的：5 的阶乘等于 5 乘以 4 的阶乘，4 乘以 3 的阶乘，依此类推。递归的基本情况为 0。当输入参数达到 0 时，您将从方法主体返回 1。

使用循环的阶乘

以下函数计算作为参数传递的数字的阶乘 — 一次使用 For 循环，然后再次使用递归。在主入口点调用此方法并传递参数。您可以通过提供 5 作为输入参数来测试这一点，程序将返回 120。

您可以在 Java 中同时使用 For 和 While 循环来执行阶乘。为了便于演示，此示例使用 For 循环。

public static int getFactorialForLoop(int number) {
    int result = number;

    if (number >= 1) {
        for (int i = number - 1; i >= 1; i--) {
            result = result * i;
        }

        return result;
    }
    else {
        System.out.println("number has to be positive");
        return 1;
    }}

使用递归的阶乘

接下来，让我们尝试使用递归来执行相同的任务。

public static int getFactorialRecursively(int number){
    if (number <= 1){
        return 1;
    }
    else {
        return number * getFactorialRecursively(number - 1);
    }}

如您所见，使用递归编写的代码比使用 For 循环的代码干净得多，并且更干净的代码容易出现更少的错误。在递归中，必须仅定义基本情况和递归情况。

在可能的情况下，递归提供了很多优点和一些缺点，我们将在后面讨论。

处理边缘情况

构建递归函数时，可以添加边缘情况以缩短递归。短路测试下一个递归调用是否为基本情况。当数字等于或小于 0 时，您可以返回 2 并开始递归，而不是仅在数字等于或小于 0 时返回 1。

请记住，短路需要编写一个包装函数，用于对参数执行条件检查。通常不鼓励这样做，因为包装器的值需要更高。

若要处理短路，请将新的成员方法作为递归函数的包装器添加到类中。包装器函数阶率调用内部方法阶乘递归来启动递归。此代码具有相同的输出，但在执行中跳过另一个步骤，因为当数字变为 2 时它会短路。

private int factorialRecursive(int number) {
    if (number <= 1) {
        return 1;
    }

    return factorialRecursive(number - 1) * number;}private int factorial(int number) {
    if (number == 2) {
        return 2;
    } else {
        return factorialRecursive(number);
    }}

递归的优缺点

现在，让我们研究一下使用“递归和阶乘”部分中的方法在递归和非递归方法之间做出决定的一些因素。

递归的优点

在 Java 中，递归以多种方式提高性能，包括：

记忆

记忆跳过已计算输出并存储在内存中的递归情况。这可以防止重复计算，因为输出已存储并提高软件的性能。此方法利用缓存使用递归来提高性能。

查找阶乘的代码使用缓存变量来存储以前使用的值。

static int[] cache = new int[1000];static int MemoizedFactorial(int number) {
    if (number <= 1)
        return number;

    if (cache[number] != 0)
        return cache[number];

    else {
        cache[number] = MemoizedFactorial(number - 1) +
            MemoizedFactorial(number - 2);

        return cache[number];
    }}

此外，递归方法还仅依赖于输入，并且包含业务逻辑，而没有底层技术方面（如堆栈管理）。这允许工程师编写具有更少内存和更少副作用的软件（方法范围之外的状态更改，例如系统参数）。

此外，它对于特定算法很有用，例如树遍历。深度优先搜索算法使用堆栈来执行搜索。因此，您可以将算法编写为递归函数，与迭代方法相比，它很容易编写。例如，比较使用递归方法和迭代方法的预序遍历代码。

使用递归的预序遍历

public void PreOrder(Node node) {
    if (node != null) {
        visit(node.value);
        PreOrder(node.left);
        PreOrder(node.right);
    }}

使用迭代预序遍历

public void PreOrderWithoutRecursion() {
    Stack < Node > stack = new Stack < Node > ();
    Node current = root;
    stack.push(root);

    while (!stack.isEmpty()) {
        current = stack.pop();
        visit(current.value);

        if (current.right != null) {
            stack.push(current.right);
        }

        if (current.left != null) {
            stack.push(current.left);
        }
    }}

最后，一些表达式，特别是在数学运算中使用，具有特定的符号。这些操作的输入的最常见表示法是前缀、中缀和后修复。固定是操作数在操作中的位置。这允许递归函数轻松复制操作，而无需额外的包装器。您可以使用上述表达式从数组构建树，反之亦然。这有助于在一维内存结构（如 RAM）中表示复杂的数据结构，例如树。

递归的缺点

递归也有其局限性。首先，递归函数反复调用自身，这可能导致堆栈溢出参数和程序过早终止。在 Java 中，每个程序的堆栈空间是有限的，而堆的限制较小。因此，当程序尝试使用大量堆栈空间时，它会收到一个 StackOverflowException，其中程序继续推送到堆栈，但没有弹出并达到限制。

另一方面，堆不是后进后出操作（LIFO），因此程序可以在系统允许的范围内尽可能多地推送到堆。

此外，当递归函数将函数调用作为最后一个语句执行时，Java 编译器无法优化使用尾递归的递归方法。相反，递归函数将函数调用作为头部递归中的第一个语句执行。

“处理边缘情况”部分中的代码演示了所有函数都不是尾递归。阶乘递归是一种非尾递归（不要与头部递归混淆），因为它作为函数的结果运行。

例如，您可以使用迭代方法编写之前检查的阶乘函数：

private int factorial(int number) {
    int factorial = 1;

    for (int i = 2; i <= number; i++) {
         factorial = factorial * i;
    }

    return factorial;}

此方法使用变量来存储所有数字的乘积。它运行一个循环，该循环从变量 i 设置为 2 开始并返回产品。请注意，大于 2 的数字必须相乘，直到 i 等于数字参数本身。当满足循环的条件时，迭代将停止。

迭代样式可以更轻松地定义迭代计数、内存管理以及计算停止的时间。这也允许对堆栈增长进行更多控制。它有助于避免Java程序中的StackOverflowException。

同样，迭代方法不需要包装函数。因此，它们避免了任何不必要的额外堆栈输入。这就是为什么通常不鼓励缩短递归以获得一次性性能改进的原因。

但是，对于基于序列的问题（例如计算阶乘或斐波那契数列），编写迭代方法通常更麻烦。递归通常会产生一种更优雅的方法，该方法以更少的代码行产生相同的结果。

递归最佳实践

在递归函数中，处理所有可能的边缘情况以从递归函数返回。如果不处理边缘情况，则递归可能会永远运行，从而导致程序由于 StackOverflowException 错误而提前终止。递归中的短路并不总是最好的方法，因为您经常必须围绕递归函数编写包装函数。对递归方法中的边缘情况和函数可以接受的参数应用条件检查，而不是短路包装器函数。

此外，请记住，堆栈不会跟踪已处理的参数。这可能会导致递归函数重复处理相同的参数。为了避免这种重复并降低时间复杂度，您应该始终使用记忆来存储处理后的参数。