文章
开始
开始学习
JavaRush /Java 博客 /Random-ZH /Java 中的递归
Алексей Дмитревский
第 31 级
Москва

Java 中的递归

已在 Random-ZH 群组中发布
要理解什么是递归，首先要理解什么是递归。其实理解这些函数并没有什么困难，只需要理解一次就可以了。并在编程时进行练习。 Java 中的递归 - 1递归不仅出现在编程中，也出现在现实生活中。手里拿着一面镜子，站在另一面镜子前。反射的反射会在反射中反映出来等等。你会看到无数的反射进入无穷远。您可以在“献给土拨鼠之日…… ”一文中找到更多关于“真实”递归的信息，让我们从现实世界回到程序员的日常生活。简单定义：java中的递归函数是调用自身的函数。让我给你举一个非常简单但非常有害的例子： 
public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}
为什么它有害？我建议你自己检查一下！如果您决定进行这次冒险（您程序员很可能会这样做！），请在注释中写下 JVM 将抛出什么错误=）这个示例以及许多其他示例都表明，在 Java 中使用递归必须采用以下方法：警告。您需要了解这种解决问题的方法在何时、何地以及为何是合理的，并确保您的函数不会将程序的执行变成“土拨鼠之日”。 对于理解递归还有两个更重要的定义：
  • 递归基础——退出递归调用块的条件——问题的基本解决方案，在不需要调用递归的条件下。
  • 递归步骤是指函数在更改参数时调用自身。
使用递归函数的一个典型示例是计算数字的阶乘。如果您忘记了，让我提醒您：正整数N（表示为 N！）的阶乘是 中的数字的乘积1 до N: N! = 1 * 2 * 3 * … (N - 1) * N。顺便说一句，根据定义，零的阶乘等于 1。因此，可以找到任何正整数和零的阶乘（用数学语言来说 - 对于非负整数集合或自然数集合和零）。我认为您了解可以使用循环对阶乘进行编程。实际上，这里有一个非递归方法来解决这个问题： 
private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
Java-университет
让我们添加一个检查来检查该数字是否为正数和整数，以及一个单独的零检查。 
private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
现在我给出递归解决这个问题的方法代码： 
private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}
我们来看看调用的输出结果： 
System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));
我们得到期望值： 
1
1
2
6
24
120
720
让我们添加一个不错的输出并计算更大数字的阶乘： 
private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");
我们得到：15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! 在这种情况下，使用递归函数是合理且安全的。我们已经明确定义了退出递归块的条件，并且我们有信心它是可以实现的：我们输入一个非负整数，如果该数字等于零或一，则返回结果，如果该数字更大，我们将结果乘以数字 的函数n-1。以三的阶乘为例： 
factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1
关于使用注意事项：这个功能有什么漏洞？如果你给一个方法一个负数作为参数，那么检查 
if (n == 1 || n == 0) {
    return result;
}
毫无意义，我们最终会陷入一个无休止的自我调用循环中。值得添加非负性检查： 
if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}
一切都会好起来的。 一种方法相对于另一种方法有什么优点？看似没有太大区别，但事实上，大量的递归调用会对性能和内存消耗产生负面影响：调用堆栈是一个几乎不可控的资源，在不同的条件下调用同一个递归函数，我们可能会也可能不会遇到与此资源相关的问题。几乎所有使用迭代（如 的循环for-each）解决的问题也可以递归地解决。递归的优点是可读性和书写方便；缺点我们在上面讲过：“搬起石头砸自己的脚”的机会并不是虚无缥缈的。使用所谓的“复杂递归”时需要更加小心：函数A()会调用函数，函数B()又调用函数A()。解决此类问题需要充分理解递归的工作原理。此类任务的一个示例：计算 的值x^n/(n!)。正如我们上面所讨论的，阶乘是在非负整数集合上定义的。最后我给出解决方案代码。复杂的递归将包含两种方法： 
private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}
要进入递归，需要使用一个方法calculate，该方法调用一个方法power，该方法又调用一个方法calculate。我们在幂法中定义了递归基础： 
if (n == 1) return x;
递归步骤也在那里定义： 
return x * calculate(x, n - 1);
剩下的就是添加对输入数据有效性的检查：
  • 零以外的任何数字都等于零的幂1。如果n = 0，那么n! = 1。需要退货1。
  • 零的任意幂都等于零。
  • 我们不会考虑类型不确定性0^0，并将接受此类输入数据为无效数据。
通过所有检查，方法将如下所示： 
private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}
好吧，当调用函数时，你需要记住捕获错误： 
try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}
评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION