5

这是 Eloquent Javascript 的一个例子：

通过从数字 1 开始，反复加 5 或乘以 3，可以产生无限数量的新数字。你将如何编写一个函数，给定一个数字，试图找到产生该数字的一系列加法和乘法？

我无法理解递归是如何在这里工作的，想知道是否有人可以写出几次 find 是如何被调用的或其他一些解释。

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)
4

11 回答 11

10

该函数使用回溯运行一个相当简单的蛮力搜索：在每个调用级别，它尝试添加到数字，并查看是否从结果数字开始让您到达目标。如果是，则返回结果；否则，该数字将乘以，然后从该新数字继续搜索目标。随着递归的进行，产生数字的表达式的文本表示被传递到下一个调用级别。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!
于 2013-03-29T22:19:32.353 回答
4

您只需创建调用树即可解决此问题：

findSequence(24)
    find(1, "1")
       find(1 + 5, "(1 + 5)")
           find(6 + 5, "((1 + 5) + 5)")
               find(11 + 5, "(((1 + 5) + 5) + 5)"
                   find(16 + 5, "((((1 + 5) + 5) + 5) + 5)"
                       find(21 + 5, "(((((1 + 5) + 5) + 5) + 5) + 5)"
                          start > goal: return null
                       find(21 * 3, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
                          start > goal: return null
                   find(16 * 3, "((((1 + 5) + 5) + 5) * 3)"
                       start > goal: return null
               find(11 * 3, "(((1 + 5) + 5) * 3)"
                   start > goal: return null
           find(6 * 3, "((1 + 5) * 3)")
               find(18 + 5, "(((1 + 5) * 3) + 5)")
                   find(23 + 5, "((((1 + 5) * 3) + 5) + 5)")
                       start > goal: return null
                   find(23 * 3, "((((1 + 5) * 3) + 5) * 3)")
                       start > goal: return null
               find(18 * 3, "(((1 + 5) * 3) * 3)")
                   start > goal: return null
       find(1 * 3, "(1 * 3)") 
           find(3 + 5, "((1 * 3) + 5)")
               find(8 + 5, "(((1 * 3) + 5) + 5)")
                   find(13 + 5, "((((1 * 3) + 5) + 5) + 5)")
                       find(18 + 5, "(((((1 * 3) + 5) + 5) + 5) + 5)")
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                       find(18 * 3, "(((((1 * 3) + 5) + 5) + 5) * 3)")
                           start > goal: return null
                   find(13 * 3, "((((1 * 3) + 5) + 5) * 3)")
                       start > goal: return null
               find(8 * 3, "(((1 * 3) + 5) * 3)")
                   return "(((1 * 3) + 5) * 3)"
           find(3 * 3, "((1 * 3) * 3)")
               find(9 + 5, "(((1 * 3) * 3) + 5)")
                  find(14 + 5, "((((1 * 3) * 3) + 5) + 5)")
                      find(19 + 5, "(((((1 * 3) * 3) + 5) +5) + 5)")
                         return "(((((1 * 3) * 3) + 5) +5) + 5)"
                      find(19 * 3, "((((1 * 3) * 3) + 5) *3)")
                          start > goal: return null
               find(9 * 3, "(((1 * 3) * 3) * 3)")
                    start > goal: return null
于 2013-03-29T22:37:57.333 回答
2

简单来说，find(start,goal)只要goal没有达到值就会递归调用。在每次调用中，当前数字将乘以 3 或增加 5。history变量存储执行操作的字符串。当前操作在每次迭代中附加到该字符串。

解释：

function findSequence(goal) {

  // This inner function will be called recursively.
  // 'history' is a string with the current operations "stack"
  function find(start, history) {
    if (start == goal)           // if goal is achieved, simply return the result
                                 // ending the recursion
      return history;
    else if (start > goal)       // return null to end the recursion
      return null;
    else
      // One of the 'find' calls can return null - using ||
      // ensures we'll get the right value.
      // Null will be returned if 'start+5' or 'start*3' is
      // greater than our 'goal' (24 in your example).
      // The following line is where a recursion happens.
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }

  // Start with '1'
  return find(1, "1");
}
于 2013-03-29T22:19:01.433 回答
2

了解这一点的最佳方法是跟踪 JavaScript 调试器中的代码。

你以前用过调试器吗？这真的很有趣，很有启发性，也很容易。

只需debugger;在您希望代码停止的地方添加一条语句。一个好地方就在你打电话之前findSequence()：

debugger;
console.log(findSequence(24));

现在在打开开发者工具的情况下在 Chrome 中加载您的页面。debugger;您的代码将在该行停止。找到让您进入代码的按钮（在 Watch Expressions 面板的右上方）。单击该按钮以进入findSequence()通话。每次单击它，它都会进入下一行代码，其中包括进入每个递归调用。

每当代码停止时，您可以将鼠标悬停在任何变量上以查看它，或查看右侧面板中的变量。还有一个调用堆栈可以准确地显示你在递归调用中的位置。

我相信有人可以向您解释递归，但是如果您通过在调试器中逐步执行代码来实际体验它，您将学到更多。

于 2013-03-29T22:20:38.940 回答
1

此函数从 1 开始，然后尝试将 5 添加到它或将其乘以 3。如果等于目标，则函数终止并打印出找到的表达式。如果不是，它会使用该级别的值递归调用自身，直到找到匹配项或直到值变得太高。

这有帮助吗？

于 2013-03-29T22:17:10.877 回答
1

有人可以写出几次 find 是如何被调用的。

干得好：

find(1, "1") -> find(3, "(1 * 3)")
             -> find(8, "((1 * 3) + 5)")
             -> find(24, "(((1 * 3) + 5) * 3)")
于 2013-03-29T22:17:57.397 回答
1

想想像二叉树一样加 5 和乘以 3 的无限组合。顶部是最容易计算的数字1（实际上是“无需步骤”的答案）。下一层，左边是1+5，右边是1*3。在每个级别，方程解析为一个新值（具有更复杂的历史）。这个等式在该树中导航，直到找到一个等于goal. 如果树的分支上的节点产生的值大于您的目标，则它返回 null （从而停止该分支的进一步回避，这是因为这两个操作都只会增加该值，因此一旦您最终大于没有点继续查找），如果一个节点的值等于目标，那么它作为答案返回（连同它用来到达那里的路径）。当该值小于时，两条路径都可能保留答案，因此它在每个路径上调用 find。这就是 JavaScript 的“真实”布尔逻辑的用武之地。通过使用||(OR) 运算符，JavaScript 将首先查看+5树的一侧。如果返回 0 或 null，则将执行另一个调用（向下看*3）。如果任何回报评估为非false值然后它将返回堆栈并且搜索将结束。

于 2013-03-29T22:19:19.873 回答
1

的主体find有三个退出路径，两个对应于停止递归的条件，一个对应于递归：

if (start == goal)
  return history; // stop recursion: solution found
else if (start > goal)
  return null;    // stop recursion: solution impossible
else
  // ...

第三条路径实际上是一个“分支”，因为它递归两次（一次尝试加法，一次尝试乘法）：

  return find(start + 5, "(" + history + " + 5)") ||
         find(start * 3, "(" + history + " * 3)");

那么这里发生了什么？

首先，请注意，这两个find调用中的每一个都将评估为非空字符串（操作历史）或null. 由于非空字符串是“真”值并且null是“假”值，因此我们通过将它们与运算符连接来利用这一点||；如果该运算符为真，则计算其第一个操作数，否则计算第二个操作数。

这意味着将首先评估第一个递归分支 (+5)。如果有一个以加 5 开始并达到目标的操作序列，则返回该序列的描述。否则，如果有一个以乘以 3 开始并达到目标的序列，则将返回该历史的描述。

如果无法达到目标，则返回值将由null第二个分支产生。

于 2013-03-29T22:19:54.673 回答
1

如果您摆脱漂亮的打印内容，代码会更容易阅读：

function findSequence(goal) {
    function find(start) {
        if (start == goal) {
            return true;
        } else if (start > goal) {
            return false;
        } else {
            return find(start + 5) || find(start * 3);
        }
    }

    return find(1);
}

外部函数findSequence动态创建一个名为where的新函数，该函数取自父函数的作用域。为了清楚起见，您可以像这样重写它：findgoal

function findSequence(start, goal) {
    if (start == goal) {
        return true;
    } else if (start > goal) {
        return false;
    } else {
        return findSequence(start + 5, goal) || findSequence(start * 3, goal);
    }
}

现在，您可以更清楚地看到发生了什么。递归步骤在最后的return语句中，它在每一步都尝试start + 5并start * 3选择最终返回的分支true。

遵循findSequence(1, 23)手工的逻辑，你就会明白它是如何工作的。

于 2013-03-29T22:23:20.433 回答
1

让我们留下历史参数，我们稍后再谈。

递归扩展到所有可能的操作。它以值1as开头start。

  1. 我们首先检查我们是否到达了目的地：goal如果我们确实返回true了，则意味着我们走的路是正确的。

  2. 其次，我们问——我们是否超过了界限（goal）？如果我们这样做了，我们应该返回，false因为这条路对我们没有帮助。

  3. 否则，让我们尝试我们的两种可能性（我们使用 OR，因为我们至少需要一种）：

    • 调用相同的函数，但设置start为start + 5
    • 调用相同的函数，但设置start为start * 3

历史变量保持我们采取的步骤。因此，如果函数调用标识start == goal它返回它。

于 2013-03-29T22:24:27.950 回答
1

goal是你的目标，它设置为 24

goal == 24

现在我们有了这个内部函数find()来检查是否start等于 24；它不是。它还会检查 start 是否大于 24 这也是不正确的，

find(1 "1")
1 == 24 //false
1 > 24 //false

所以它会再次调用 find 的 else 语句，这就是else if()来自 in 的空值的来源。如果返回为空，那么它调用 || 部分，直到它最终找到正确的答案。

return find(6, "(1 + 5)")
       find(11, "((1 + 5) + 5)")
       find(16, "(((1 + 5) + 5) +5)")
       find(21, "((((1+5) + 5) + 5) +5)")
       //next one returns null!
       //tries * by 3 on 21, 16, and 11 all return null

所以它切换到 ||

return find(3, "(1 * 3)")
       find(8, "((1 * 3) +5)")
       //some calls down +5 path but that returns null
       find(24, "(((1 * 3) + 5) * 3)")

最后！我们有一个真正的回报，我们已经记录了我们在历史变量中所走的路径。

于 2013-03-29T22:37:36.183 回答