时间戳

首页 > 解决方案 > 递归函数：返回 null

javascript - 递归函数：返回 null

问题描述

这个来自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, ..，正如上面的调用堆栈似乎表明的那样。

标签： javascriptrecursion

解决方案

我了解find(11 + 5,.. 如何将调用传递给find(11 * 3..，但我不明白find(11 * 3.. 如何将调用传递给find(6 * 3, .. 然后传递给find(1 * 3, ..

首先请注意，有两种类型的东西find可能会返回：（非空）字符串 ( history) 或null. 第一个是真值，第二个是假值。

您了解find(16, "(((1 + 5) + 5) + 5)")返回null，因此 - 表达式的另一部分||被评估，即find(33, "(((1 + 5) + 5) * 3)").

就像左边||可以返回一样null，右边也可以返回null。在这种情况下，整个表达式返回null到“父”调用，该调用也是由这样的||表达式生成的。

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

“家长”

递归意味着——在函数执行时——对同一函数进行新的调用。我调用父函数执行递归调用并等待该调用返回一个返回值。

该孩子也可能成为更嵌套的孙子电话的父母。所以你有一堆未完成的函数执行。当其中最深的返回一个值时，“上方”的那个将“唤醒”并接收该值：然后它可以继续并进行另一个子调用，并且类似的场景会重复。如果它不再需要进行此类调用，它将向其父级返回一个值（回溯），它一直在等待递归调用返回一个值。

将整个递归过程想象成一个堆栈。当一些代码调用这个函数时，调用者的执行上下文被压入堆栈，继续执行函数。这个执行上下文保存了启动代码从它进行函数调用的那一点开始所需的一切。它有带有值的变量，在代码中进行函数调用的确切位置，传递给该函数调用的参数等等。

然后函数可能会调用自己，因此它自己的执行上下文再次被压入堆栈（“调用堆栈”），因此堆栈可能会增长。但是在某些时候，函数将返回一个值，堆栈展开：先前的执行上下文被恢复，并且该父级将继续从它进行递归调用的位置执行。当此调用堆栈被清空时，执行结束。

推荐阅读