First, thanks for any help.

I have this recursive code for counting ways of change from a list of coins and a given amount.

I need to write a recursive generator code that presents the ways in every iteration. Example at the end:

This is the code:

def countChange(amount, coins):if (amount == 0):return 1elif (amount < 0 or coins == []):return 0else:return (countChange(amount, coins[:-1]) + countChange(amount - coins[-1], coins))

Now, I need to present the ways with a recursive generator. I have a part of the code that I need to write:

def change_gen(amount, coins):if amount == 0:yield ?????elif not (amount < 0 or coins == []):g = change_gen(amount, coins[:-1])????? 

This should be the output for example:

 for e in change_gen(5,[1,2,3]):print(e)[1, 1, 1, 1, 1][1, 1, 1, 2][1, 2, 2][1, 1, 3][2, 3]

Btw this reminds me of Problem 31.

If you are using Python 3.3+ we can write change_gen with yield from:

def change_gen(amount, coins):if amount == 0:yield 1elif amount < 0 or not coins:yield 0else:yield from change_gen(amount, coins[:-1])yield from change_gen(amount - coins[-1], coins)

or without yield from

def change_gen(amount, coins):if amount == 0:yield 1elif amount < 0 or not coins:yield 0else:for element in change_gen(amount, coins[:-1]):yield elementfor element in change_gen(amount - coins[-1], coins):yield element

Tests

import randomfor _ in range(10):amount = random.randint(0, 900)coins = list({random.randint(1, 100)for _ in range(random.randint(1, 10))})assert countChange(amount, coins) == sum(change_gen(amount, coins))

worked fine, so it seems to give similar output

Note

You should remember that for large values of amount and small coins we may reach recursion limit (max depth is near 1000 on my machines).

EDIT

if you want to get which coins were used we can add extra parameter for them

def change_gen(amount, left_coins, used_coins):if amount == 0:yield used_coinselif amount < 0 or not left_coins:yieldelse:yield from change_gen(amount, left_coins[:-1],used_coins=used_coins[:])yield from change_gen(amount - left_coins[-1],left_coins,used_coins[:] + [left_coins[-1]])

possible problem here is that in situations when amount is negative or no coins left None object will be yielded, but it's ok, we can filter them from results using filter:

for e in filter(None, change_gen(5, [1, 2, 3], used_coins=[])):print(e)

gives us

[1, 1, 1, 1, 1]
[2, 1, 1, 1]
[2, 2, 1]
[3, 1, 1]
[3, 2]