subtracting lists recursively

[jrp370]

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
thanks in advance

[griswolf]

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:])

[jrp370]

im trying to subtract one list from another

[griswolf]

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?

[jrp370]

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

[griswolf]

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.

[TrustyTony]

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)