Рекурсивное решение для ножниц каменной бумаги

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){...} это утверждение неверно, так как 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 здесь не изменяет result, а работает на копии и concats [] с "rock", создавая таким образом ["rock"].

Если мы хотим на самом деле изменить массив результатов, мы будем использовать здесь result.push(...). Но каждый экземпляр рекурсии имеет свою локальную версию результата, так что это не сработает, поскольку изменения ничего не повлияют.

Наш первый экземпляр рекурсии по-прежнему открыт, и мы все еще находимся в нашем первом цикле forEach, когда мы начинаем наш рекурсивный вызов.

Вызывается наш второй экземпляр рекурсии findOutCome. В нашем втором случае roundsLeft=2 и result=["rock"].

if (roundsLeft === 0) {...} является ложным, поэтому мы переходим на наш цикл по каждому элементу ...

Мы входим в наш первый цикл ForEach и play="rock". Затем мы звоним findOutCome(1, ["rock","rock"])

Таким образом, мы вводим наш третий уровень рекурсии и устанавливаем roundsLeft=1 и result=["rock","rock"].

if (roundsLeft === 0) {...} еще ложь, поэтому мы переходим ...

Таким образом, мы войти в нашем 3-е уровня нашего цикла Foreach который петля через наши прослушивания массива ... первый цикл использует 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"]];

Тогда наше утверждение, если встречает return, который заканчивается наш 4-й уровень рекурсии и возвращается в наш 3-го уровня рекурсии.

На нашем третьем уровне рекурсии мы все еще находимся в пределах нашего цикла forEach, поэтому перейдем к нашему 2-му элементу в цикле.

Помните, что на нашем третьем уровне рекурсии наша функция 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;} верно, предотвращая более 3-х уровней рекурсии глубины, поэтому мы обрабатываем его логику.

outcomes.push(result) прилагает ["rock","rock","paper"] к нашему массиву.

Таким образом, наши результаты массив теперь гласит: outcomes=[["rock","rock","rock"],["rock","rock","paper"]];

Тогда мы сталкиваемся с return заявление и закрыть наш 4-й уровень рекурсии глубины и возобновить цикл по каждому элементу нашего 3-го уровня рекурсии в.

К тому времени наши концы петли Foreach в нашем 3-го уровня рекурсии, outcomes=[["rock","rock","rock"],["rock","rock","paper"],["rock","rock","scissors"]];

Тогда наш цикл Foreach заканчивает тем самым возвращаясь к нашей 2-го уровня петли Foreach рекурсии, где roundsLeft=2 и result=["rock"].

Продолжаем нашу вторую петлю нашего forEach для нашего второго уровня глубины рекурсии. play="paper". Тогда мы сталкиваемся:

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

Таким образом, создается новый 3-й уровень глубины с roundsLeft=1 и result=["rock","paper"].

3-й уровень проходит через другой для каждого и устанавливает result=["rock","paper","rock"] и roundsLeft=0 отправляет его на 4-й уровень глубины.

Наш результат добавляется к результатам. Таким образом, мы теперь имеем: outcomes=[["rock","rock","rock"],["rock","rock","paper"],["rock","rock","scissors"],["rock","paper","rock"]];

и т.д., и т.д. ... в конечном счете, наш outcomes массив вырастает до 27 элементов в размерах и наш первый уровень рекурсии, которая была вызвана с roundsLeft=3 и result=[] заканчивает свой цикл по каждому элементу. Наконец, мы встретим return outcomes; и таким образом вернем наш ответ console.log(...), который выводит наш ответ на консоль. Теперь консоль отображает массив, содержащий 27 элементов, каждый из которых содержит массив размером 3 элемента.

Answer 2

Если вы посмотрите на функцию findOutCome:

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)); 
    }); 
} 

вы можете заметить, что:

if (roundsLeft === 0) { 
    outcomes.push(result); 
    return; 
} 

означает, что функция создаст толчок другой Possiblity когда roundsLeft достигает 0.

Теперь давайте посмотрим на plays.forEach:

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

, где для каждого варианта в plays (rock, paper, scissors), текущий массив результата вычисляется начинается с этой опцией, а затем добавляет результат:

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

Это означает, что мы оглянемся назад на findOutCome с одним менее круглым.

Так говорят 3 первоначально был принят в:

