今天我们在一堂课上遇到了这个问题,我很难想象递归的工作原理。您应该返回n个石头剪刀布(一个玩家)的所有可能组合的数组。如果n = 3,它将返回一个长度为27的数组。

我在递归调用中获得roundsLeft-1参数,但是每次调用该函数时会发生什么?会非常感谢您的高级解释。我认为正在发生的是:

子例程递归函数将忽略第一个元素,然后连接下两个元素。我没有看到它是如何到达所有解决方案的,而不仅仅是那些以岩石为第一个元素,最后两个为串联的解决方案。 :-/

var rockPaperScissors = function(numRounds) {
  var outcomes = [];
  var plays = ["rock", "paper", "scissors"];

  // can add rounds later, get 3 working.
  // for a three round game, it would be 3^3 = 27.
  // for any number of rounds it would be 3^numrounds.

function findOutCome(roundsLeft, result){
  // when you cover all the rounds
  // push to the outcomes
  if (roundsLeft === 0) {
    outcomes.push(result);
    return;
  }

  plays.forEach(function(play){
    //result.push(play);
    //concat returns the entire array
    findOutCome(roundsLeft-1, result.concat(play))
  })
}

findOutCome(numRounds, []); // give it a starting point

return outcomes;
}


console.log(rockPaperScissors(3)); // returns an array of length 27

最佳答案

var rockPaperScissors = function(numRounds) {
  var outcomes = [];
  var plays = ["rock", "paper", "scissors"];

  // can add rounds later, get 3 working.
  // for a three round game, it would be 3^3 = 27.
  // for any number of rounds it would be 3^numrounds.

function findOutCome(roundsLeft, result){
  // when you cover all the rounds
  // push to the outcomes
  if (roundsLeft === 0) {
    outcomes.push(result);
    return;
  }

  plays.forEach(function(play){
    //result.push(play);
    //concat returns the entire array
    findOutCome(roundsLeft-1, result.concat(play))
  })
}

findOutCome(numRounds, []); // give it a starting point

return outcomes;
}


console.log(rockPaperScissors(3)); // returns an array of length 27


上面发生的是,在执行之前,我们首先定义了一个大型函数,该函数内部嵌套了一个函数。

然后我们调用console.log(rockPaperScissors(3));,这就是调用我们的大型函数并分配numRounds=3。在我们的功能体内,我们发现:

var outcomes = [];var plays = ["rock", "paper", "scissors"];
这些将为我们的递归函数保留定义,以读取plays并写入outcomes

然后,将定义用于递归的嵌套函数。

然后,最后,我们的嵌套函数被调用:findOutCome(numRounds, []);

这是它第一次调用我们的嵌套函数,并分配roundsLeft=numRoundsresult=[].

我们的第一个递归调用看起来像这样:

if (roundsLeft === 0){...}该语句为false,因为roundsLeft设置为3,所以我们继续...

plays.forEach(function(play){...}这会循环3次,因为播放设置为["rock", "paper", "scissors"]

第一个循环function(play){...}play="rock"调用,在回调函数主体中我们调用:

findOutCome(roundsLeft-1, result.concat(play));

这就是所谓的findOutCome(2,result.concat("rock"))

这里使用concat不会修改结果数组,而是在副本上工作,并使用[]"rock"与concat结合起来,从而创建["rock"]

如果要实际修改结果数组,请在此处使用result.push(...)
但是每个递归实例都有其自己的本地结果版本,因此,由于更改不会影响任何内容,因此该实例将不起作用。

我们的第一个递归实例仍处于打开状态,并且当我们开始递归调用时,我们仍处于第一个forEach循环内。

我们的findOutCome的第二个递归实例被调用。在我们的第二个实例roundsLeft=2result=["rock"]中。

if (roundsLeft === 0) {...}是错误的,因此我们进入forEach循环...

我们输入第一个forEach循环和play="rock"。然后,我们调用findOutCome(1, ["rock","rock"])

因此,我们输入了第三级递归,并设置了roundsLeft=1result=["rock","rock"]

if (roundsLeft === 0) {...}仍然为假,所以我们继续...

因此,我们进入forEach循环的第三级,该循环遍历plays数组...第一个循环使用play="rock",因此我们的循环以以下结尾:

findOutCome(0,["rock","rock","rock"])

然后,我们输入第4个递归级别并设置roundsLeft=0result=["rock","rock","rock"]

if (roundsLeft === 0) {outcomes.push(result);return;}这句话是对的,因此我们处理其逻辑。

当前设置为outcomes[]数组附加了["rock","rock","rock"]从而创建:

outcomes=[["rock","rock","rock"]];

然后,我们的if语句遇到return,这将结束我们的第四递归级别,并返回到我们的第三递归级别。

在第3个递归级别中,我们仍然在forEach循环中,因此我们继续进行循环中的第2个元素。

记住,在我们的第3个递归级别中,我们的findOutCome函数是用roundsLeft=1result=["rock","rock"]调用的,没有被修改。永远不要修改变量,而是每个递归实例都使用它们自己的这些变量的本地副本。因此,在我们的forEach循环中,由于它是第二个循环遍历的元素,play="paper"

然后,我们遇到findOutCome(roundsLeft-1, result.concat(play)),其结果为:

findOutCome(0, ["rock","rock","paper"])

因此,我们输入第4个递归级别,并且if (roundsLeft === 0) {outcomes.push(result);return;}为true,防止深度超过3个递归级别,因此我们处理其逻辑。

outcomes.push(result)["rock","rock","paper"]追加到我们的数组中。

因此,我们的结果数组现在显示为:outcomes=[["rock","rock","rock"],["rock","rock","paper"]];

然后,我们遇到return语句并关闭深度的第4个递归级别,并恢复第3个递归级别的forEach循环。

等到我们的forEach循环在第三个递归级别完成时,outcomes=[["rock","rock","rock"],["rock","rock","paper"],["rock","rock","scissors"]];

然后,我们的forEach循环完成,因此返回到递归的第二级forEach循环,其中roundsLeft=2result=["rock"]

我们继续进行forEach的第二循环,以达到深度的第二递归水平。 play="paper"。然后我们遇到:

findOutCome(roundsLeft-1, result.concat(play))

因此,用roundsLeft=1result=["rock","paper"]创建新的第三深度级别。

第三级通过另一个forEach并设置result=["rock","paper","rock"],然后roundsLeft=0将其发送到第四级深度。

我们的结果被添加到结果中。因此,我们现在有:
outcomes=[["rock","rock","rock"],["rock","rock","paper"],["rock","rock","scissors"],["rock","paper","rock"]];

等等……最终,我们的outcomes数组的大小增长到27个元素,并且我们的第一级递归被roundsLeft=3result=[]调用完成了它的forEach循环。最终,我们遇到return outcomes;,因此将我们的答案返回到console.log(...),后者将我们的答案输出到控制台。控制台现在显示一个包含27个元素的数组,每个元素包含一个3个元素的数组。

关于javascript - 剪刀的递归解,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32218850/

10-09 19:02