首页 > 新闻 > 递归在 Java 中的工作原理

递归在 Java 中的工作原理

2023-01-05 小编

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

在办公室的计算机上使用 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 错误而提前终止。递归中的短路并不总是最好的方法,因为您经常必须围绕递归函数编写包装函数。对递归方法中的边缘情况和函数可以接受的参数应用条件检查,而不是短路包装器函数。

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

递归在 Java 中的工作原理

递归函数允许 Java 程序中的代码调用自身,通过对一系列输入参数运行相同的操作来计算输出。所涵盖的示例只是其实际应用的一小部分。Java 软件开发工具包 (SDK) 中的各种搜索和排序算法都使用递归,包括深度优先搜索、合并排序和树遍历。

这并不是说递归是万能的方法,尤其是在内存有限的情况下。在这种情况下,建议使用迭代方法来编写函数。这使得解决方案更具可扩展性,并且不易发生内存溢出。

但是,递归使软件工程师能够利用函数式编程的最佳实践,并将其应用于面向对象的编程,而不会产生副作用。这是一种更聪明而不是更难的方法。


*必填

您好,访客!有什么新鲜事想告诉大家?

点击按钮快速添加回复内容: 高兴 支持 激动 给力 加油 生气 路过 威武
发表
暂时还没评论,等你发挥!