英文:
Factorial Recursion, answer doesn't make sense on paper?
问题
以下是翻译好的内容：
我在 CodingBat 上做递归练习时遇到了这个问题：
public int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n-1);
}
我不明白这在纸上是如何工作的。当 n 为 1 时返回 1，没问题；n 为 2 时返回 2，没问题；n 为 3 时返回 6，没问题；但是 factorial(4) 返回 24？factorial(5) 返回 120？
这不太有道理，因为它似乎是从 n 的上一个答案开始进行的，但没有减去 1？但是它通过了所有的测试。所以它是在做 64 = 24，而不是 4(n-1)，这不会等于 24？请帮忙解释一下。
英文:
So I was on codingbat doing recursion excercises and I ran into this
public int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n-1);
}
I don't understand how this works on paper. as 1 returns 1 thats fine, 2 returns 2, thats fine, 3 returns 6 thats fine, but then factorial(4) returns 24? factorial(5) returns 120?
It doesn't make sense because it is doing it from the last answer of n I assume but not minusing 1? But passes all the tests. So it does 6*4 = 24, rather than 4x(n-1) which wouldn't equal 24? Help?
答案1
得分: 1
对于任何阶乘(n)，计算方法为 n x (n-1) x (n-2) x ... x 1
所以对于阶乘(4)，计算过程为 4 x 3 x 2 x 1 = 24
递归通常是通过阶乘的示例来介绍的，所以为了可视化，它看起来像是
fact(4) = 4 x fact(3)
= 4 x 3 x fact(2)
= 4 x 3 x 2 x fact(1)
= 4 x 3 x 2 x 1 = 24
递归重复进行，直到达到"锚点"，即基本情况为 1。
英文:
For any factorial(n), it is computed as n x (n-1) x (n-2) x ... x 1
So for factorial(4) that will be 4 x 3 x 2 x 1 = 24
Recursion is mostly introduced using factorial as an example, so to visualize it will look like
fact(4) = 4 x fact(3)
= 4 x 3 x fact(2)
= 4 x 3 x 2 x fact(1)
= 4 x 3 x 2 x 1 = 24
The recursion repeats until it hits the "anchor" which is the base case of 1
答案2
得分: 0
当你试图理解递归时，将其想象成一个堆栈是很有帮助的。每当我们调用 return n * factorial(n - 1) 时，我们都会将一个值推入堆栈，这样在计算完 factorial(n - 1) 调用后，我们可以取回这个值。依此类推。
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 *factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120
英文:
When you're trying to understand recursion, it's good to picture a stack. Every time we're calling return n * factorial(n - 1) we are pushing a value down the stack so we can retrieve it after we're done computing the factorial(n - 1) call. And so on so forth.
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 *factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论