这个递归函数如何改变“历史"变量? [英] How Is This Recursive Function Changing The 'history' Variable?

问题描述

我觉得很接近解决这个问题，但我不太明白这个功能..

I feel so close to figuring this out, but I can't quite understand this function..

我知道函数如何不断检查目标数字，如果它太高，它会返回 null 和第二个||"运算符被应用.

I get how the function keeps checking for the target number and if it gets too high, it returns null and the second '||' operator is applied.

我不明白的是，一旦当前变量高于目标变量，它将开始返回历史变量但没有额外的(+5).这是怎么从字符串中取出来的??????

What I do not understand is, once the current variable is higher than the target variable, it will start returning the history variable but without an additional (+5). How is this being taken out of the string?????

任何解释将不胜感激.希望这是有道理的.我从 Marijn Haverbeke 的 Eloquent Javascript 一书中获取了这一点

Any explanation would be greatly appreciated. Hopefully this makes sense. I am taking this from the book, Eloquent Javascript by Marijn Haverbeke

function findSolution(target) {
  function find(current, history) {
    if (current == target) {
      return history;
    } else if (current > target) {
      //console.log(`CURRENT AT NULL: ` + current);
      console.log(`HISTORY AT NULL:  ${history}`);
      return null;

    } else {
      console.log(`${history}`);
      return find(current + 5, `(${history} + 5)`) ||
        find(current * 3, `(${history} * 3)`);
    }
  }
  return find(1, "1");
}
console.log(findSolution(24));

// → (((1 * 3) + 5) * 3)

推荐答案

您正在通过递归进行所谓的深度优先搜索.每个人对递归的理解略有不同.某些东西最终会让它为您点击.

You are doing what's called a depth-first search via recursion. Everyone groks recursion a little differently. Something will eventually make it click for you.

我想在您的代码中做几个注释，以帮助它打印出更自然的记录.希望这会有所帮助.

I'd like to make a couple of annotations in your code that help it print out a more natural transcript of what transpires. Hopefully that will help some.

但我认为最重要的是通过缩进可视化您在递归中的深度.当您在递归深度优先搜索期间记录时，您基本上是在制作一个二叉树，其输出如下:

But I think the most important thing is to visualize how many levels deep in the recursion you are with some indenting. When you log during a recursive depth-first search, you are basically making a binary tree where the output is like:

Root
   Root > Left
   Root > Right

它开始嵌套这样的递归:

And it starts to nest with recursion like this:

Root
   Root > Left
      Root > Left > Left
      Root > Left > Right
   Root > Right
      Root > Right > Left
      Root > Right > Right

您正在创建探索的+5"和*3"分支，而不是左"和右"路径.在您的递归中，您首先探索树的 +5 分支以寻找解决方案.如果没有找到，则探索树的 *3 分支.当什么都没有找到时，这只是意味着答案不在您正在考虑的分支上，并且必须在树的早期做出不同的选择.

And instead of "Left" and "Right" paths, you are creating "+5" and "*3" branches of exploration. In your recursion you explore the +5 branch of the tree first looking for a solution. If you don't find it, then you explore the *3 branch of the tree. When nothing is found, it just means that the answer does not lie on the branch you are considering and a different choice earlier in the tree must be made.

当两种途径都尝试但都没有成功时，似乎会发生一些回溯.但实际上这只是一个假设的结论，我们说如果我们+5，我们能到达那里吗?"或者如果我们*3，我们能到达那里吗?"如果两者的答案都是否定的，那么你就是无法从你所在的地方到达那里.您实际上不必回溯，递归的美妙之处在于您可以在搜索中找到自己的位置，因为有人将您作为假设……"的一部分调用.如果您的整个搜索结果都是空的，没问题.您只需放弃当前的搜索分支，调用您的某人"将在不同的分支上尝试其他内容.

Some back-tracking appears to occur when both avenues are tried and neither succeeds. But really it's just a conclusion of a hypothesis made where we say "can we get there if we +5?" or "can we get there if we *3?" If the answer is no to both, then you just can't get there from where you are. You don't have to actually back-track, the beauty of recursion is that you got where you are in the search because someone invoked you as part of a "what if...". If your entire search comes up empty, no problem. You just abandon your current branch of the search and the "someone" that invoked you will try something else on a different branch.

您的递归状态(您正在探索的分支)保存在您的调用堆栈中.那才是我们真正备份"的地方.

The state of your recursion (which branch you are exploring) is kept on your call stack. That's where we actually "back up".

history 永远不会被修改.我们只是探索通过递归构造的不同版本的 history.每个 history 都是它自己的副本，它只会变长(搜索树中的左分支或右分支)或被放弃，然后从其他位置的其他 history 继续搜索递归.

history is never modified. We just explore different versions of history that are constructed via recursion. Each history is its own copy and it only ever gets longer (a left or right branch in the search tree) or gets abandoned and the search continues from some other history elsewhere in the recursion.

所以这是您的代码，其中包含一些缩进和对每一步发生的事情的一些冗长描述，希望能更紧密地与递归联系起来.

So here's your code with some indenting and some wordy descriptions of what's going on at each step that hopefully ties back to the recursion a little more closely.

function spaces(indent) {
  return '    '.repeat(indent);
}

