Recursive solution?

Question

We've got 3 kind of coins ($1,$2,$5) and we are going to have a mixture of these coins in order to make $1000. We want the number of all possible ways of creating $1000 using these coins and also we need to print each possible way.

I've just written the below code for the question of coins in a non-recursive style and it is working properly.
Now I need to write a recursive function that do the same thing but I just can't figure out the base case of my recursive function. Any ideas for writing a recursive function?

i=0
for x in range(1001):
  for y in range(501):
    for z in range(201):
        if x + 2*y + 5*z == 1000:
            print(" {} coin $1 , {} coin $2 , {} coin $5".format(x,y,z))
            i+=1
print("number of possibilities",i)

Answer 1

The accepted answer by Sabuj Hassan is incorrect, here is a correction. I've also added package invocation_tree to show the invocation tree of recursive function calls:

import invocation_tree as ivt # see link above for install instructions

def counts(x, y, z, make):
    if(x + y + z > make):
        return 0 # going over 'make': 0 possibility

    if x + y + z == make:
        print("{} coin$1, {} coin$2, {} coin$5".format(x, y//2, z//5))
        return 1 # matching 'make': 1 possibility

    possibilities = 0
    if x == 0 and y == 0: # start with $5, but don't add $5 after adding $2 or $1
        possibilities += counts(x, y, z+5, make)
    if x == 0:            # then $2, but don't add $2 after adding $1
        possibilities += counts(x, y+2, z, make)
    possibilities += counts(x+1, y, z, make) # then $1
    return possibilities # return sum of possibilities of children

tree = ivt.blocking()
possibilities = tree(counts, 0, 0, 0, 7) # make $7 to keep the tree small
print('possibilities:', possibilities)

After pressing <Enter> repeatedly, this then results in:

0 coin$1, 1 coin$2, 1 coin$5
2 coin$1, 0 coin$2, 1 coin$5
1 coin$1, 3 coin$2, 0 coin$5
3 coin$1, 2 coin$2, 0 coin$5
5 coin$1, 1 coin$2, 0 coin$5
7 coin$1, 0 coin$2, 0 coin$5
possibilities: 6

Full disclosure: I am the developer of invocation_tree.

Answer 2

Here is a recursive and dynamic way. Take your pick:

def dynamic(tgt,coins):
    combos = [1]+[0]*tgt
    for coin in coins:
        for i in range(coin, tgt+1):
            combos[i] += combos[i-coin]
    return combos[tgt]         

def recursive(tgt,coins):
    if coins==[1]: return 1
    coin = coins.pop()
    return sum(recursive(tgt%coin + coin*n, coins[:]) for n in range(tgt//coin+1)) 

print(dynamic(1000,[1,2,5])) 
# 50401
print(recursive(1000,[1,2,5]))  
# 50401

Answer 3

Try this:

def changes(amount, coins):
    possibilities = [0] * (amount + 1)
    possibilities[0] = 1
    for coin in coins:
        for j in range(coin, amount + 1):
            possibilities[j] += possibilities[j - coin]
    return possibilities[amount]

print(changes(1000, [1,2,5]))
#50401

Answer 4

I really doubt whether recursive is a best approach for doing this. Dynamic programming will always suit best for this kind of tasks. Here is a recursive code.

def counts(x, y, z):
    if(x + y + z > 1000):
        return

    if x + y + z == 1000:
        print(" {} coin $1 , {} coin $2 , {} coin $5".format(x,y/2,z/5))

    counts(x+1, y, z)
    counts(x, y+2, z)
    counts(x, y, z+5)


counts(1, 2, 5)

Answer 5

Here's a simple solution. But it will generate duplicate solutions. Dynamic programming would still be better to solve the problem.

>>> def coins(total, coins1=0, coins2=0, coins5=0):
...     if total == 0:
...             print "%s 1$, %s 2$, %s 5$" % (coins1, coins2, coins5)
...             return
...     if total < 0:
...             return
...     coins(total - 1, coins1 + 1, coins2, coins5)
...     coins(total - 2, coins1, coins2 + 1, coins5)
...     coins(total - 5, coins1, coins2, coins5 + 1)
...
>>> coins(1000)

Answer 6

aga has already listed base cases, but referred to SICP for how to do the recursion (reputedly an excellent book - I haven't read it though I'll warn you I do know it targets Scheme - a Lisp dialect).

Basically, what you need to do for each recursive step is...

1. Check whether you've reached a base case. If so, determine whether you've found a valid solution or not, and output a solution if needed. Either way, return (backtrack) to find more solutions.

2. Otherwise, choose each possible coin type in turn, updating totals and making the recursive call for each.

The totals you'd pass for each call must include the count for each coin value, and may also include the total value so far (though you could equally calculate that whenever you need it).

Pseudocode...

def recursive_solution (totals) :
  if found_a_base_case :
    if its_a_valid_solution_base_case :
      output solution
  else
    derive totals for adding another $5
    recursive_solution (those_new_totals)

    derive totals for adding another $2
    recursive_solution (those_new_totals)

    derive totals for adding another $1
    recursive_solution (those_new_totals)

As I mentioned in the comments, this will do lots of redundant work - one side-effect is that it will tend to find each solution multiple times. To prevent that, you need to remember which solutions you've already found. If you also remember partial solutions you've already tried and use that to avoid re-doing that work, that's called memoization.

Answer 7

You have three base cases:

• If the total amount of money to create equals to 0 you have only one way to create this sum.
• If total amount money to create is less than 0, there is no way to create the sum - so there're 0 ways.
• If there're 0 kinds of coins, you can't make any sum from them, so there're 0 ways.

If you need an in-depth explanation of recursive approach of solving this problem, you can read it in "Structure and Interpretation of Computer Programs" (I've read it in my native language, so I can't point you to the exact page - it has to be somewhere in section named like "Recursion").