How does this interleaving recursive function work?

Question

I'm trying to understand exactly how this recursive function works. I know that it takes two lists and interleaves them. Could someone enlighten me about the nested part of the function?

def interleave(lst):
    def interleaveHelper(lst1,lst2):
        if not lst1:
            return lst2
        elif not lst2:
            return lst1
        return lst1[0:1] + interleaveHelper(lst2, lst1[1:])
    return interleaveHelper(lst[:len(lst)/2], lst[len(lst)/2:])

Answer 1

The recursive nested function just takes the first element of the first argument, then swaps the arguments for the recursive call (minus that first element).

So given a list [1, 2, 3, 4], the outer call splits the list in two and the recursion then does:

([1, 2], [3, 4]) -> [1] + ([3, 4], [2])
    ([3, 4], [2]) -> [3] + ([2], [4])
        ([2], [4]) -> [2] + ([4], [])
            ([4], []) -> return [4]  # lst2 is empty, return lst1
        return [2] + [4]
    return [3] + [2, 4]
return [1] + [3, 2, 4]

Answer 2

Well, there are actually two different things defined and being used here. interleaveHelper will take the first elemente from the first list and then apply teh same function recursively but with the lists swapped. That means, that the next call it will take out the first element of the second list.

Now that this is clarified, you should see the other function: interleave. This function takes one list and split it at the half (see the last line) by slicing (for instance, lst[:len(lst)/2] is the first half). Then it takes the two halves and interleave them.

This means that the function will shuffle the items in a similar way as you shuffle the cards: split in halves and mix them one by one. :-)

A simple example would be:

In [2]: a = range(10)

In [3]: interleave(a)
Out[3]: [0, 5, 1, 6, 2, 7, 3, 8, 4, 9]

Answer 3

The interleave function is really interleaveHelper(l1, l2). Assume that you have 2 lists l1=[1,2,3] and another l2=['a', 'b', 'c', 'd', 'e'] as an example. Also lets call interleaveHelper(l1, l2) = f(l1,l2) for brevity. Then, the last line will give:

f([1,2,3], ['a', 'b', 'c', 'd']) = [1] + f(['a', 'b', 'c', 'd'], [2,3])
                                 = [1] + ['a'] + f([2,3], ['b', 'c', 'd']) 
                                 = [1, 'a'] + f([2,3], ['b', 'c', 'd'])
                                 = [1, 'a'] + [2] + f(['b', 'c', 'd'], [3])
                                 = [1, 'a', 2] + f(['b', 'c', 'd'], [3])
                                 = [1, 'a', 2] + ['b'] + f([3], ['c', 'd'])
                                 = [1, 'a', 2, 'b'] + f([3], ['c', 'd'])
                                 = [1, 'a', 2, 'b'] + [3] + f(['c', 'd'], [])
                                 = [1, 'a', 2, 'b', 3] + f(['c', 'd'], [])
                                 = [1, 'a', 2, 'b', 3] + ['c', 'd']
                                 = [1, 'a', 2, 'b', 3, 'c', 'd']

I think its very easy to understand in this way ...