function findSolution(target) {
  function nope(indent, history) {
    console.log(spaces(indent) + `Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to ${target}, but not by starting from ${history}.`);
    return false;
  }
  function badnews(history) {
    console.log(`I've tried everything and there's just no way of getting to ${target}.  :(`);
    return false;
  }
  function find(current, which, history, indent) {
    if (current == target) {
      console.log(spaces(indent) + `${which}, and guess what...we finally found a solution! Because ${history} = ${current}.  So we can stop now. :)`);
      return history;
    } else if (current > target) {
      //console.log(`CURRENT AT NULL: ` + current);
      console.log(spaces(indent) + `${which}, we reached a dead end because ${history} = ${current} which is unfortunately already bigger than ${target}.`);
      return null;

    } else {
      console.log(spaces(indent) + `${which}, ${history} looks promising because it equals ${current}, which is still less than ${target}.  We'll try two ways of getting to ${target} from here.`);
      return find(current + 5, 'First, by adding 5', `(${history} + 5)`, indent+1) ||
        find(current * 3, 'Second, by multiplying by 3', `(${history} * 3)`, indent+1) ||
        nope(indent+1, history);
    }
  }
  return find(1, 'Initially', "1", 0) || badnews();
}
console.log(`${findSolution(24)}`);

输出复制如下，以防万一.抱歉，没有对输出进行包装，因为缩进更重要，因此您可以查看递归的深度，以及导致回溯的原因.如果您发现代码段控制台输出更具可读性，则可以运行该代码段.

Output is copied below, just in case. Sorry, there's no wrapping of the output because indenting is more important so you can see how many levels deep in the recursion you are, and what causes a back-track. You can run the snippet if you find the snippet console output more readable.

Initially, 1 looks promising because it equals 1, which is still less than 24.  We'll try two ways of getting to 24 from here.
    First, by adding 5, (1 + 5) looks promising because it equals 6, which is still less than 24.  We'll try two ways of getting to 24 from here.
        First, by adding 5, ((1 + 5) + 5) looks promising because it equals 11, which is still less than 24.  We'll try two ways of getting to 24 from here.
            First, by adding 5, (((1 + 5) + 5) + 5) looks promising because it equals 16, which is still less than 24.  We'll try two ways of getting to 24 from here.
                First, by adding 5, ((((1 + 5) + 5) + 5) + 5) looks promising because it equals 21, which is still less than 24.  We'll try two ways of getting to 24 from here.
                    First, by adding 5, we reached a dead end because (((((1 + 5) + 5) + 5) + 5) + 5) = 26 which is unfortunately already bigger than 24.
                    Second, by multiplying by 3, we reached a dead end because (((((1 + 5) + 5) + 5) + 5) * 3) = 63 which is unfortunately already bigger than 24.
                    Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((((1 + 5) + 5) + 5) + 5).
                Second, by multiplying by 3, we reached a dead end because ((((1 + 5) + 5) + 5) * 3) = 48 which is unfortunately already bigger than 24.
                Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((1 + 5) + 5) + 5).
            Second, by multiplying by 3, we reached a dead end because (((1 + 5) + 5) * 3) = 33 which is unfortunately already bigger than 24.
            Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((1 + 5) + 5).
        Second, by multiplying by 3, ((1 + 5) * 3) looks promising because it equals 18, which is still less than 24.  We'll try two ways of getting to 24 from here.
            First, by adding 5, (((1 + 5) * 3) + 5) looks promising because it equals 23, which is still less than 24.  We'll try two ways of getting to 24 from here.
                First, by adding 5, we reached a dead end because ((((1 + 5) * 3) + 5) + 5) = 28 which is unfortunately already bigger than 24.
                Second, by multiplying by 3, we reached a dead end because ((((1 + 5) * 3) + 5) * 3) = 69 which is unfortunately already bigger than 24.
                Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((1 + 5) * 3) + 5).
            Second, by multiplying by 3, we reached a dead end because (((1 + 5) * 3) * 3) = 54 which is unfortunately already bigger than 24.
            Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((1 + 5) * 3).
        Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (1 + 5).
    Second, by multiplying by 3, (1 * 3) looks promising because it equals 3, which is still less than 24.  We'll try two ways of getting to 24 from here.
        First, by adding 5, ((1 * 3) + 5) looks promising because it equals 8, which is still less than 24.  We'll try two ways of getting to 24 from here.
            First, by adding 5, (((1 * 3) + 5) + 5) looks promising because it equals 13, which is still less than 24.  We'll try two ways of getting to 24 from here.
                First, by adding 5, ((((1 * 3) + 5) + 5) + 5) looks promising because it equals 18, which is still less than 24.  We'll try two ways of getting to 24 from here.
                    First, by adding 5, (((((1 * 3) + 5) + 5) + 5) + 5) looks promising because it equals 23, which is still less than 24.  We'll try two ways of getting to 24 from here.
                        First, by adding 5, we reached a dead end because ((((((1 * 3) + 5) + 5) + 5) + 5) + 5) = 28 which is unfortunately already bigger than 24.
                        Second, by multiplying by 3, we reached a dead end because ((((((1 * 3) + 5) + 5) + 5) + 5) * 3) = 69 which is unfortunately already bigger than 24.
                        Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((((1 * 3) + 5) + 5) + 5) + 5).
                    Second, by multiplying by 3, we reached a dead end because (((((1 * 3) + 5) + 5) + 5) * 3) = 54 which is unfortunately already bigger than 24.
                    Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((((1 * 3) + 5) + 5) + 5).
                Second, by multiplying by 3, we reached a dead end because ((((1 * 3) + 5) + 5) * 3) = 39 which is unfortunately already bigger than 24.
                Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((1 * 3) + 5) + 5).
            Second, by multiplying by 3, and guess what...we finally found a solution! Because (((1 * 3) + 5) * 3) = 24.  So we can stop now. :)
(((1 * 3) + 5) * 3)

这篇关于这个递归函数如何改变“历史"变量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！