这种递归如何工作？

Question

这是Eloquent Javascript的一个例子:

从数字1开始并重复加5或乘3,可以产生无限量的新数.你会如何编写一个函数,给定一个数字,试图找到一个产生该数字的加法和乘法序列？

我无法理解递归在这里如何工作,想知道是否有人可以写出几次如何调用查找或其他解释.

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");
}

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3)

Answer 1

该函数使用回溯运行一个相当简单的强力搜索:在每个调用级别,它尝试添加到数字,并查看从结果数字开始是否使您达到目标.如果是,则返回结果; 否则,将该数字乘以,并从该新数字继续搜索目标.随着递归的进行,产生数字的表达式的文本表示将传递给下一个调用级别.53

搜索14如下:

(1,  "1")
(5,  "1+5")
(10, "(1+5)+5")
(15, "((1+5)+5)+5") <<= Fail
(30, "((1+5)+5)*3") <<= Fail
(15, "(1+5)*3") <<= Fail
(3,  "1*3")
(8,  "(1*3)+5")
(13, "((1*3)+5)+5")
(18, "(((1*3)+5)+5)+5") <<= Fail
(39, "(((1*3)+5)+5)*3") <<= Fail
(24,  "((1*3)+5)*3") <<= Fail
(9, "(1*3)*3")
(14, "((1*3)*3)+5) <<= Success!