Mastering recursion

Welcome back to another week in Code Review, a series of coding challenges and interview related content delivered weekly. Last week we started to discuss recursion. In case you missed it - check out last week’s article here. Additionally, we released our new newsletter! Give us your email here and we'll add you to our "first to know" list :) And without further ado - let's get solving last week’s problem!

The solution

This solution involves, you guessed it, recursion! If you solved it in a more “dynamic programming” approach, be sure to comment with your solution below.

Something that helps me solve any algorithm problem is stopping and thinking for a moment how would my brain solve this problem? What if I had to count the ways to make change of a certain amount with coins with a specific set of denominations?

Let’s say I had to make 5 cents from coins worth 1 and 2 cents. I’d probably start by taking one 2 cents coin, subtract 2 cents from my desired total 5 cents and work with the remaining 3 cents. I’d take another 2 cents coin, subtract that from the remaining 3 cents leaving me with 1 cent needed to make my desired 5. Taking another 2 cents would push my total over, so I’d move on to the next smallest denomination, in this case 1 cent. Taking that gets me to 5 cents and that is one way to make 5 cents with 2 cents and 1 cents. And I’d continue down the coins list like that until I found all the ways. How to translate that into code? Well, it sounds like when my total remaining cents to make is 0 we have found a way right? That sounds like a base case. And if we go over the total desired into negative territory, that isn’t a way. That also sounds like a base case.

// see if you can spot the bug before I complete this function below!
function coins (amount) {
 const coinsArr = [ 1, 2 ]
 if (amount === 0) return 1
 if (amount < 0) return 0

 let numberOfWays = 0
 for (let i = 0; i < coinsArr.length; i++) {
   numberOfWays += coins(amount - coinsArr[i])
 }
 return numberOfWays
}

After our base cases, we essentially just loop through the coins array trying to make change for the remaining amounts.

Walk through

Let's walk through some inputs so we can follow this recursion tree. First we call the function with an amount = 4. We start with the first coin, 1 and subtract it from the current amount, 4 and get 3. We then call coins again with that number. We then reenter the coins function with an amount of 3 and we again start with the first coin 1. We subtract 1 from 3 and call coins again with 2. And so on until we subtract 1 from 1 and get 0 and hit our first base case and add 1 to our numberOfWays variable. This is the 1,1,1,1 way. We come back out into the for loop (with the amount 1) and subtract 2 and get -1. This brings us to our other base case and we return 0. And so on. This is shown as a tree below:

So have you spotted it yet?

That’s right - we’re counting some combinations multiple times due to different permutations of the same coins. 1,1,2, 1,2,1 and 2,1,1 are all the same combination for our purposes. So how can we not restart each for loop for every time we call the coins function? Pass in whatever coin we are up to of course! Another good tip - talk with your interviewer about the function signature. You never know when an extra parameter might be needed or desired. Usually, this can be a good talking point with your interviewer. Don’t be shy!

Here that is in code:

function coins (amount, idx) {
 const coinsArr = [ 1, 2 ]
 if (amount === 0) return 1
 if (amount < 0) return 0

 let numberOfWays = 0
 for (let i = idx; i < coinsArr.length; i++) {
   numberOfWays += coins(amount - coinsArr[i], i)
 }
 return numberOfWays
}

And here is the tree to help you visualize it:

Good work all! See you next week, where I'll break down how I built my favorite side project, Breadwinnerss.