Understanding Recursion

Dec 21, 2019

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.

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

1
2
3
4
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.

=>¹ 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.

1
2
3
4
5
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:

1
2
>>>85 // 50
1

Modulo Division for remainder:

1
2
>>>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 , 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:

1
2
3
4
5
6
7
8
9
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.

Applying the Function to Validate the accomplishment

Steps

change_coins(85) , calling the function with the amount to be returned to the customer
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 the amount to be returned to the customer 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 the amount to be returned to the customer 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 a falsy value and there it
        return 10 // 5 => return 2

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 ↩︎

Gautham's

Posts

Tags

About

Resume