Zach

Posted on Jun 26, 2021

Recursion Breakthrough Pt. 2

In my previous post I reflected a bit on my journey solving the 'Rock Paper Scissors' recursion problem.

When starting my final and successful approach, I had a clarity of purpose in starting small and specific, and moving with certainty from the inside fo the recursion outward. The process was edifying and so I've recreated it here, complete with some of my minor missteps, and the corrections to those missteps.

Before beginning, I'll emphasize how critical and clarifying it was for me to start granularly and take my first step from the base case, or at least as close to it as I could.

var myArr = ['A','B','C']
myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    console.log(item + elem)
  })
})

Ar,Ap,As,Br,Bp,Bs,Cr,Cp,Cs

Good. We want to put this into an array. Yhis is going to be a recursive function, so let's feed it back into the original array.

var myArr = ['A','B','C']
myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    myArr.push(item + elem)
  })
})

["A", "B", "C", "Ar", "Ap", "As", "Br", "Bp", "Bs", "Cr", "Cp", "Cs"]
Not quite. We don't want to keep the original array, just the results after recursing over and changing the array items. Let's put the results in a new array.

var newArr = []
var myArr = ['A','B','C']
myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    newArr.push(item + elem)
  })
})
console.log[newArray]

["Ar", "Ap", "As", "Br", "Bp", "Bs", "Cr", "Cp", "Cs"]

Nice. We want to do this again right? To recurse over our array myArr.

Run the above command again and we get:

["Ar", "Ap", "As", "Br", "Bp", "Bs", "Cr", "Cp", "Cs"]

Same thing. Ok what inputs are we feeding into this code? myArr items. But we're not changing myArr, so we're going to get the exact same array output.

So let's dump our new array items (which were our desired output) and feed them back into myArr, that way we concat those new items (rr rp and rs vs r p and s for instance) to our next round of 'rps'.

var newArr = []
var myArr = ['A','B','C']
myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    newArr.push(item + elem)
  })
})
myArr = newArr

myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    newArr.push(item + elem)
  })
})
myArr = newArr
console.log(myArr)

["Ar", "Ap", "As", "Br", "Bp", "Bs", "Cr", "Cp", "Cs", "Arr", "Arp", "Ars", "Apr", "App", "Aps", "Asr", "Asp", "Ass", "Brr", "Brp", "Brs", "Bpr", "Bpp", "Bps", "Bsr", "Bsp", "Bss", "Crr", "Crp", "Crs", "Cpr", "Cpp", "Cps", "Csr", "Csp", "Css"]

Whoa what happened? We only want to see combinations of three (eg. 'srs') and not of two (eg 'rs'). So we have results from the first round in there. Let's check out newArray after the first round, and before the second round. It should look like our output of our first round (that we feed back into myArr):

console.log(newArray)

["Ar", "Ap", "As", "Br", "Bp", "Bs", "Cr", "Cp", "Cs", "Dr", "Dp", "Ds", "Er", "Ep", "Es"]

Yep. We never cleared out newArr. The whole point of newArr is to have a fresh array to work with for each round. So we have to clear it out. Let's do that and run those first two rounds again.

var newArr = []
var myArr = ['A','B','C']
myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    newArr.push(item + elem)
  })
})
myArr = newArr

var newArr = []
myArr.forEach(function(item){
  ['r','p','s'].forEach(function(elem){
    newArr.push(item + elem)
  })
});
myArr = newArr
console.log(myArr)

["Arr", "Arp", "Ars", "Apr", "App", "Aps", "Asr", "Asp", "Ass", "Brr", "Brp", "Brs", "Bpr", "Bpp", "Bps", "Bsr", "Bsp", "Bss", "Crr", "Crp", "Crs", "Cpr", "Cpp", "Cps", "Csr", "Csp", "Css"]

We're cooking now. Not only do the results look right, but the math checks out, too. Our array myArr is now 27 items long and we're expecting 3x3x3 = 27.

There we have it, this is the basis of our recursion. In other words, we have our recursive case now.

Building out the function

What's cool about what we've got is that there are certain elements of our code that have been repeated and some that haven't. Some that we've recursed over and others that we haven't. We can sue these observations to arrange our function.

What specifically do I notice?

That console.log at the end prints our desired output. It looks like a return statement.
We create an empty array, newArr, for each iteration.
We initialize our primary array, myArr, once and declare it's contents at that time.

We also haven't talked about two related ideas:

A base case - aka when do we stop (or wind back out of) the recursion?
Keeping track of our levels of recursion. In other words, how do we incorporate our user input, which tells us how many rounds of 'rps' to play, which is another way of saying how long is each string item within our array and how long is the array.