1) `3 === 0` is `false` so we move on. 
2) `plays.forEach` says take each option in `plays` (added to `result` which starts off empty) and pass it in to `findOutCome` with one round less. We pass in `Rock` as `result` and `2` as roundsLeft`: 
    A) `2 === 0` is `false` so we move on. 
    B) `plays.forEach` says do same as #2. We pass in [`Rock`, `Rock`] as `result` with `1` as `roundsLeft`. 
     I) `1 === 0` is `false` so we move on. 
     II) `plays.forEach says do same as #B. We pass in [`Rock`, `Rock`, `Rock`] as `result` with `0` as `roundsLeft`. 
      Z) `0 === 0` is `true` so this time we add the `result` array we just got to the `outcomes` array. 

    Now wait a second, we left off going through each `plays` in #B. We need to repeat #I, #II, and #Z with the next option (after `rock`) in `plays`. Let's use `paper`. The result should be another array of ['rock', 'rock', `paper`] being pushed to `outcomes`. 

Используя последний вариант scissors (с шагами #i, #II и #III должны привести к [rock, rock, scissors] массив добавляется к outcomes.

подождите, мы были в середине делают весь этот процесс, где roundsLeft является 2. мы просто сделали это для rock. повторим #A и #B для второго неавтоматического ион paper.Затем повторите roundsLeft по адресу 1, где plays.forEach добавляет все возможности #I, #II и #Z, когда мы находимся на [rock, paper. Это добавит еще три массивы outcomes:

[`rock`, `paper`, `rock`] 
[`rock`, `paper`, `paper`] 
[`rock`, `paper`, `scissors`] 

Затем мы можем запустить третий вариант, где roundsLeft является 2 и добавить еще три массива в outcomes:

[`rock`, `scissors`, `rock`] 
[`rock`, `scissors`, `paper`] 
[`rock`, `scissors`, `scissors`] 

Сейчас, подожди мы в середине прохождения каждый из plays и добавление 9 возможных массивов в outcomes. Мы начали с [rock. Добавим еще 9 в [paper и еще 9 по адресу [scissors.

Это дает нам 27 возможных комбинаций, которые мы ищем.

Как начинается roundsLeft, чем больше слоев, в которых мы запускаем все это, тем больше мы можем заботиться обо всех этих растущих возможностях.

Answer 3

Чтобы понять рекурсию, вам нужно понять объем функций. Чтобы все было достаточно просто, чтобы понять, предположим, что фигурные скобки, которые определяют начало и конец функционального блока (тела), представляют собой область видимости, и этот объем можно проиллюстрировать с помощью окна. Просто визуализируйте коробку. Теперь, каждый раз, когда функция объявлена, она появляется как поле.
Функция может быть вызвана с использованием внешнего кода или внутреннего кода (рекурсия). Поэтому, если вы вызываете функцию внутри себя (или другую функцию), эта функция появляется в виде дочернего окна, расположенного внутри родительского поля. Вы можете передать параметр (ы) функции, но параметры знают только значение, которое оно передало ему. поэтому любые изменения, применяемые к параметру, не должны влиять на внешнюю переменную с тем же именем, что и параметр. что, как говорится, вернемся к вашему вопросу и попытаемся объяснить результаты, используя нашу аналогию с полем.

В дальнейшем мы будем использовать коробки разных цветов (красный, зеленый, желтый, белый). Помните, что ящики иллюстрируют различные области. Также «рок» - «r», «бумага» - «p», «ножница» - это «s».

При первом вызове 'findOutcome' создается RED-поле и содержит параметры roundleft = 3. result = [].

//RED BOX : roundleft = 3, result =[] 
//----for each rock, paper, scissor 
//start with rock (r) -- note : 3 , r means "roundleft, rock" 
3 , r => internal call to findOutcome() creates a GREEN BOX, 
      so that GREEN BOX is inside the RED one, 
      with decremented roundleft value 2. 
      Keep in mind that parameter only knows about its value 

//GREEN BOX : roundleft = 2, result =[r] 
//-----for each r p s, 
//starts with rock, 
2 , r => internal call to findOutcome() creates a YELLOW BOX, 
      inside the GREEN BOX which is inside the RED BOX 
      with decremented roundleft value 1. 

    //YELLOW BOX : roundleft 1, result =[r, r] 
    //----- for each r p s, 
    //starts with rock, roundleft =1, result =[r, r] 
    1, r => internal call to findOutcome() creates a WHITE BOX 
      with decremented roundleft value 0. 
      at this point RED > GREEN > YELLOW > WHITE 

    //WHITE BOX: round = 0, result =[r, r, r] 
    roundsLeft = 0 => push result to outcomes. 
         return means exit WHITE BOX. 
         we are now (back) inside YELLOW BOX 
         where roundl= 1, res=[r, r] 
         is there another element to go through? YES : "paper" 

    //follow with paper, roundleft =1, result =[r, r] 
    1, paper(p) // internal call creates a WHITE BOX 

    //WHITE BOX: round 0, result =[r, r, p] 
    0 => push result to outcomes. 
     exit white box, back to YELLOW BOX 
     is there another element to go through? YES : "scissor" 

    //follow with scissor. roundleft =1, result =[r, r] 
    1, scissor // internal call creates a WHITE BOX 

    //WHITE BOX: roundl 0, result =[r, r, s] 
    0 => push result to outcomes. 
     exit WHITE BOX, back to YELLOW BOX 
     is there another element to go through? NO =>exit YELLOW BOX 
     back inside GREEN BOX where roundl 2, result =[r] 

/*------ at this point outcomes length = 3 ---------- */ 


//GREEN BOX (is inside RED BOX) 
//is there another element to go through? YES : "paper" 

//follow with paper, roundleft =2, result =[r] 
2, p // internal call creates a YELLOW BOX 
    //----- for each r p s, 
    //starts with rock, roundleft =1, result =[r, p] 
    1, r // internal call creates a WHITE BOX 

    //WHITE BOX: roundl 0, result =[r, p, r] 
    0 => push result to outcomes. 
     exit WHITE BOX and back inside YELLOW BOX 
     where roundl= 1, res=[r, p] 
     is there another element to go through? YES : "paper" 

    //follow with paper, roundleft =1, result =[r, p] 
    1, p // internal call creates a WHITE BOX inside the YELLOW 

    //WHITE BOX: roundl 0, result =[r, p, p] 
    0 => push result to outcomes. 
     exit WHITE BOX, back to YELLOW BOX 
     is there another element to go through? YES : "scissor" 


    //follow with scissor. roundleft =1, result =[r, p] 
    1, s // internal call creates a WHITE BOX 

    //WHITE BOX: roundl 0, result =[r, p, s] 
    0 => push result to outcomes. 
     exit WHITE BOX, back to YELLOW BOX 
     is there another element to go through? NO =>exit YELLOW BOX 
     back inside GREEN BOX where roundl 2, result =[r] 

/*------ at this point outcomes length = 6 --------*/ 


//GREEN BOX (inside the RED BOX) 
//is there another element to go through? YES : "scissor" 

//follow with scissor, roundleft =2, result =[r] 
2, s 
    //----- for each r p s, 
    //starts with rock, roundleft =1, result =[r, s] 
    1, r 

    //WHITE BOX: roundl 0, result =[r, s, r] 
    0 => push result to outcomes. 
     exit WHITE BOX and back inside YELLOW BOX 
     where roundl= 1, res=[r, s] 
     is there another element to go through? YES : "paper" 

    //follow with paper, roundleft =1, result =[r, s] 
    1, p 

    //WHITE BOX: roundl 0, result =[r, s, p] 
    0 => push result to outcomes. 
     exit WHITE BOX, back to YELLOW BOX 
     is there another element to go through? YES : "scissor" 


    //follow with scissor. roundleft =1, result =[r, s] 
    1 s // decrement to 0 

    //WHITE BOX: roundl 0, result =[r, p, s] 
    0 => push result to outcomes. 
     exit WHITE BOX, back to YELLOW BOX 
     is there another element to go through? NO =>exit YELLOW BOX 
     back inside GREEN BOX where roundl 2, result =[r] 

/*------ at this point outcomes length = 9 --------------*/ 


//GREEN BOX : is there another element to go through after scissor ? 
// NO =>exit GREEN BOX 
//back inside RED BOX where roundl 3, result =[] 

// RED BOX 
//is there another element to go through after rock? YES : "paper" 
//start with paper 
3, p // internal call creates a GREEN BOX 

//GREEN BOX : roundl 2, result =[p] 
//-----for each r p s, 
//starts with rock, 
2, r // internal call creates a YELLOW BOX 

    //YELLOW BOX : roundl 1, result = [p, r] 
    //----- for each r p s, 
    //starts with rock, roundleft =1, result =[p, r] 
    1, r // internal call creates a WHITE BOX 

    //WHITE BOX: roundl 0, result = [p, r, r] 
    0 => push result to outcomes. 
     exit WHITE BOX and back inside YELLOW BOX 
     where roundl= 1, result = [p, r] 
     is there another element to go through? YES : "paper" 

    //follow with paper, roundleft =1, result =[p, r] 
    // ... and so on... 

И так далее, пока мы снова к RED BOX и длина результаты будут идти с 9 (породы) до 18 (на бумаге) до 27 (на ножничные).
Таким образом, в рекурсии функция называется внутренне и каждый раз, когда создается новая область. Выполняется один и тот же блок кода, каждый раз с параметрами, которые знают только о своих значениях и поэтому не влияют на внешний вид области (поле). при попадании в нижнюю часть окна, если нет внутреннего вызова функции, он возвращается в родительский блок (один уровень вверх).
Мой родной язык французский, поэтому, надеюсь, мой английский не настолько ржавый, и эта аналогия коробки помогла вам понять, как работает рекурсия.