so i know how to add the numbers in a list recursively

``````def ListSum(list):
if list = []:
return 0
else:
return list[0] + ListSum(list[1:])``````

but how would i go about subtracting a list from a list using recursion? does anyone know how/ where i could go to learn how to do so

3
Contributors
6
Replies
8
Views
7 Years
Discussion Span
Last Post by pyTony

I don't know what you mean by 'subtracting lists'. With your `listSum()` you implicitly start with the accumulator set to 0. What is the initial value of the accumulator for a subtraction? Or do you want to 'subtract' one list from another? As a set or each element from its matching element?
Assuming the first:

``````def listSubtract(accum,alist):
if not alist: # bad form to use keyword "list" to name a variable
return accum
else:
return listSubtract(accum-alist[0],alist[1:])``````

Edited by griswolf: n/a

im trying to subtract one list from another

That is not a complete specification of your requirement. Are you trying to subtract "element by element"? Then what about mismatched length? Suppose you have

``````lhs = [1,1]
rhs = [1,1,1]
[B]???[/B] = subtract(lhs, rhs) # lhs - rhs``````

Or maybe you mean "set-like" subtraction? Or subtract the sum of one from the sum of the other?

Edited by griswolf: n/a

heres the exact question that i am trying to solve,
write in python a recursive function "subtract" that takes as parameters two lists of integers. the list are sorted and contain no duplicates.(they represent sets) the function returns a sorted list of integers, without duplicates, representing the set-difference. for instance subtract([1,2], [2,3]) should return 1

OK. There is an easy way and a hard way (of course). The easy way is to use the built in `set` container, but of course that doesn't meet the spec. Just for a warm up:

``````def subtract(lhs, rhs):
return sorted(list(set(lhs) - set(rhs))``````

Now, you need to do the recursive work yourself, so I'm not going to write the code. Think this way: If I know the first element in `lhs` is in `rhs` then the return value will not hold that value, otherwise it will. Depending on whether the return list holds the first element of the left list, the recursion may involve either or both lists. The base case needs a little thought too.

Edit: Notice that the problem statement does not require you to do the work in place: The returned list and each of the argument lists can be distinct; and the argument lists can remain unchanged.

Edited by griswolf: n/a

Griswolf is right, I got mixed up. I remembered that you wanted union, but you want to take out common elements, like in this not recursive version:

``````def diff(a,b):
return list(item for item in a if item not in b)``````

Edited by pyTony: n/a