[If we play two rounds, we would expect our items to be strings that are two characters long ('rr' or 'ps') and for myArr to have a length of 3^2. For four rounds of play, we're looking at three character strings and a length of 3^4.]

Let's consider these as we start to build this function.

var rockPaperScissors = function(count){
  myArr = ['r','p','s']
  //something goes here
  return myArr
}

Let's now dump in our recursive case. We know we'll be looping over this somehow and I'm already thinking 'inner function'.

var rockPaperScissors = function(count){
  myArr = ['r','p','s']

  //start recursive case
  var newArr = []
  myArr.forEach(function(item){
    ['r','p','s'].forEach(function(elem){
      newArr.push(item + elem)
    })
  });
  myArr = newArr
  //end recursive case

  return myArr
}

Alright, so we know that once we enter the recursive case and then exit it, we'll want to re-visit it immediately until we hit some base case, at which point we should have a fully populated and accurate myArr with all of our combinations of 'rps'.

Let's create an inner function to do that.

Since we know that we're going to end this recursion when there are no more rounds left to play,

we'll set a count of 0 as our base case.

We also know that we need to

decrement our round count. Based on my previous experience with recursion, my sense is we can do that as our parameter in our inner function.

var rockPaperScissors = function(count){
  myArr = ['r','p','s']

  //start recursive case
  var innerFunc = function(count){

    if (count === 0){
      return
    }

    var newArr = []
    myArr.forEach(function(item){
      ['r','p','s'].forEach(function(elem){
        newArr.push(item + elem)
      })
    });
    myArr = newArr
    innerFunc(count-1)
  }
  //end recursive case

  return myArr
}

Let's try it:

rockPaperScissors(3)

["r", "p", "s"]

Hmmm, not it. It looks like we haven't recursed.

Looking back through the code, we never called the inner function! The code reads our variable declarations for:

var myArr
var innerFunc ...and then it returns.

We need to call innerFunc before we return:

var rockPaperScissors = function(count){
  myArr = ['r','p','s']

  //start recursive case
  var innerFunc = function(count){

    if (count === 0){
      return
    }

    var newArr = []
    myArr.forEach(function(item){
      ['r','p','s'].forEach(function(elem){
        newArr.push(item + elem)
      })
    });
    myArr = newArr
    innerFunc(count-1)
  }
  //end recursive case

  innerFunc(count)
  return myArr
}

Here we go again:

rockPaperScissors(3)

["rrrr", "rrrp", "rrrs", "rrpr", "rrpp", "rrps", "rrsr", "rrsp", "rrss", "rprr", "rprp", "rprs", "rppr", "rppp", "rpps", "rpsr", "rpsp", "rpss", "rsrr", "rsrp", "rsrs", "rspr", "rspp", "rsps", "rssr", "rssp", "rsss", "prrr", "prrp", "prrs", "prpr", "prpp", "prps", "prsr", "prsp", "prss", "pprr", "pprp", "pprs", "pppr", "pppp", "ppps", "ppsr", "ppsp", "ppss", "psrr", "psrp", "psrs", "pspr", "pspp", "psps", "pssr", "pssp", "psss", "srrr", "srrp", "srrs", "srpr", "srpp", "srps", "srsr", "srsp", "srss", "sprr", "sprp", "sprs", "sppr", "sppp", "spps", "spsr", "spsp", "spss", "ssrr", "ssrp", "ssrs", "sspr", "sspp", "ssps", "sssr", "sssp", "ssss"]

81 items. Too long! 81 is 3^4. Looks like I have to stop the recursion once 'count' early.

Let's go.

var rockPaperScissors = function(count){
  myArr = ['r','p','s']

  //start recursive case
  var innerFunc = function(count){

    if (count === 1){
      return
    }

    var newArr = []
    myArr.forEach(function(item){
      ['r','p','s'].forEach(function(elem){
        newArr.push(item + elem)
      })
    });
    myArr = newArr
    innerFunc(count-1)
  }
  //end recursive case

  innerFunc(count)
  return myArr
}

rockPaperScissors(3)

["rrr", "rrp", "rrs", "rpr", "rpp", "rps", "rsr", "rsp", "rss", "prr", "prp", "prs", "ppr", "ppp", "pps", "psr", "psp", "pss", "srr", "srp", "srs", "spr", "spp", "sps", "ssr", "ssp", "sss"]

27 items. Done and done.

I feel really good about this approach, the solution it yielded, and the learning I accomplished along the way. I'll restate, for my own benefit, the questions that kicked off this successful process: