# Change for a dollar? I’ve got three ways to help you with that (i.e., the Coin Changer Kata)

I worked on another fun kata this week – the Coin Changer kata.

How it Works: Given a certain amount of cents, the algorithm should return the most efficient change equivalent to that amount. For example, if you need to get back \$0.89, you should receive 3 quarters, 1 dime, and 4 pennies.

Solution #1: Hello TDD

I started out simple–my favorite advantage of TDD so far–by solving for an empty array [ ], an array with just one penny , and an array with multiple pennies [1,1,1]. I quickly realized there was a pattern developing (which was very similar to the Roman Numeral Kata). With the help of TDD, I was able to come up with the following algorithm quickly. It loops through each coin and adds the appropriate number of coin to the coins_returned array:

```def get_change(remaining_cents)
coins_returned = []
[25, 10, 5, 1].each do |coin|
while remaining_cents >= coin
coins_returned << coin
remaining_cents -= coin
end
end
coins_returned
end
```

Solution #2: Let’s use math

My mentor Ryan challenged me to think about other ways to complete the kata. He wanted me to try and solve it without using loops. But before I arrived at the loop-free solution, I came up with the following…

How do I actually make the correct change in my head? I quickly solve for the number of necessary coins with division and subtraction, right? For \$0.89, I quickly think.. “okay .89/.25 = 3. Then I’m left with .14 and .14/.10 = 1. Then I’m left with .04 and .04/.01 = 4. So that ends up being 3 quarters, 1 dime, and 4 pennies.” I tried to replicate this thought process to see what the code would look like. This is what I came up with:

```def change_amount(remaining_cents)
coins_returned = []
[25, 10, 5, 1].each do |coin|
(remaining_cents/coin).times { coins_returned << coin }
remaining_cents -= (coin * (remaining_cents/coin))
end
coins_returned
end
```

Solution #3: Can't use a loop? Try recursion.
So like I said, my mentor wanted me to do the Coin Changer kata sans looping. Say whaaat? Yeah, how Iam I going to do that?

After a few people told me I should think about using recursion and googling it for a while, I finally began to understand what they were talking about.

Here is a user-friendly definition in the words of a StackOverflow genius: A recursive method calls itself. For a recursive algorithm to terminate you need a base case (e.g. a condition where the function does not call itself recursively) and you also need to make sure that you get closer to that base case in each recursive call.

After much trial and error with TDD, I arrived at the solution below. You'll see that my base case is when remaining_cents is equal to zero. In order to get closer to the base case, I add coins to the coin_array once I check to see if each coin in the demoninations array is needed, I eliminate that coin in the denominations array once I'm done with it, and then I subtract from remaining_cents.

```def change_amount(cents)
get_change(cents, [], [25,10,5,1])
end

def get_change(remaining_cents, coin_array, denominations)
return coin_array if remaining_cents == 0

current_coin = denominations
remaining_denominations = denominations.drop(1)

if remaining_cents >= current_coin
number_of_coins = remaining_cents/current_coin
remaining_cents -= (number_of_coins * current_coin)