使用递归分解数字

Question

我试图理解递归，并发现以下内容作为freecodecamp递归练习的答案，以分解一个数字。这是正确的，但我不明白它是如何运行的。

• -如果"return 1"退出函数，那么输出不应该是1吗？
• -所需的模式，如果 10x9x8x7 等。但是，如果它每次都调用自己，这不遵循模式 10x9、9x8、8x7 等吗？

抱歉，如果这不是一个合适的问题，第一次使用。

function factorialize(num) {
if (num === 0) { return 1; }
return num * factorialize(num-1);
}
factorialize(5);
>120

Answer 1

由于递归函数的各个结果是累积的，因此可以通过以下方式想象这个过程：

1. 调用因子分解(5);
2. 第一个递归步骤返回 -> 5 * 阶乘化(4)

   当前值：5 * 阶乘化(4)

3. 第二个递归步骤返回 -> 4 * 阶乘化(3)

   当前值：5 * 4 * 阶乘化(3)

4. 第三个递归步骤返回 -> 3 * 阶乘化(2)

   当前值：5 * 4 * 3 * 阶乘化(2)

5. 第四递归步骤返回 -> 2 * 阶乘化(1)

   当前值：5 * 4 * 3 * 2 * 阶乘化(1)

6. 第六递归步骤返回 -> 1 * 阶乘化(0)

   当前值：5 * 4 * 3 * 2 * 1 * 阶乘化(0)

7. 第七个(最后一个)递归步骤返回 -> 1

   当前值：5 * 4 * 3 * 2 * 1 * 1

这导致 120。

function factorialize(num) {
if (num === 0) { return 1; }      // 7th step
return num * factorialize(num-1); // 1st to 6th step
}

Answer 2

迭代编写函数可能有助于澄清问题;循环中的每个步骤都相当于一个递归调用。

function factorialize(num) {
let factorial = 1; // base case, equivalent to fact(0)
for (let i = 1; i <= num; i++) { // multiply for each number from 1 to n
factorial *= i;
}
return factorial;
}
console.log(factorialize(5));

递归函数的工作方式相同。fact(n)是原始调用，但要计算fact(n)，它必须首先计算n - 1的阶乘。 没有fact(n - 2)就无法计算fact(n - 1)。每个函数都被推送到调用堆栈上，等待其上方的函数解析。最终fact(0)将被调用，我们知道这是基于阶乘的递归定义1的。fact(0)称为基本情况，不会进行任何递归调用。如果没有基本情况，n会变得越来越小，直到堆栈空间不足，导致程序崩溃。

有了来自基本情况的信息，fact(1)现在可以计算1 * 1并将结果1传递给其调用函数fact(2)。fact(2)计算2 * 1并将结果传递给fact(3)，计算3 * 2并将结果传递给fact(4)，计算4 * 6并将结果传递给fact(5)，计算5 * 24并返回120的最终结果。

如果这仍然没有意义，请折腾一个console.log()来查看沿途的每一步：

function factorialize(num) {
if (num === 0) { // base case 
console.log("fact(0) returning 1");
return 1; 
}
// recursive case
const result = num * factorialize(num - 1);
console.log("fact(" + num + ") returning " + result);
return result;
}
console.log(factorialize(5));