请问这个递归工作？ [英] How does this recursion work?

问题描述

这是从雄辩的Javascript的例子：

  

通过从数字1开始，反复要么加入5或   乘以3，新的数字无限量可以生产。   你会怎么写，给定一个数的函数，试图寻找一个   加法和乘法产生这个数字的序列？

我无法理解如何递归在这里工作，不知道是否有人能写出几次是怎么找到获取调用或一些其他的解释。

 函数findSequence（目标）{
  功能查找（开始，历史）{
    如果（开始==目标）
      回到历史;
    否则，如果（开始＆gt;目标）
      返回null;
    其他
      返回查找（启动+ 5（+历史++ 5））||
             找到（开始* 3，（+历史+* 3））;
  }
  返回的查找（1，1）;
}

的console.log（findSequence（24））; // =＆GT; （（（1 * 3）+ 5）* 3）
 

解决方案

该函数运行一个相当简单的的蛮力搜索 的与的回溯的：在每次调用级别它会尝试加入 5 的数量，看看从所得的编号开始让你的目标。如果是这样，则返回结果;否则，数由乘以3 ，并寻找目标继续从该新号码。作为递归随之而来，的前pression生产数量的文本重新presentation被传递到下一个调用水平

寻求 14 的情况如下：

 （1，1）
（5，1 + 5）
（10，（1 + 5）5」）
（15（（1 + 5）+5）+ 5）＆LT;＆LT; =失败
（30，（（1 + 5）5）* 3）＆其中;＆其中; =失败
（15，（1 + 5）* 3）＆其中;＆其中; =失败
（3，1 * 3）
（8（1 * 3）5）
（13，（（1 * 3）5）5」）
（18，（（（1 * 3）5）5）5）＆其中;＆其中; =失败
（39，（（（1 * 3）5）5）* 3）＆其中;＆其中; =失败
（24，（（1 * 3）5）* 3）＆其中;＆其中; =失败
（9中，（1 * 3）* 3）
（14，（（1 * 3）* 3）5）所述;＆其中; =成功！
 

This is an example from Eloquent Javascript:

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?

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)

解决方案

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.

The search for 14 goes as follows:

(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屋！