Calling a function recursively

Question

I have 10, 20, 50 notes and when I need to pay any amount, I need to find the best combination. So for e.g. when I need to pay 7 I will pay a note of 5 and 2

I have a function that will calculate this. But I need to run the same function 3 or 4 times as shown below. How do I call the function recursively?

my_dir={}
import bisect
def my_change(my_amount):
    c=[1,2,5,10,20,50,100,500]
    my_pos=bisect.bisect(c, my_amount)
    my_val=c[my_pos-1]
    my_num=my_amount//my_val
    my_recurr=my_amount-(my_num*c[my_pos-1])
    my_dir[my_val] = my_num
    return my_recurr

Is there any better way to calculate this?

my_change(417)
17

my_change(17)
7

my_change(7)
2

my_change(2)
0

my_dir
{2: 1, 5: 1, 10: 1, 100: 4}

---

update:

And depending upon what is available, the combination may change!

available_cash={1:20, 2:10, 10:100, 50:100, 100:1, 500:1}

should result in this:

actual_pay={1:1, 2: 3, 10: 1, 50:6, 100: 1}

---

Update:

Is there any better way to code this ?

amt=417
my_dict={}
available_cash={1:20, 2:10, 10:100, 50:100, 100:1, 500:1}
new_list=sorted(available_cash, reverse=True)

for key in new_list:
    if amt >= key * available_cash[key]:
        my_dict[key] = available_cash[key]
        amt = amt - (key * available_cash[key])
    else:
        if amt >= key:
            notes = amt // key
            amt = amt - (key * notes)
            my_dict[key] = notes

---

Update 1:

And if I need to find the notes left in the ATM after the payment, I can use counter

from collections import Counter
A = Counter(available_cash)
B = Counter(my_dict)

A - B
Counter({10: 99, 50: 94, 1: 19, 2: 7, 500: 1})

Answer 1

So, since you've edited the question we've got new requirements.
The code I'm going to propose is a little bit longer than yours but it takes into account that you actually should also modify available_cash since you're taking the money from the ATM. It's obvious that withdrawal of money makes the amount of notes available in the machine lower.

from collections import OrderedDict

amount = 417
available_cash = OrderedDict((
    (1, 20), (2, 10), (10, 100), (50, 100), (100, 1), (500, 1)
))

def my_change(amount, available_cash):
    change = {}
    for note in reversed(available_cash.keys()):
        note_count = amount / note
        if note_count == 0:
            continue
        elif note_count > available_cash[note]:
            note_count = available_cash[note]
            available_cash[note] = 0
        else:
            available_cash[note] -= note_count
        change[note] = note_count
        amount -= note_count * note
        if amount == 0:
            break
    return change

print my_change(amount, available_cash)

I've also dropped the idea of recursive function calls.
The other important thing from stdlib is the OrderedDict class.

Answer 2

Recursion isn't encouraged in Python. Python can't optimize tail-call recursion, and it limits the maximum depth of recursive calls (although that limit can be modified). This particular application will not recurse deeply, but still it's best to avoid recursion in Python unless it's appropriate for the problem, eg walking a tree structure.

This problem can easily be solved by iteration, using a greedy algorithm (how appropriate for a task connected with money :) ). At each stage, simply remove multiples of the highest note that's smaller than the current amount.

For example:

#!/usr/bin/env python

all_notes = [1, 2, 5, 10, 20, 50, 100, 500]

def my_change(amount):
    my_notes = list(all_notes)

    change = {}
    print amount
    while amount > 0:
        while my_notes[-1] > amount:
            my_notes.pop()
        note = my_notes[-1]
        num, amount = divmod(amount, note)
        print '%d x %d = %d, %d' % (num, note, num * note, amount)
        change[note] = num
    return change

print my_change(9)
print my_change(26)
print my_change(873)

output

9
1 x 5 = 5, 4
2 x 2 = 4, 0
{2: 2, 5: 1}
26
1 x 20 = 20, 6
1 x 5 = 5, 1
1 x 1 = 1, 0
{1: 1, 20: 1, 5: 1}
873
1 x 500 = 500, 373
3 x 100 = 300, 73
1 x 50 = 50, 23
1 x 20 = 20, 3
1 x 2 = 2, 1
1 x 1 = 1, 0
{1: 1, 2: 1, 100: 3, 50: 1, 500: 1, 20: 1}

I've added some print statements to the function so you can follow what's happening.

The heart of the my_change() function is the built-in divmod() function which performs a division, returning the quotient and the remainder as a tuple. my_change() also uses the list.pop() method to remove notes that are too big from my_notes, which is a temporary copy of the all_notes list.

It would be easy to modify this function to take my_notes as a parameter, so it could be used if the full collection of notes is not available for some reason.

---

The code in the question uses bisect. That's great for working with large sorted lists, but it's overkill for small lists - a simple linear search is faster than bisect for small lists.

Answer 3

You can use something like:

my_dir = {}
change = 417
def my_change(my_amount):
    # Your function code here
while change > 0:
    change = my_change(change)

But actually, your code can be simplified and the solution with recursion is:

def my_change(amount, i=None):
    c = [1, 2, 5, 10, 20, 50, 100, 500]
    if i is None:
        i = len(c) - 1
    note = c[i]
    n, rest = divmod(amount, note)
    result = {}
    if n > 0:
        result[note] = n
    if rest > 0:
        result.update(my_change(rest, i - 1))
    return result

No need for bisect or complex calculations.

Answer 4

If you insist on doing it recursively you could do so using a little helper function which invokes itself with an ever-decreasing amount (until it hits zero), passing itself the set of notes used so far. Like

import collections

notes = [500, 100, 50, 20, 10, 5, 2, 1]

def my_change(amount):
    def go(amount, notesUsed):
        if amount <= 0:
            return notesUsed
        largestNote = next(x for x in notes if x <= amount)
        notesUsed[largestNote] += 1
        return go(amount - largestNote, notesUsed)

    return go(amount, collections.defaultdict(int))

go is a local helper function performing the actual recursion and a defaultdict is used for counting the notes.

Answer 5

you don't even need to use recursion, you can wrap inside a while, so it will keep calculating until the change is 0, basically is the same thing that you did manually, but with just 1 run :

my_dir={}
import bisect
def my_change(my_amount):
    my_dict={}
    c=[1,2,5,10,20,50,100,500]
    while (my_amount > 0 ):
        my_pos=bisect.bisect(c, my_amount)
        my_val=c[my_pos-1]
        my_num=my_amount//my_val
        my_recurr=my_amount-(my_num*c[my_pos-1])
        my_dir[my_val] = my_num
        my_amount = my_recurr
    return my_dir