javascript - 递归函数 : returning null

Question

这个来自 Eloquent JavaScript 的特殊难题已在 SO 的其他地方被问到，但我还没有找到与我引用它的具体问题相关的难题。

function findSolution(target) {
  function find(start, history) {
    if (start == target)
      return history;
    else if (start > target)
      return null;
    else
      return find(start + 5, `(${history} + 5)`) ||
             find(start * 3, `(${history} * 3)`);
  }
  return find(1, "1");
}

console.log(findSolution(13));
// (((1 * 3) + 5) +5)

...这是调用堆栈:

find(1, "1")
  find(6, "(1 + 5)")
    find(11, "((1 + 5) + 5)")
      find(16, "(((1 + 5) + 5) + 5)")
        too big
      find(33, "(((1 + 5) + 5) * 3)")
        too big
    find(18, "((1 + 5) * 3)")
      too big
  find(3, "(1 * 3)")
    find(8, "((1 * 3) + 5)")
      find(13, "(((1 * 3) + 5) + 5)")
        found!

我的问题与 return null; 在这里的工作方式有关。我想更好地理解此语句如何导致 find() 返回先前计算的 target 参数；例如，find(33, .. --> find(18, .. --> find(3, ..。我明白了find(11 + 5, .. 如何将调用传递给 find(11 * 3 ..，但我不明白 find(11 * 3 .. 将调用传递给 find(6 * 3, ..，然后传递给 find(1 * 3, ..，就像上面的调用堆栈一样表示。

Answer 1

I understand how find(11 + 5, .. passes the call to find(11 * 3 .., but I don't understand how find(11 * 3 .. passes the call to find(6 * 3, .. and then to find(1 * 3, ..

首先请注意，find 可能返回两种类型的内容:(非空)字符串(history)或null。第一个是真值，第二个是假值。

您了解 find(16, "(((1 + 5) + 5) + 5)") 返回 null 并且 的另一部分code>||-expression 被评估，即 find(33, "(((1 + 5) + 5) * 3)")。

就像||的左边部分可以返回null一样，它的右边部分也可以返回null。在那种情况下，整个表达式返回 null 给“parent”调用，它也是从这样的 || 表达式生成的。

所以你真的在那里发生了同样的事情，但在递归树中更高一级。以上是在更高级别 find(11, "((1 + 5) + 5)") 执行时发生的。它最终返回了 null || null，即 null，然后(在更高级别)它转到其自身 || 表达式的另一侧并计算 find (18, "((1 + 5) * 3)")。这也返回 null(这次是立即返回)。所以我们又得到了 null || null，并回溯(就是这个词!)到递归树中的更高级别。

“父级”

递归意味着 - 当函数正在执行时 - 对同一函数进行新的调用。我将 parent 称为进行递归调用的函数执行，它正在等待该调用返回一个返回值。

那个 child 也可能成为一个更嵌套的孙 调用的 parent 。所以你有一堆未完成的函数执行。当最深的那些返回一个值时，它“上方”的那个将“醒来”并接收该值:然后它可以继续并进行另一个子调用，并且重复类似的场景。如果它没有更多这样的调用要进行，它将返回一个值给它的父级(回溯)，它一直在等待递归调用返回一个值。

将整个递归过程想象成一个堆栈。当某些代码调用此函数时，调用者的执行上下文 被压入堆栈，然后继续执行函数。此执行上下文包含启动代码从进行函数调用的那一点开始所需的一切。它具有变量及其值、代码中进行函数调用的确切位置、传递给该函数调用的参数等。

然后该函数可能会调用自身，因此其自己的 执行上下文再次被压入堆栈(“调用堆栈”)，因此堆栈可能会增长。但在某个时刻，该函数将返回一个值，并且堆栈展开:恢复先前的执行上下文，并且 parent 将从它进行递归调用的地方继续执行。当此调用堆栈为空时，执行结束。