javascript - 有人可以解释一下这个递归代码是如何工作的吗？

Question

function findSequence(goal) {
  function find(start, history) {
    if (start == goal)
      return history;
    else if (start > goal)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

findSequence(24);

这来自 Eloquent JavaScript。它的目的是“给定一个数字，试图找到产生该数字的加法和乘法序列”。

我已经在 Chrome 中运行了调试器，当运行带有数字 24 的函数时，我在 start 变量上得到了这个堆栈。我试图具体了解 start 随着它的变化而变化。

1. 开始 = 1 - 加 5。
2. start = 6 - 加 5。
3. start = 11 - 加 5。
4. start = 16 - 加 5。
5. start = 21 - 加 5。
6. start = 26。大于 24。返回 null。开始返回 21。尝试乘以 3。
7. start = 63。大于 24。返回 null。开始回到 21。

正是在这一点上，start 从 21 变为 16。这是为什么？我在代码中看不到任何可以使它恢复正常的内容。它对 16 重复此操作，乘以 3，返回到 16，然后返回到 11。我真的很想知道这里发生了什么。

Answer 1

1
+ 5 -- 6
       + 5 -- 11
               + 5 -- 16
                       + 5 -- 21
                               + 5 -- 26 > 24, returns null
                               x 3 -- 63 > 24, returns null
                       x 3 -- 38
...
...

这就是正在发生的事情。你在递归中更深入。你去了一个没有前进的地方。所以，你回到当前状态之前的地方。这就是为什么当您无法继续 21 时，递归展开并让您从 16 继续另一条路径。这就是为什么 start 又是 16。