Understanding Recursion
Introduction
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.
Problem Statement
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.
Approach Towards Solution
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.


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 realtime’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 coins available isn’t of our concern with respect to the current problem statement


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.


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:


 Modulo Division for remainder:


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
, and
remaining 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:


Now for a clearer understanding, let’s check how this function works by analysing the working of the function at each step.
Applying the Function to Validate the accomplishment
Steps
change_coins(85)
, calling the function with the amount to be returned to the customerif amount:
, check if amount is notNone
, 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 the amount to be returned to the customer againfor 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 the amount to be returned to the customer againfor 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
, butif 10 % 5:
=False
because,0
is a falsy value and there itreturn 10 // 5
=>return 2
 in the first iteration,
 in the first iteration,
 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
↩︎