何时在 Javascript 中设置调用堆栈？

Question

在尝试解决以下问题：

Generate all combinations of an array of string.
Ex: Input: ['A', 'T', 'C', 'K']
Output: [
  'ATCK', 'ATC', 'ATK',
  'AT',   'ACK', 'AC',
  'AK',   'A',   'TCK',
  'TC',   'TK',  'T',
  'CK',   'C',   'K',
  ''
]

我有以下代码：

function getSpellableWords(arr) {
    const res = [];
    // helper(arr, res, 0, '');
    helper(arr, res, 0, []);
    return res;
}

function helper(arr, res, i, slate) {
  const char = arr[i];
  console.log(i, 'i')
  if(i === arr.length) {
    res.push(slate.join(''));
    return;
  }

  // slate = slate + char;
  slate.push(char)
  console.log(slate, 'slate')
  helper(arr, res, i+1, slate);
  slate.pop()

  helper(arr, res, i+1, slate);
}

getSpellableWords(['A', 'T', 'C', 'K']);

我的问题是：

如果我删除代码中的以下行：

helper(arr, res, i+1, slate);

一旦 i 等于 5（即 array.length），代码将在将 slate 推入 res 后停止。但是，如果我保留该行，则会设置一个调用堆栈，因此 i 将从 1->5 上升，然后逐渐弹出到 4 然后 3 然后回到4 等等。为什么会这样？

澄清： 所以我明白对于每个递归调用，都会生成另一个 i 变量。然而，我期待第二次递归调用也再次从 1->4 生成 i，但这次不是线性递增，而是回溯。为什么第一次调用没有回溯，第一次调用只产生第一个结果时，为什么第二次调用产生剩余的结果？

Answer 1

helper 的每个递归调用确实会在调用堆栈上添加一个级别，因此当递归调用 returns 返回其调用者时，调用代码可以继续其自己的本地执行上下文。

helper的每次执行都有自己的执行上下文，其中包括一个本地变量i，它只对可见执行上下文。它仅在调用堆栈中的该级别发挥作用。

请注意，helper 代码永远不会更改其 i 变量的值。当它被调用时，它会被作为第三个参数传递的任何值初始化，这是它唯一拥有的值。

您注意到的更改到i实际上没有更改。您看到的每个 i 的不同值实际上是关于一个 不同的 变量，而该变量恰好具有相同的名称。

这里是关于这些 i 变量生命周期的一个小模式，当 res 变量的长度为 2 时（只是为了不让它太长！）：

helper(arr, res, 0, []); // The initial call
    +--------top level helper execution context----+
    | i = 0                                        |
    | ....                                         |
    | slate.push(char)                             |
    | helper(arr, res, i+1, slate);                |
    |      +---nested helper execution context---+ |
    |      | i = 1                               | |
    |      | ....                                | |
    |      | slate.push(char)                    | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +--deepest exec. context-----+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      | slate.pop()                         | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +----------------------------+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      +-------------------------------------+ |
    | // i is still 0                              |
    | slate.pop()                                  |
    | helper(arr, res, i+1, slate);                |
    |      +-------------------------------------+ |
    |      | i = 1                               | |
    |      | ....                                | |
    |      | slate.push(char)                    | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +----------------------------+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      | slate.pop()                         | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +----------------------------+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      +-------------------------------------+ |
    | // i is still 0                              |
    +----------------------------------------------+

所以我们看到，在这个特定的算法中，调用堆栈的大小（即递归树的深度）正好对应于变量的值i 在当前执行上下文中。当函数 returns 时，调用堆栈的大小减小（即递归 depth 减小），因此我们到达一个状态（从堆栈中弹出）是 i 的另一个实例，它的值也与调用堆栈的当前当前大小相匹配。

Answer 2

Trincot 就该功能的内部运作方式给出了有用的详细回复。我只想指出一个重要的简化，您可以这样写：

const getSpellableWords = ([x, ...xs]) => 
  x == undefined
    ? ['']
    : ((ps = getSpellableWords (xs)) => [...ps .map (p => x + p), ...ps]) ()

console .log (
  getSpellableWords (['A', 'T', 'C', 'K'])
)

.as-console-wrapper {max-height: 100% !important; top: 0}

这里我们注意到，我们可以创建的单词要么包含第一个字符，要么不包含。我们可以递归地计算余数中的所有单词，然后 return 将该单词数组与通过将第一个字符添加到每个单词之前找到的单词组合的结果。当然，如果没有剩余字符，我们的递归就会触底，其中我们的数组 returned 只包含空字符串。

这里有一点语法上的欺骗，在递归分支中有一个 IIFE。我们可能更喜欢使用 call 辅助函数，它接受一个函数和任何参数，并使用这些参数调用该函数。有时这更清楚：

const call = (fn, ...args) => fn (...args)

const getSpellableWords = ([x, ...xs]) => 
  x == undefined
    ? ['']
    : call (
        (ps) => [...ps .map (p => x + p), ...ps],
        getSpellableWords (xs)
      )

何时在 Javascript 中设置调用堆栈？

When does the call stack get set up in Javascript?

javascript

arrays

recursion

callstack

backtracking