Divide List Using Recursion

I am trying to implement this function using recursion, the function takes a function parameter f where when passed a value it will return as true or false. It should check all val

Solution 1:

Recursive version.

But I agree with others that it is better to do this without recursion.

def divL(f, l):

    if not l:
        return ([],[])
    else:
        a, b = divL(f,l[1:])

        if f(l[0]):
            a.insert(0, l[0])
        else:
            b.insert(0, l[0])

        return (a, b)

#-- test ---

def f(x): return x > 0

divL(f,[1,-2,3,4,2,-5])

([1, 3, 4, 2], [-2, -5])

Solution 2:

To solve this problem recursively, then you can start with:

def div_l(fn, elements):
    if not elements:
        return ([], [])
    else:
        trues, falses = div_l(fn, elements[1:])
        if fn(elements[0]):
            trues.append(elements[0])
        else:
            falses.append(elements[0])
        return (trues, falses)

One thing to note about your code, is that, at the moment, there are no recursive calls. In the code above, our base case is when the list of elements is empty (if not elements). Then, we constantly check the first element of the list to see if it satisfies fn, appending it to trues or falses appropriately. Then we pass all the elements of the list besides the first one (elements[1:]) to the function again and repeat until the list is empty.

Having said that, the problem does not seem to be recursive in nature. Why not just use list comprehensions:

a = [element for element in l if f(element)]
b = [element for element in l if not f(element)]

Also, names like a, b, l and f are not great because they say nothing about what they actually mean.

Regarding the way you have written your code so far, the Pythonic way to iterate through the elements of a list is not the same as languages like C/C++/Java/etc; you should rarely need to get list items using their index. Instead you can re-write your for statement as follows:

for element in l:
   if f(element):
        a.append(element)

   else:
        b.append(element)

P.S. I haven't tested the code above yet, but it should be a reasonable starting point.

Solution 3:

Recursive function that takes split lists as parameters:

def _R(f, l, ts, fs):
  if not l:
    return ts, fs
  if f(l[0]):
    return _R(f, l[1:], ts + l[:1], fs)
  return _R(f, l[1:], ts, fs + l[:1])

def R(f, l):
  return _R(f, l, [], [])

print R( lambda x: x > 10, range(20) )