Javascript 递归和函数

Question

难以理解此代码的工作原理

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.push(n);
    return countArray;
  }
}
console.log(countup(5));

我能理解为什么一旦它到达 Array.push 就打印出 [1]，但在那之后我不明白它是如何从 [1] 到 [=15] =].

此外，(n-1) 不会总是 1-1 因为没有它 if (n < 1) 就不会是真的吗？

Answer 1

添加一些日志记录应该有助于您理解执行顺序。这最初是用 countup(5) 触发的，然后递归调用 countup(n-1) 直到 n-1 为 0。returns 是一个空数组，然后每次调用 countup将 n 附加到数组并将其附加到 returns 。所以你最终得到一个执行顺序，如：

countup(5)
calls countup(4)
calls countup(3)
calls countup(2)
calls countup(1)
calls countup(0), which returns [] to countup(1)
the call from countup(1) appends 1 to the (empty) array and returns [1] to countup(2)
the call from countup(2) appends 2 to the array and returns [1, 2] to countup(3)
the call from countup(3) appends 3 to the array and returns [1, 2, 3] to countup(3)
the call from countup(4) appends 4 to the array and returns [1, 2, 3, 4] to countup(4)
the call from countup(5) appends 5 to the array and returns [1, 2, 3, 4, 5]

function countup(n) {
  console.log('countup('+n+')');
  if (n < 1) {
    console.log('returning empty array');
    return [];
  } else {
    console.log('calling countup - 1');
    const countArray = countup(n - 1);
    console.log('pushing '+n);
    countArray.push(n);
    console.log('returning countArray:');
    console.log(countArray);
    return countArray;
  }
}

console.log(countup(5));

Answer 2

如果您在调试器中逐行执行它，一切都会变得清晰：

我无法像我希望的那样慢地记录它，因为我运行达到了最大值。从中创建 GIF 的大小。无论如何，如果您自己也这样做可能是最好的。观察调用堆栈和局部变量的值。当您以交互方式执行此操作时，我鼓励您还探索调用堆栈中函数 higher-up 实例的局部变量（您可以单击调用堆栈条目以切换到其范围）。

countup(5)被调用，所以n = 5。由于 5 不小于 1，我们转到 else 分支。使用 n = 5，我们得到 n - 1 = 4，因此调用 countup(4)。
与#1 相同，但使用 n = 4，最终调用 countup(3)。
多次与#1/#2 相同，直到我们最终调用 countup(0)。此时我们在调用堆栈中共有 6 个函数实例。
用n = 0，我们进入if的第一个分支，returning一个空数组[]。
countup(1)实例从countup(0)接收[]的return值并将其存储到countArray。
countup(1) 实例将 n (1) 推入 countArray，产生 [1]。然后数组 returned 到被调用的 (countup(2)).
countup(2)实例从countup(1)接收[1]的return值，并将其存储到自己的countArray。
countup(2) 实例将 n (2) 推入 countArray，产生 [1, 2]。然后数组 returned 给调用者 (countup(3)).
步骤 #5-8 继续 countup(3)、countup(4) 和 countup(5)，直到最后 countup(5) 将 5 推入其 countArray，以 [1, 2, 3, 4, 5] 结尾，该数组现在 returned 给调用者（主函数）。
主函数从 countup(5) 得到结果 [1, 2, 3, 4, 5] 现在传递给 console.log.

你也可以这样想：

countup(0) returns []¹.
countup(n) 对于任何非零 n returns [...countup(n - 1), n]².

(...其中 ...array 表示 spread operator 因此 [a, ...[b, c], d] 变为 [a, b, c, d])

所以我们得到如下进化：

向上：

countup(0) = []
              \_______________________
                                      \
countup(1) = [...countup(0), 1] = [...[], 1] = [1]
                                         ______/
                                        /
countup(2) = [...countup(1), 2] = [...[1], 2] = [1, 2]
                                            ____/
                                           /
countup(3) = [...countup(2), 3] = [...[1, 2], 3] = [1, 2, 3]
                                               ____/
                                              /
countup(4) = [...countup(3), 4] = [...[1, 2, 3], 4] = [1, 2, 3, 4]
                                                  ____/
                                                 /
countup(5) = [...countup(4), 5] = [...[1, 2, 3, 4], 5] = [1, 2, 3, 4, 5]

向下：

countup(5) = [...countup(4),  5]
              |············\__ \__
              |···············\   \
           = [...countup(3),  4,  5]
              |············\__ \__ \__
              |···············\   \   \
           = [...countup(2),  3,  4,  5]
              |············\__ \__ \__ \__
              |···············\   \   \   \
           = [...countup(1),  2,  3,  4,  5]
              |············\__ \__ \__ \__ \__
              |···············\   \   \   \   \
           = [...countup(0),  1,  2,  3,  4,  5]
              |··· _______/   |   |   |   |   |
              |···/           |   |   |   |   |
           = [...[],          1,  2,  3,  4,  5]
              \_x_/           |   |   |   |   |
           = [                1,  2,  3,  4,  5]

_{1: 从技术上讲，任何 n < 1 都会使 countup(n) return []，不仅n = 0.}

_{2: 从技术上讲，这里一直使用同一个数组，只是在每一步都发生了变化。在处理这个问题的纯功能方式中，必须创建一个副本（const countup = n => n < 1 ? [] : [...countup(n - 1), n]）。但这对于这个解释并不重要，因为在 returned.}

之后，前面的函数当然不再需要数组了。

Answer 3

递归方法很有趣，但乍一看有点难以理解。在这个特定的例子中，函数计算一个非常具体的约束。如果 n < 1 函数将 return 一个空数组。让我们深入了解代码执行：

在第一次迭代时 n = 5 允许执行 else 块。一旦第二次 countup 调用 (countup(n - 1)) 它再次计算输入，并且由于 n 仍然大于 0，整个过程将重复。
一旦 countup 函数接收到 0 (n = 0) 的输入，它 return 就是一个空数组。这样的数组然后被分配给 countArray 变量（在这个特定点 countArray = []）并且 n 的当前值被推入数组（因为 n = 0 的情况已经 returned，您将找到 n=1) 的情况。同样，此过程将在每个步骤中重复进行，直到达到 n=5 的情况（从技术上讲是您的第一次迭代）。一旦 5 被推入数组，该函数将 return 包含从 1 到提供的数字 n 的每个值的数组从最小到最大的数字排序。

Javascript 递归和函数

Javascript Recursion and Functions

javascript

recursion