来自 Eloquent Javascript 的 Javascript 递归 [英] Javascript recursion from Eloquent Javascript

问题描述

所以这是来自 Eloquent Javascript.我想弄清楚这段代码是如何实际执行的.所以我们试图找到一种方法，通过加 5 或乘以 3 来达到目标​​数字，我们从数字 1 开始.数字?例如，先乘以 3 再乘以 5 可以达到数字 13，而数字 15 则根本达不到.

So this is from the Eloquent Javascript. I am trying to figure out how this code is actually stepped through. So we are trying to find a way to reach the target number by adding either 5 or multiplying by 3, and we start from the number 1. So, essentially, we are trying to find a sequence of such additions and multiplications that produce the target number? For example, the number 13 could be reached by first multiplying by 3 and then adding 5 twice, whereas the number 15 cannot be reached at all.

这是代码片段:

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)

显然这就是我们调用 findSolution(13) 时发生的情况:

Apparently this is what happens when we call findSolution(13):

为了更好地理解这个函数如何产生我们正在寻找的效果，让我们看看在搜索数字 13 的解时对 find 的所有调用.

To better understand how this function produces the effect we’re looking for, let’s look at all the calls to find that are made when searching for a solution for the number 13.

find(1, "1")
  find(6, "(1 + 5)")
    find(11, "((1 + 5) + 5)")
      find(16, "(((1 + 5) + 5) + 5)")
        too big
      find(33, "(((1 + 5) + 5) * 3)")
        too big
    find(18, "((1 + 5) * 3)")
      too big
  find(3, "(1 * 3)")
    find(8, "((1 * 3) + 5)")
      find(13, "(((1 * 3) + 5) + 5)")
        found!

问题:
1) 我很困惑当我们调用 findSolution(13) 时会发生什么.当我没有提供开始或历史编号时，第一行是如何找到 (1, "1") 的?代码如何直接下线:

Question:
1) I am confused what happens when we call findSolution(13). How is it that the first line is find (1, "1") when I haven't supplied it either the start or history number? How does the code just step down to line:

return find(1,"1")

代码如何到达那里?
2)这是OR语句在递归中的操作方式吗?在递归检查中，Javascript 通常会在处理第二个分支之前探索 OR 语句的第一个分支吗?这条线是:

How does the code get there?
2) Is this how OR statements operate in recursion? In a recursive check, does Javascript typically explore the first branch of the OR statement before tackling the second branch? Is this line:

find(3, "(1 * 3)")  

仅在以下所有分支之后检查:

only checked after the all of the branches of:

find(6, "(1 + 5)")

未能返回解决方案?

推荐答案

1) 如果你看代码，findSolution"函数由两部分组成:一个方法定义find"，以及对该方法的调用返回查找(1，1")".除非被调用，否则定义本身不会产生计算.因此，实际执行的第一个表达式是find(1, "1")".这是起点.

1) If you look at the code, the function "findSolution" is composed of two parts: a method definition "find", and a call to that method "return find(1, "1")". The definition, in itself, won't produce computing unless it is called. So, the first expression that is actually executed is "find(1, "1")". It's the starting point.

2) OR 语句是按照它们的阅读顺序执行的，所以find(start + 5, ...)"将首先执行，然后只有当它确实返回null(即它没有找到解决方案)将执行下一条语句find(start * 3, ...)".由于递归，您可以在执行*3"之前执行任意数量的+5"，这当然取决于目标.

2) OR statements are executed in their reading order, so "find(start + 5, ...)" will be first executed, and then only if it does return null (that is, it hasn't find the solution) the next statement "find(start * 3, ...)" is going to be executed. Due to recursion, you can have any number of "+5" exection before a "*3" being executed, depending on the target of course.

这篇关于来自 Eloquent Javascript 的 Javascript 递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！