Why doesn't this recursive function work for counting number of coins due in change?

Question

I am learning to write recursive functions in python. I wrote this to solve for the number of coins due back in making change for any amount (ignores any paper money, i.e. a quarter is the highest denomination possible).

While I know there is probably a better algorithm for this, right now I am just interested in why this one I wrote doesn't work. If I input anything other than a coin's exact amount, it returns an error saying recursive depth exceeded.

    import sys
    import math
    
    
    
    def get_change(m, coin_count):

        if m == 0:
            return coin_count
    
        else:
            if m >= 0.25:
                coin_count += math.floor(m / 0.25)
                m = m % 0.25
            
            elif m >= 0.1:
                coin_count += math.floor(m / 0.1)
                m = m % 0.1
            
            elif m >= 0.05:
                coin_count += math.floor(m / 0.1)
                m = m % 0.05
    
            elif m >= 0.01:
                coin_count += math.floor(m / 0.01)
                m = m % 0.01
    
            return get_change(m, coin_count)
            
    m = float(input())
    coin_count = 0
    print(get_change(m, coin_count))

Here is corrected code from the helpful comments. Works now. Decided to change format so decimals are not an issue:

def get_change(m, coin_count):

    if m < 1:
        return coin_count

    else:
        if m >= 25:
            coin_count += math.floor(m / 25)
            m = m % 25
        
        elif m >= 1:
            coin_count += math.floor(m / 10)
            m = m %1
        
        elif m >= 5:
            coin_count += math.floor(m / 5)
            m = m % 5

        elif m >= 1:
            coin_count += math.floor(m / 1)
            m = m % 1

        return get_change(m, coin_count)

m = int(input())
coin_count = 0
print(get_change(m, coin_count))

You shouldn't use floating point numbers for this. This can introduce inaccuracies that prevent the algorithm from terminating. — Barmar, Sep 10 '21 at 20:46
Numbers such as ``0.01`` are *base 2* floating point numbers – they are *not* exact for decimal numbers. — MisterMiyagi, Sep 10 '21 at 20:46
Does this answer your question? [Why not use Double or Float to represent currency?](https://stackoverflow.com/questions/3730019/why-not-use-double-or-float-to-represent-currency) — MisterMiyagi, Sep 10 '21 at 20:48

Allan Wind · Accepted Answer · 2021-09-10T21:06:02.297

This is how you fix the termination issue (that cause the error "RecursionError: maximum recursion depth exceeded while calling a Python object"):

  if m < 0.01: # was m == 0

and the logic error:

        elif m >= 0.05:
            coin_count += math.floor(m / 0.05) # was 0.1
            m = m % 0.05

Here is revised version that eliminates the duplicated logic, and carries the count in the return value instead of as an argument:

import sys
import math

def get_change(m):
    coins = [0.25, 0.1, 0.05, 0.01]

    if m < coins[-1]:
        return 0

    for coin in coins:
        if m >= coin:
            count = math.floor(m / coin)
            m = m % coin
            return get_change(m) + count

m = float(input())
print(get_change(m))

It's better to do the calculations in cents (i.e. 100 * m) so you deal with integers.

Why doesn't this recursive function work for counting number of coins due in change?

1 Answers1