javascript - 剪刀的递归解

Question

今天我们在一堂课上遇到了这个问题，我很难想象递归的工作原理。您应该返回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

Answer 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

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

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

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

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

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

这是它第一次调用我们的嵌套函数，并分配 roundsLeft=numRounds和 result=[].

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

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=2和 result=["rock"]中。

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

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

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

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

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

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

然后，我们输入第4个递归级别并设置 roundsLeft=0和 result=["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=1和 result=["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=2和 result=["rock"]。

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

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

因此，用 roundsLeft=1和 result=["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=3和 result=[]调用完成了它的forEach循环。最终，我们遇到 return outcomes;，因此将我们的答案返回到 console.log(...)，后者将我们的答案输出到控制台。控制台现在显示一个包含27个元素的数组，每个元素包含一个3个元素的数组。