Recursion Error for coin change calculator - cannot debug

Question

I'm doing a change calculator - a function that takes in the cost of an item and the amount of money given to the cashier, before returning the number of each type of coin to optimally return the minimum coins.

I did it the nice simple way using floor division and modulo functions, but was also curious to stretch my understanding of recursion and defining functions within functions by doing it the following method (print statements for debugging):

def change_calc_2(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left):

        for i, c in enumerate(coin_vals):
            print("for loop level:", i)
            print("Amount left at start of kernel:", left)
            print("Coin val in question:", c)

            if left == 0:
                return coins # early exit routine

            elif c > left:
                continue

            else:
                coins[i] += 1
                print("coin added:", c)
                left -= c
                print("Amount left at end of kernel:", left)
                _calc(left)

        return coins

    #_calc(left)
    return _calc(left)       
    #return coins

print(change_calc_2(17, 20))

Running change_calc_2(x, 20) for x = 18 and x = 19, works fine. The outcomes are [1 0 0 0 0 0 0 0] ( a single £2 coin), and [0 1 0 0 0 0 0 0] (a single £1 coin).

However, when I try x = 17, and expect [1 1 0 0 0 0 0 0], I get [1 2 0 0 0 0 0 0].

The print debugging gives the following:

for loop level: 0
Amount left at start of kernel: 300
Coin val in question: 200
coin added: 200
Amount left at end of kernel: 100   ##### Completion of one round of for loop, as expected
for loop level: 0
Amount left at start of kernel: 100
Coin val in question: 200          ##### Rejects the 200p coin as too big for the amount left
for loop level: 1
Amount left at start of kernel: 100
Coin val in question: 100
coin added: 100                   #### Adds the last coin expected, so 100p + 200p in total
Amount left at end of kernel: 0 
for loop level: 0               
Amount left at start of kernel: 0 ############ <----- Running as expected until here
Coin val in question: 200         ************** <--- Should break just after this point?
for loop level: 2
Amount left at start of kernel: 0
Coin val in question: 50
for loop level: 1
Amount left at start of kernel: 100  ########### <--- Wtf? How has it added on money?
Coin val in question: 100
coin added: 100
Amount left at end of kernel: 0
for loop level: 0
Amount left at start of kernel: 0
Coin val in question: 200
for loop level: 2
Amount left at start of kernel: 0
Coin val in question: 50
[1 2 0 0 0 0 0 0]

I expect, at the marked points in the logs above, the program to have left=0 (which it does), and then hit the if left == 0: return coins , then exit the instance of _calc(). My thoughts are as it returns into the parent instance of _calc(), the parent too will hit the left==0, and return to the _calc() above it and so on.

Obviously my thinking is wrong - any help greatly appreciated! I have a feeling that it is due to me misunderstanding of the return function, and/or misunderstanding the "locality" vs "globality" of the variables

Answer 1

First, I'll say how you can fix your code above, then I'll give you a slightly better way to code this, if that is what you are looking for.

How to fix it

Your error is cropping up because your recursive call to _calc will edit coins, but not left. This is because within the function _calc, left has been replaced with a local variable.

I've added some 'quick-and-dirty' dynamic indenting to show how this is working:

def change_calc_2(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left,recur_level):
        print("{}recursion level:".format(' '*4*recur_level), recur_level)
        for i, c in enumerate(coin_vals):
            print("    {}for loop level:".format(' '*4*recur_level), i)
            print("    {}Amount left at start of kernel:".format(' '*4*recur_level), left)
            print("    {}Coin val in question:".format(' '*4*recur_level), c)

            if left == 0:
                print("{}EXIT recursion level:".format(' '*4*recur_level), recur_level)
                return coins # early exit routine

            elif c > left:
                continue

            else:
                coins[i] += 1
                print("    {}coin added:".format(' '*4*recur_level), c)
                left -= c
                print("    {}Amount left at end of kernel:".format(' '*4*recur_level), left)
                _calc(left,recur_level+1)

        return coins

    #_calc(left)
    return _calc(left,0)       
    #return coins

