我是计算机科学和学习递归方法的新手。有人可以简要解释一下此方法吗?
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); // ??
}
}
机器不知道 factorial
是什么,那里的代码告诉它如何计算阶乘。通过说“您给我的号码是1吗?”来完成此操作。直到它返回的数值乘以函数n - 1
的返回值,从本质上讲,这将层叠为阶乘的计算。
如果您举个例子,这很容易看出:
3! = 3*2*1
或
3! = 3*2!
这是return方法的形式:
factorial(n) = n * factorial(n-1)
给出的程序:
factorial(3);
将通过以下步骤:
3*factorial(2)
3*factorial(2)
,它计算factorial(2)
。2*factorial(1)
,因为它要返回到第三步,所以overall的返回值现在将是3*2*factorial(1)
。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。负整数,浮点数和复数值的阶乘也可以定义,也可以内插,如上一句中链接中所述,但它们比简单的递归阶乘复杂得多。
它知道什么是阶乘,因为您将其定义为阶乘。
您已经创建了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)
,这与您在最后一行看到的完全一样。
只需拿一张纸并追踪您的代码:
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
语句
您的代码:
private static long factorial(int n) {
if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
定义名为factorial
的方法。可以将其命名为func
,fred
或任何您喜欢的名称。它不会改变其行为。
其行为如下:
n
等于1,则仅返回1n
的乘积,并使用等于factorial
的参数调用n - 1
。这是递归步骤。请注意,该函数可以调用自身,直到递归调用返回之前它不会返回。调用链被推入堆栈,每个调用在计算乘积并返回之前都等待下一个返回。稍加思考,您应该能够看到上述行为与因式函数的通用教科书定义完全匹配。
假设使用大于0的参数调用factorial
,则递归最终总是以对等于1的参数调用factorial
结束。如所写,如果该函数失败,则会产生堆栈溢出异常调用n
小于1的值。
这是将问题分解成较小的版本。
什么是1!?
是1。
由以下代码表示
if (n == 1)
return 1;
如果知道(n-1)!可以找到n!吗?当然可以!
只需乘以n
由代码的另一部分表示。
else
return n * factorial(n - 1);
您正在做的是从内部调用该函数,最终n
将为1,并且循环将停止。
您的其余代码无关紧要,请分解您的递归函数:
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
乘以这个较小问题的结果,则会得到正确的答案。
数字的整数] >>(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),直到我们遇到基本情况,我们的函数才不返回任何东西)