我试着理解这个递归代码，现在已经被困住了

Question

我想我已经掌握了Javascript中的递归，但希望在我正在阅读的一本书中对具体的递归代码有一些清晰的了解。

正如我所理解的，下面的代码正在进行几个步骤，如果您能够纠正我理解中的任何错误，我将非常感激：

• findSolution函数正在寻找一个解决方案，您可以在其中添加5或乘以3才能得到24。
• 函数find是递归碰巧找到该解决方案的地方，if (start == target)语句告诉递归在找到解决方案时结束，并返回这种情况的历史记录。
• 第8-9行中的返回语句以等于6的(1 + 5)开头，因此它从最前面的if语句开始，通过不满足的if语句，然后再继续返回语句，这次是(6 + 5)，等于11。
• 它一直进行到满足其中一个if语句为止。当start高于目标时，该函数就会继续运行，然后转到另一边，从(1 * 3)开始，历史记录等于"(1 * 3)“。

我不确定的是，为什么函数在下一次迭代中通过第一部分将5添加到(1 * 3)，函数如何知道添加5，然后在下一次迭代中乘以3？为什么它不继续添加5，然后这样做，直到它太大并返回null？

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(24));
// → (((1 * 3) + 5) * 3)

Answer 1

也许这让我们更清楚地知道了发生了什么。

我刚刚向depth-argument添加了一个find-function以确定递归深度，并添加了一个console.log()来记录所有递归调用。

​

function findSolution(target) {
    //added a depth-property to show the recursion better
    function find(start, history, depth) {
        //simply log all calls in order
        console.log("%s%d == %s", "|  ".repeat(depth), start, history);

        if (start == target)
            return history;
        else if (start > target)
            return null;
        else
            return find(start + 5, "(" + history + " + 5)", depth+1) ||
                   find(start * 3, "(" + history + " * 3)", depth+1);
    }
    return find(1, "1", 0);
}

console.log(findSolution(24));

​

Answer 2

其实你提到的每一个可能的案子都经过了。它继续添加5，直到它太大并返回null (在本例中为find(start + 5, "(" + history + " + 5)") === null (false) )，因此结果将来自另一个分支。

这真的很难解释，因为你需要理解执行堆栈，或者画一棵执行树。让我知道我能帮上什么忙

Answer 3

下面是您的代码的一个版本，它将为您打印一个执行树，以便您可以跟随算法实际上正在尝试的所有不同排列：

function findSolution(target) {
  function find(start, history, trace) {
    trace.push(history)
    if (start == target) {
      console.log(trace.join(' => ') + ' => ' + start + ' == ' + target);
      return history;
    }
    if (start > target) {
      console.log(trace.join(' => ') + ' => ' + start + ' > ' + target);
      return null;
    }
    return find(start + 5, "(" + history + " + 5)", [].slice.call(trace)) ||
           find(start * 3, "(" + history + " * 3)", [].slice.call(trace));
  }
  return find(1, "1", []);
}
findSolution(24)

下面是执行树：

1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) + 5) => ((((1 + 5) + 5) + 5) + 5) => (((((1 + 5) + 5) + 5) + 5) + 5) => 26 > 24
1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) + 5) => ((((1 + 5) + 5) + 5) + 5) => (((((1 + 5) + 5) + 5) + 5) * 3) => 63 > 24
1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) + 5) => ((((1 + 5) + 5) + 5) * 3) => 48 > 24
1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) * 3) => 33 > 24
1 => (1 + 5) => ((1 + 5) * 3) => (((1 + 5) * 3) + 5) => ((((1 + 5) * 3) + 5) + 5) => 28 > 24
1 => (1 + 5) => ((1 + 5) * 3) => (((1 + 5) * 3) + 5) => ((((1 + 5) * 3) + 5) * 3) => 69 > 24
1 => (1 + 5) => ((1 + 5) * 3) => (((1 + 5) * 3) * 3) => 54 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) + 5) => (((((1 * 3) + 5) + 5) + 5) + 5) => ((((((1 * 3) + 5) + 5) + 5) + 5) + 5) => 28 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) + 5) => (((((1 * 3) + 5) + 5) + 5) + 5) => ((((((1 * 3) + 5) + 5) + 5) + 5) * 3) => 69 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) + 5) => (((((1 * 3) + 5) + 5) + 5) * 3) => 54 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) * 3) => 39 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) * 3) => 24 == 24