If we quickly run this:

>>> change_calc_2(17,20)
recursion level: 0
    for loop level: 0
    Amount left at start of kernel: 300
    Coin val in question: 200
    coin added: 200
    Amount left at end of kernel: 100      #<----- These values are the same
    recursion level: 1
        for loop level: 0
        Amount left at start of kernel: 100
        Coin val in question: 200
        for loop level: 1
        Amount left at start of kernel: 100
        Coin val in question: 100
        coin added: 100
        Amount left at end of kernel: 0
        recursion level: 2
            for loop level: 0
            Amount left at start of kernel: 0
            Coin val in question: 200
        EXIT recursion level: 2
        for loop level: 2
        Amount left at start of kernel: 0
        Coin val in question: 50
    EXIT recursion level: 1
    for loop level: 1
    Amount left at start of kernel: 100   #<----- These values are the same
    Coin val in question: 100
    coin added: 100
    Amount left at end of kernel: 0
    recursion level: 1
        for loop level: 0
        Amount left at start of kernel: 0
        Coin val in question: 200
    EXIT recursion level: 1
    for loop level: 2
    Amount left at start of kernel: 0
    Coin val in question: 50
EXIT recursion level: 0

Your error is preventing your left from updating correctly. If you wish to use recursion, make sure you just nest your calls correctly:

def change_calc_rec(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left,coin_index):
        i = coin_index
        c = coin_vals[i]
        print("{}coin_index:".format(' '*4*i), i)
        while True:
            if left == 0:
                print("{}EXIT recursion level:".format(' '*4*i), i)
                return coins # early exit routine
            elif c > left:
                break
            else:
                coins[i] += 1
                print("    {}coin added:".format(' '*4*i), c)
                left -= c
                print("    {}Amount left at end of kernel:".format(' '*4*i), left)

        if coin_index < len(coin_vals):
            return _calc(left,coin_index+1)
        else:
            return coins

    #_calc(left)
    return _calc(left,0)       
    #return coins

What is your recursion level should be the same as your coin index. Previously, you were getting to the index where your coin was larger than the required change, then starting a new loop with index 0. The above should fix it.

Without recursion

You don't need recursion for this problem at all. You can code it in a much safer fashion using a while loop:

def change_calc(cost, given): # input in full £xx.xx
coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
coins = [0] * len(coin_vals)

cost = cost * 100 # pence
given = given * 100
left = given - cost

for i, c in enumerate(coin_vals):
    while True:
        if left == 0:
            return coins # early exit routine
        elif c > left:
            break
        else:
            coins[i] += 1
            left -= c
raise ValueError('Bad given or cost!')

This will keep running the while loop until c > left, then it moves onto smaller coins. It returns when left == 0. It raises a ValueError if you give a bad value of given or cost, such that left == 0 never happens.

Enjoy!

Answer 2

def change_calc_2(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left):

        for i, c in enumerate(coin_vals):
            print("for loop level:", i)
            print("Amount left at start of kernel:", left)
            print("Coin val in question:", c)

            if left == 0:
                return coins # early exit routine

            elif c > left:
                continue

            else:
                coins[i] += 1
                print("coin added:", c)
                left -= c
                print("Amount left at end of kernel:", left)
                return _calc(left)   #### <----- This was the bug

        return coins

    #_calc(left)
    return _calc(left)       
    #return coins

print(change_calc_2(17, 20))

You didn't put the return statement.
So, your loop continued for the further iterations after returning from the child recursion call.

Answer 3

you are using a for loop inside a recursive function and the same condition gets evaluated twice ie.

This code

        coins[i] += 1
        print("coin added:", c)
        left -= c
        print("Amount left at end of kernel:", left)
        _calc(left)

will be evaluated inside the inner function and also inside the outer function

with the same index value i=1 in the for loop for i, c in enumerate(coin_vals):.

In effect you don't need the recursion in the first place or you need to pass the index to the inner function.