解释递归方法

问题描述 投票:1回答:7

我是计算机科学和学习递归方法的新手。有人可以简要解释一下此方法吗?

 import java.util.Scanner;

public class factorial {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        System.out.print(factorial(n));

    }

    private static long factorial(int n) {      // HERE I DON'T UNDERSTAND HOW 
                                               //  THE MACHINE NOWS WHAT IS "factorial"
        if (n == 1)
            return 1;
        else
            return n * factorial(n - 1);               // ??
    }

}
java methods factorial
7个回答
11
投票

机器不知道 factorial是什么,那里的代码告诉它如何计算阶乘。通过说“您给我的号码是1吗?”来完成此操作。直到它返回的数值乘以函数n - 1的返回值,从本质上讲,这将层叠为阶乘的计算。

如果您举个例子,这很容易看出:

3! = 3*2*1

3! = 3*2!

这是return方法的形式:

factorial(n) = n * factorial(n-1)

给出的程序:

factorial(3);

将通过以下步骤:

  1. 3是否等于1?
  2. 不是,所以它返回3*factorial(2)
  3. 为了获得3*factorial(2),它计算factorial(2)
  4. 现在检查:2是否等于1?
  5. 并非如此,它返回2*factorial(1),因为它要返回到第三步,所以overall的返回值现在将是3*2*factorial(1)
  6. 接下来程序检查:1是否等于1?
  7. 就是这样,它返回1。
  8. [在第五步中返回到我们的调用:2*factorial(1)变为2*1 = 2,它返回到第3步,这是我们的第一个调用,给我们3*2 = 6,这是函数将整体返回的结果。

尽管此方法可以进行一些调整。假设您向其提供了0?因为序列0,-1,-2,-3,-4,...永远不会到达1,所以它将连续调用无限递归的阶乘方法。更好的方法如下所示:

private static long factorial(int n) {

    if (n == 1 || n == 0) {
        return 1;
    } else if (n < 0) {  // factorials are not defined below 0, they can be interpolated
        return null;     // though, see note below
    } else {
        return n * factorial(n - 1);
    }
}

现在,此函数将覆盖整个整数范围的阶乘,对负数使用空解决方案。 n阶乘的定义定义为1到n之间的整数的乘积; see this。负整数,浮点数和复数值的阶乘也可以定义,也可以内插,如上一句中链接中所述,但它们比简单的递归阶乘复杂得多。


2
投票

它知道什么是阶乘,因为您将其定义为阶乘。

您已经创建了private static long factorial(int n),这意味着“具有单个参数n的因子分解方法,该方法返回long,在factorial类上静态可用,并且是该类专用的。

您可以在任何可以访问阶乘的地方调用阶乘,在这种情况下,阶乘类本身就可以调用阶乘。这意味着您可以从main方法调用它,也可以从阶乘方法本身调用它。这只是一个函数调用,碰巧会自行调用。

我们知道阶乘1 * 2 * ... (n-1) * n的定义。我们也可以将其定义为n! = n * (n - 1)!或换句话说factorial(n) = n * factorial(n-1),这与您在最后一行看到的完全一样。


1
投票

只需拿一张纸并追踪您的代码:

factorial(5):
5!=1:
    return 5*factorial(4):
    4!=1:
        return 4*factorial(3):
        3!=1:
            return 3*factorial(2):
            2!=1:
                return 2*factorial(1):
                1==1:
                return 1;

因此,最后我们有:return 5*4*3*2*1语句


1
投票

您的代码:

private static long factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

定义名为factorial的方法。可以将其命名为funcfred或任何您喜欢的名称。它不会改变其行为。

其行为如下:

  • 如果参数n等于1,则仅返回1
  • 否则,它返回n的乘积,并使用等于factorial的参数调用n - 1。这是递归步骤。请注意,该函数可以调用自身,直到递归调用返回之前它不会返回。调用链被推入堆栈,每个调用在计算乘积并返回之前都等待下一个返回。

稍加思考,您应该能够看到上述行为与因式函数的通用教科书定义完全匹配。

假设使用大于0的参数调用factorial,则递归最终总是以对等于1的参数调用factorial结束。如所写,如果该函数失败,则会产生堆栈溢出异常调用n小于1的值。


1
投票

这是将问题分解成较小的版本。

什么是1!

1

由以下代码表示

    if (n == 1)
        return 1;

如果知道(n-1)!可以找到n!吗?当然可以!

只需乘以n

由代码的另一部分表示。

    else
        return n * factorial(n - 1); 

您正在做的是从内部调用该函数,最终n将为1,并且循环将停止。


0
投票

您的其余代码无关紧要,请分解您的递归函数:

private static long factorial(int n) {     
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

[第一行或签名说的是,“我是一个私有方法(private),未附加到返回static(这是一个长整数)的特定对象实例(long)我之所以命名为“阶乘”,是因为输出大概是输入的阶乘。作为输入,我取了一个int,我将其命名为n

我们知道阶乘定义为f(n) = n*(n-1)*...*1。另一种写法是:

f(n) = n * f(n-1)

或:

f(n) = n * (n-1) * f(n-2)
f(n) = n * (n-1) * (n-2) * f(n-3)

依此类推。但是什么时候停止?当n == 1。我们在方法中看到了这一点:

if (n == 1)
  return 1;//If n == 1, return 1. This is the 'base case'
else
  return n * factorial(n - 1);//Multiply n by the factorial of n-1 (duh, right?)

此处的递归调用位于最后一行:它使用same function找出较小问题的解决方案。毕竟,我们知道,如果将n乘以这个较小问题的结果,则会得到正确的答案。


0
投票

数字的整数] >>(n =数字)是所有小于或等于n的正整数的乘积。n的阶乘可表示为n!前/5的阶乘= 5!100的阶乘= 100!

 factorial of 5 means (5!) -> 5 * 4 * 3 * 2 * 1

根据此方法的ex /

  1   private static long factorial(int n) {                                      
  2     if (n == 1){
  3       return 1;
  4     } else{
  5       return n * factorial(n - 1);
  6     }
  7   }

如果我们需要找到5! -(乘以5)必须使用数字5调用上述方法。ex /

factorial(5)

第2行的[if (n == 1)条件检查您传递的数字是否等于1(因为1!等于1),我们以该行为基本情况(递归函数停止的位置)]

基本情况

当我们调用递归函数时,它会不断地反复调用,直到我们的堆栈溢出为止。因此,我们需要一个递归函数的“停止点”。该端点称为基本案例

主要目标是了解这行-

return n * factorial(n - 1);

在我们的第一次迭代中,n = 5和n-1 = 4(根据我们的示例)

想象这样的函数调用

第一次迭代5! = 5 * factorial(4)-在此行中,我们单独保留5,然后*我们再次调用factorial(4)

第二次迭代4! = 4 * factorial(3)-在此行中,我们再次调用factorial(3)

第三次迭代3! = 3 *阶乘(2)-在此行中,我们再次称为阶乘(2)

第4次迭代2! = 2 * factorial(1)-在这一行中,我们再次调用factorial(1)

第5次迭代1! = 1-开始返回1

想象这样的返回值

ex /return 5 * factorial(4)-> 5 * [接收(4 * 3 * 2 * 1)] = 5 *(24)阶乘(4)-4 * factorial(3)-> 4 * [接收(3 * 2 * 1)= 4 *(6)阶乘(3)-------> 3 * factorial(2)-> 3 * [接收(2 * 1)] = 3 *(2)阶乘(2)---------------> 2 * factorial(1)-> 2 * [return 1] = 1this image will helpful (image I got from quora.com) 它一直在调用直到我们的n等于1一旦我们的函数满足n = 1的基本情况,它将开始返回1。

(记住,直到遇到基本情况,它一直调用函数factorial(n),直到我们遇到基本情况,我们的函数才不返回任何东西)

© www.soinside.com 2019 - 2024. All rights reserved.