这个递归是如何工作的? [英] How does this recursion work?

问题描述

这是一个来自 Eloquent Javascript 的例子:

This is an example from Eloquent Javascript:

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

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of additions and multiplications that produce that number?

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

I'm having trouble understanding how the recursion is working here, wondering if someone could write out a couple times how find is getting called or some other explanation.

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)

推荐答案

该函数运行一个相当简单的暴力搜索 使用回溯:在每个调用级别，它尝试将 5 添加到数字，看看从结果数字开始是否能让你达到目标.如果是，则返回结果；否则，数字乘以 3，然后从新数字继续搜索目标.随着递归的进行，产生数字的表达式的文本表示被传递到下一个调用级别.

The function runs a rather simple brute force search with backtracking: at each invocation level it tries adding 5 to the number, and see if starting from the resultant number gets you to the goal. If it does, the result is returned; otherwise, the number is multiplied by 3, and the search for the goal continues from that new number. As the recursion goes along, the textual representation of the expression producing the number is passed to the next invocation levels.

搜索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!

这篇关于这个递归是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！