### Thread: Help with python recursion

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
15
Rep Power
0

#### Help with python recursion

hello everyone,
I tried to create a program which received a number (n) and a list of coins.
the program needs to find all the possibilities of creating with the list of coins content in order to find the number n.

example:
lets say I got n=10.
and I have a list of [5,10]
the program should give me all the possibilities which are: [5,5] and [10].
note ( I must use only recursion, no"while" or something to replace it )
now I created a code, but frankly , I am lost in my own code.
I got this program to assist me find all the possibilities
Code:
```def permuste(elements):
if len(elements)==0:
return[[]]
permutation=[]
for curr in elements:
elements_minus_curr=elements[:]
elements_minus_curr.remove(curr)
sub_perms=permuste(elements_minus_curr)
for perm in sub_perms:
perm.append(curr)
permutation.extend(sub_perms)
return permutation
elements=[1,2,3]
d=permuste(elements)
print d```
so I tried to follow this form of program into my program,
and ended up with this:
Code:
```def find_changes(n, coins):

if n < 0:
return []
if n == 0:
return [[]]

all_changes = []

for last_used_coin in coins:
if n==sum(coins):
all_changes.extend(coins)
all_used_but_one=coins[:]
all_used_but_one.remove(last_used_coin)
new_group_of_coins= find_changes(n,all_used_but_one)

if n==sum(find_changes(n,all_used_but_one)):
for new in new_group_of_coins:
str(last_used_coin)
str(new)
new.append(last_used_coin)

all_changes.extend(new_group_of_coins)

return all_changes
n=2
coins=[1,2]
d=find_changes(n, coins)
print d```
now, in my code I get a lot of errors such as "'int' object has no attribute 'append'"
I tried to fix it, but it only led to more errors.

I ask of you please, tell me if my code is something near to what I desire of it to be, if it is, could you please tell me how can I fix all of those errors?
if it is not even near to what is desire of it , could you tell me how I should build this program?
I thank you vary much for reading this far, and hope you could help me somehow.
I thank you all, and good day.
2. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
May 2009
Posts
530
Rep Power
34
Some logic is the place to start. The function receives a list [1, 5, 10] and wants to find all coins that will add up to ten. Take the first element and divide 10 by it and see if it is evenly divisable. Slice the first element off the list and do a recursive call to the function to repeat with the next element. Add some print statements while testing to see if the logic is working correctly, and too see what is returned by the function, and you should be good to go. So, for starters, create a function that works correctly for one value in the list and then add in the recursion.
Last edited by dwblas; November 9th, 2013 at 01:05 PM.
3. logic is a good idea, "evenly divisible" isn't particularly useful. Let's try this:
Code:
```def change(total, denominations, current, result):
'''
doctest.  Run doctest with command
\$ python -m doctest thisfile.py

>>> result = []
>>> change(total = 10, denominations = [5, 10], current = [], result = result)
>>> assert len(result) == 2
>>> assert [5, 5] in result
>>> assert [10] in result
'''

# recursion rule:  find a way to stop the recursion
s = sum(current)
if s == total:                        # if the sum is correct, append the result
result.append(current)
if total <= s:                        # if the sum is correct or too large, return.
return

# recursively try all the possibilities
for denomination in denominations:
change(total, denominations, current+[denomination], result)```
Simple, and it passes the test, but I think it's wrong. Example:
Code:
```>>> result = []
>>> change(10, [1, 5, 10], [], result)
>>> print(result)
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 5, 1], [1, 1, 1, 5, 1, 1], [1, 1, 5, 1, 1, 1], [1, 5, 1, 1, 1, 1], [5, 1, 1, 1, 1, 1], [5, 5], [10]]```
Change does not depend on order. The algorotithm could additionally post process the output by sorting each of the lists then retain only the unique entries.

Or we could not create the entries in the first place. This version of the algorithm works from biggest to smallest thereby avoiding the problem.
Code:
```def change(total, denominations, current, result):
'''
doctest.  Run doctest with command
\$ python -m doctest thisfile.py

>>> result = []
>>> change(total = 10, denominations = [5, 10], current = [], result = result)
>>> assert len(result) == 2
>>> assert [5, 5] in result
>>> assert [10] in result
'''
# recursion rule:  find a way to stop the recursion
s = sum(current)
if s == total:                        # if the sum is correct, append the result
result.append(current)
if total <= s:                        # if the sum is correct or too large, return.
return

denominations.sort(reverse = True)  # use a sorting step
# recursively try all the possibilities
for (i, denomination,) in enumerate(denominations):
change(total, denominations[i:], current+[denomination], result)```
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
15
Rep Power
0
I found out there is a simple solution to my problem.
:
Code:
```

def find_changes(n, coins):

if n < 0:
return []
if n == 0:
return [[]]

all_changes = []

for last_used_coin in coins:

new_coins=coins[:]
new_coins.remove(last_used_coin)

t=find_changes(n-last_used_coin,coins)
for coin in t:
coin.append(last_used_coin)
all_changes.extend(t)

return all_changes

n=10
coins=[1,2,5]
d=find_changes(n, coins)
print d```
5. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
May 2009
Posts
530
Rep Power
34
I did not find the single [10] entry when running this code. Take a look at the "coins" list if you want to include it.
the program should give me all the possibilities which are: [5,5] and [10].
Last edited by dwblas; November 10th, 2013 at 05:43 PM.
6. The useless statements

new_coins=coins[:]
new_coins.remove(last_used_coin)

have no benefit.