* - Stephen Hawking*

Recursion is that type of programming construct that first bewilders those who take their first glance at it and then frightens only until they take a step forward fearlessly. Once taken, they’ll realise that it’s just like that *dragon* that’s hard to tame but nevertheless the strongest.

So, without any further ado, let’s just barge in.

Today, I have come across a video on Youtube by **interviewing.io** called Python interview with a Google Engineer: Coin Change

Before getting into solving the problem, let’s first try and understand the Problem itself.

Suppose, You are at a grocery store and about to buy some groceries worth INR 99.15/-. You give the shopkeeper at the counter an INR 100/- bill and now the shopkeeper must return the exact change back to you and not some *mints* or *chocolates* like they got used to.

We know that, he has to return 85 paise (100 - 99.15) and (assume) we have only the following denominations of coins available.

- 50 paise
- 25 paise
- 05 paise
- 01 paise

We have to calculate the number of coins that the shopkeeper has to return to return the exact change. As per the premise above, the shopkeeper has to return:

- 1 of 50 paise coin
- 1 of 25 paise coin
- 2 of 05 paise coin

=> a total of **4 coins**.

Now, what we have to do is, write a program for the same, i.e.one that returns the **number of coins** to be returned by the shopkeeper.

Hoping that you’ve understood the problem, let’s now get into solving it.

All we’ve to do is to write a function that takes in the *amount* (input) that has to be given back to the customer and returns the *number of coins* to return.

For this, let’s first define a function with the *input parameter* and *return value*.

```
def coins_change(amount):
# Calculation comes here
return no_of_coins
```

Now, somehow, we have to store the denominations of coins available to be able to return the exact number of coins to return. There exists decent room for optimisation here, which is, considering the premise above, when the shopkeeper has to return 85 paisa, he can do it by giving *85 nos of 1 paisa coins* or *19 nos of 5 paisa coins* etc, instead, the shopkeeper always tries to get rid of only least nos of coins. For which, he starts picking the coins from the highest denomination possible and proceeds towards the least, which means that he picks *one coin from the 50 paisa* drawer, then *one from the 25 paisa* drawer and so on, and this is exactly what our program has to do.

For this, I felt like having a `dictionary`

data structure with the **denominations of the coins** as **keys** and the **number of coins** of that denomination that are available as **values**.

Any data structure among *lists*, *tuples* and *sets* can be used for this data but just to make the program closer possible a real-time’s simulation, I have decided to go with dictionaries.

This data structure can be created within or outside the function as it doesn’t matter much for our current problem statement as the

number of coinsavailable isn’t of our concern with respect to the current problem statement

```
def coins_change(amount):
denominations = {50:5, 25:5, 5:10, 1:20}
# Calculation comes here
return no_of_coins
```

Now the actual solution starts. From the number of coins available of each denomination, we have to start from the highest denomination available and possible.

=>^{1} if I have to return 35 paise, then I have to start picking the coins from 25 paise denomination slot and then from the 5 paise coins slot.

=> If I have to return 9 paise, then I have to pick 1 of the 5 paise coins and 4 of 1 paise coins.

=> We’ve to read the keys of the dictionary in a descending order for which I have passed it to the `sorted()`

with the parameter for `reverse`

keyword argument being `True`

which returns the keys of the dictionary in the required descending order.

```
def coins_change(amount):
denominations = {50:5, 25:5, 5:10, 1:20}
for denomination in sorted(denominations, reverse = True):
# Calculation comes here
return no_of_coins
```

Now, at each iteration of the `for`

loop, we get each denomination available in descending order.

Therefore, we’ve to first check if the `amount`

(the change we’ve to return) is bigger than the `denomination`

at hand (the value, the `denomination`

object is holding in the iteration). If it turns out to be `false`

(=> if `amount`

< 50 paisa) , go to the next denomination, else (if `amount`

> 50 paisa, as in our case, 85 paisa), we’ve to calculate the number of coins of 50 paise to return and this will be given by the **Floor Division** ( `//`

) operator and the remaining amount to be given is determined by the **Modulo** ( `%`

) operator.

- Floor Division for
*number of coins*:

```
>>>85 // 50
1
```

- Modulo Division for
*remainder*:

```
>>>85 % 50
35
```

And here comes the crucial part.

Now, if the `amount >= denomination`

, then calculate the `no_of_coins`

that are to be given and check if the remainder, `amount - (no_of_coins * denomination)`

, is greater than `0`

. If `false`

, meaning there is no remainder, therefore, return `no_of_coins`

but if `true`

, meaning that remainder exists, `return`

`no_of_coins +`

, since we are yet to calculate the number of coins to be returned for the remaining amount, we return `coins_change(amount % denomination)`

. Where,

`no_of_coins`

=`amount // denomination`

, andremaining amount =

`amount`

-`no_of_coins`

* denomination.

**The above mentioned property of a function calling itself (as in the return statement mentioned above) is called Recursion**

Here’s the code for the same:

```
def change_coins(amount=None):
denominations = {50: 5, 25: 5, 5: 10, 1: 20}
if amount:
for denomination in sorted(denominations, reverse=True):
if amount >= denomination:
if amount % denomination:
return (amount // denomination) + change_coins(amount % denomination)
else:
return amount // denomination
```

Now for a clearer understanding, let’s check how this function works by analysing the working of the function at each step.

`change_coins(85)`

, _calling the function with theto be returned to the customer_*amount*`if amount:`

, check if amount is not`None`

, just to make sure that the function*literally*does nothing when*nothing is to be returned*.`for denomination in sorted(denominations, reverse=True):`

==`for denomination in [50, 25, 5, 1]:`

- in the first iteration,
`denomination`

= 50 `if amount >= denomination:`

=>`if 85 >= 50:`

=`True`

`if amount % denomination:`

=>`if 85 % 50:`

=>`if 35`

=`True`

because,`35 > 0`

=>**remainder exists!**`return (amount // denomination) + change_coins(amount % denomination)`

=>`return ( 85 // 50) + change_coins( 85 % 50)`

=>`return 1 + change_coins(35)`

`change_coins(35)`

, _calling the function with theto be returned to the customer*amount*_*again*`for denomination in [50, 25, 5, 1]:`

- in the
*first*iteration,`denomination`

= 50 `if amount >= denomination:`

=>`if 35 >= 50:`

=`False`

- in the
*second*iteration,`denomination`

= 25 `if amount >= denomination:`

=>`if 35 >= 25:`

=`True`

`return ( 35 // 25 ) + change_coins( 35 % 25 )`

==`return 1 + change_coins(10)`

`change_coins(10)`

, _calling the function with theto be returned to the customer*amount*_*again*`for denomination in [50, 25, 5, 1]:`

- in the
*first*iteration,`denomination`

= 50 `if amount >= denomination:`

=>`if 10 >= 50:`

=`False`

- in the
*second*iteration,`denomination`

= 25 `if amount >= denomination:`

=>`if 10 >= 25:`

=`False`

- in the
*third*iteration,`denomination`

= 5 `if amount >= denomination:`

=>`if 10 >= 5:`

=`True`

,*but*`if 10 % 5:`

=`False`

because,`0`

is avalue and there it*falsy*`return 10 // 5`

=>`return 2`

- in the

- in the

- in the first iteration,

**change_coins(85) = return 1 + change_coins(35) = return 1 + change_coins(return 1 + change_coins(10)) = return 1 + (return 1 + change_coins(10)) = return 1 +(return 1 + (return 2)) = 1 + (1 + (2)) = 1 + 1 + 2 = 4**

- a symbol meaning
`implies`

^{[return]}