Merging two lists using recursion

Question

I want to merge every other element of 2 lists with different lengths into one list. I am not allowed to use the built-in function zip and must use recursion.

From print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10])) the result should be: [1, 2, 3, 4, 5, 6, 8, 10].

This is my code so far:

def zippa(l1, l2): 
    if len(l1) == 0:
        return l2[0] + zippa(l1,l2[1:])
    elif len(l2) == 0:
        return l1[0] + zippa(l1[1:],l2)
    elif len(l1) == 0 and len(l2) == 0:
        return 0
    else:
        return zippa(l1[1:0],l2) + zippa(l1,l2[1:0])

I don't understand how to get the values back into a list. Does the order of the elif and such matter?

Answer 1

Simple but quadratic:

def zippa(l1, l2):
    if l1:
        return l1[:1] + zippa(l2, l1[1:])
    return l2[:]

Linearithmic, and logarithmic recursion depth, by splitting at the half-point of the first list:

def zippa(l1, l2):
    h = len(l1) // 2
    if not h:
        return l1 + l2
    return (
        zippa(l1[:h], l2[:h]) +
        zippa(l1[h:], l2[h:])
    )

Attempt This Online!

Answer 2

I am not allowed to use the built-in function zip and must use recursion.

This is unfortunate. Your professor or instructor (apologies for the assumption that this is an academic project; if it's not, the same sentiment applies) is forcing you to misapply recursion. It's like trying to put out a fire with a bottle of champagne instead of a fire extinguisher. When you finish the class, please use a builtin and iteration!

Generally speaking, iteration is almost always the correct tool for operations on lists in Python. There are other problems where recursion is actually suitable, like traversing a tree, because the recursive step breaks the problem down by a sublinear factor. There's no dividing and conquering happening here.

Some reasons why recursion is a poor replacement for iteration:

• Every recursive call takes extra computational work to allocate and destroy call frames that loops don't.
• CPython has a recursion limit of around 1000 by default, so if your lists are longer than that (and they will be, for any nontrivial application), your program will crash. You can't indefinitely extend the call stack size, so sys.setrecursionlimit is an unsafe hack.
• Call frames don't share state with one another, so you're forced to do ugly things like add indexes to parameters or copy the entire list on every call with a slice (as you're doing), leading to unnecessary quadratic complexity at worst (as is the case here) or just awkward code (for example, if you want to build a result list, as is the case here).

Some languages support tail call optimization and are naturally suited to writing algorithms like this, but Python isn't one of them.

That said, I understand this is a pedagogical exercise, so let's play along and learn something about recursion.

---

I'd also like to offer a few general programming tips before diving in.

When you're stuck working on an algorithm, try simplifying the problem. See if you can merge two lists of equal length, then, once that's working, add the additional requirement of the lists being different lengths. This would eliminate checks for one list being empty and the other not and generally make the problem easier to grasp. When you go to tackle the full problem, you already have minimal working code for a subproblem and experience and patterns you've gained from solving issues in the smaller problem space.

The code here seems like you've jumped ahead, wrote it up without testing along the way, and have made a series of decisions and assumptions that don't make sense taken individually. Take smaller steps.

Print (or use a debugger) to inspect values at each frame. Work out the algorithm on small examples.

Essential reading: Eric Lippert - How to Debug Small Programs.

---

Let's inspect some of the small problems in the code and build up to the larger ones.

Does the order of the elif and such matter?

If the branch conditions are all disjoint, then order doesn't matter, as in:

if foo == "a": return 0
if foo == "b": return 1
if foo == "c": return 2

Since foo can't be "a", "b" and "c" at the same time, these branches are mutually exclusive. This is a nice simplifying assumption when you can get it (the code above could be refactored to a table lookup, removing the conditional chain completely).

But if you have dependent checks like

if len(l1) == 0:
    pass # l1 must be empty; l2 may or may not be
elif len(l2) == 0:
    pass # l2 must be empty and l1 is known to be nonempty
         # or the `len(l1) == 0` branch would have been taken
elif len(l1) == 0 and len(l2) == 0:
    pass # unreachable, we've already covered cases
         # where one or the other was empty

then order does matter. The case when both are empty should be checked first (you can use simply if lst: and if not lst: to check their emptiness Pythonically).

Consider the cases when one of the lists is empty:

if len(l1) == 0:
    return l2[0] + zippa(l1,l2[1:])

At this point, you can just return l2 -- when one list is empty, all you need to do is return the nonempty one rather than chop it down piece-by-piece. Due to the order of your branches, l2 isn't guaranteed to have an element -- it may well be empty.

Next, the code

elif len(l1) == 0 and len(l2) == 0:
    return 0 # ??!

has an inconsistent type. We're trying to return a list, so the base case of two empty lists is merged to one empty list, not the integer 0. This should be return [] so the caller is using + on two lists to concatenate them, not [] + 0, which raises a TypeError. A typed language would not let you write this, and even in a dynamically-typed language, it's generally an antipattern to mix types even when it works.

In the primary recursive case code, the slice l1[1:0] always gives an empty list. Breaking the problem down to a small chunk and trying it in the repl to test our hypothesis, we see:

>>> [1,2,3][1:0]
[]

Clearly, that's not what you intended. It looks like you're trying to encode the "alternation" pattern here, so you probably just wanted to chop off the first element as a list:

>>> [1,2,3][0:1]
[1]
>>> [1,2,3][:1]
[1]

Secondly, it's not clear to me how the zippa(l1[:1],l2) + zippa(l1,l2[:1]) pattern would work. We have an infinite loop because that first element will never be removed by any of the logic once it's there. Spawning more than 1 recursive call and merging the results isn't necessary for a linear list algorithm. It seems easiest to merge one of each of the elements from both lists in a single call -- there's no rule in recursion that says you can't.

Going back to the slicing, that's unnecessary quadratic complexity -- a lot of extra work just to shoehorn the algorithm to work recursively. We can solve both the complexity problem and the slicing problem by passing an index into the recursive calls as a third parameter. This could be a default parameter, or it can be added on an inner or helper function.

As a final optimization point that also makes the code simpler: every + operator on lists allocates a whole new list! If we do this on every frame, we're back to quadratic complexity. Merging lists must only involve a constant number of allocations (preferably one) if it's to be usable for any nontrivial purpose. This can be done by passing a single result list through the recursive calls, allocating it one time on the first call.

Here's the code:

def merge_iterables(a, b, i=0, result=None): 
    if result is None:
        result = []

    if i < len(a) and i < len(b):
        result.append(a[i])
        result.append(b[i])
        merge_iterables(a, b, i + 1, result)
    else:
        result.extend(a[i:])
        result.extend(b[i:])

    return result

If you don't like exposing those parameters to the caller, use an inner or helper function, typical of recursion:

def merge_iterables(a, b):
    result = []

    def merge(i=0):
        if i < len(a) and i < len(b):
            result.append(a[i])
            result.append(b[i])
            merge(i + 1)
        else:
            result.extend(a[i:])
            result.extend(b[i:])

    merge()
    return result

Note that although I'm slicing, it's in the one-off base case, so this is constant complexity (and one or both of the slices is empty anyway). You could use a traditional range loop to avoid these allocations, but that's a premature optimization.

---

Although it's not part of your assignment, an algorithm like this should generalize to any number of lists. This is easy by adding a loop:

def merge_iterables(*its):
    result = []

    def merge(i=0):
        for x in its:
            if i < len(x):
                result.append(x[i])

        if any(i < len(x) for x in its):
            merge(i + 1)

    merge()
    return result

Time and space complexity here is O(nm).

Finally, generators are a Pythonic way to deal with iterable algorithms like this. itertools uses generators for everything, and it's good to follow suit. Generators give the caller maximum flexibility: they can use the same algorithm to merge, say, the first half of an iterable, or do it over time, lazily, in a memory-efficient manner (these use cases are part of the motivation why you want your algorithm to use constant space!)

def merge_iterables(*its):
    def merge(i=0):
        for x in its:
            if i < len(x):
                yield x[i]

        if any(i < len(x) for x in its):
            yield from merge(i + 1)

    yield from merge()

if __name__ == "__main__":
    print(list(merge_iterables([1,2], [4,5,6,7], "a", "xyz")))
    # => [1, 4, 'a', 'x', 2, 5, 'y', 6, 'z', 7]

---

After all that, this is still a contrived and poor use case for recursion (try it on a 1000-element list if there's any lingering doubt), so you might want to see my suggested solution to the problem in the canonical thread Pythonic way to combine two lists in an alternating fashion?.

Let's benchmark some of the code in that answer along with the code in this answer and the quadratic solution given in this other answer.

import argparse
import copy
import dis
import inspect
import random
import sys
import timeit
from itertools import zip_longest

sys.setrecursionlimit(1350) # just for testing

def merge_pythonic(*its):
    return [x for y in zip_longest(*its) for x in y if x is not None]

def merge_iterables(*its):
    result = []

    def merge(i=0):
        for x in its:
            if i < len(x):
                result.append(x[i])

        if any(i < len(x) for x in its):
            merge(i + 1)

    merge()
    return result

def zippa(*its):
    if len(its) == 0:
        return []
    
    head_list, *rest_its = its
    
    if head_list:
        head, *rest = head_list
        return [head] + zippa(*rest_its, rest)
    else:
        return zippa(*rest_its)

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("--n", type=int, default=1300)
    parser.add_argument("--m", type=int, default=1300)
    parser.add_argument("--trials", type=int, default=1000)
    parser.add_argument("--dis", action="store_true")
    args = parser.parse_args()
    n = args.n
    m = args.m
    trials = args.trials
    namespace = dict(its=[random.sample(range(n), k=n) for _ in range(m)])
    funcs_to_test = [x for x in locals().values() 
                     if callable(x) and x.__module__ == __name__]
    print(f"{'-' * 30}\nn = {n}, {trials} trials\n{'-' * 30}\n")

    for func in funcs_to_test:
        fname = func.__name__
        fargs = ", ".join(inspect.signature(func).parameters)
        stmt = f"{fname}({fargs})"
        setup = f"from __main__ import {fname}"
        time = timeit.timeit(stmt, setup, number=trials, globals=namespace)
        print(inspect.getsource(globals().get(fname)))

        if args.dis:
            dis.dis(globals().get(fname))

        print(f"time (s) => {'%.16f' % time}\n{'-' * 30}\n")

Even with the unfortunate restriction that we can't use larger tests than a thousand elements or so (argh! recursion!), the results are clear: the builtin smashes the recursive approaches, and quadratic doesn't scale as predicted, even on the tiny input (real-world iterables can often be hundreds of thousands, millions or billions of elements or more):

------------------------------
n = 1300, m = 1300, 1000 trials
------------------------------

def merge_pythonic(*its):
    return [x for y in zip_longest(*its) for x in y if x is not None]

time (s) => 0.4278396000000000
------------------------------

def merge_iterables(*its):
    result = []

    def merge(i=0):
        for x in its:
            if i < len(x):
                result.append(x[i])

        if any(i < len(x) for x in its):
            merge(i + 1)

    merge()
    return result

time (s) => 4.4487939000000001
------------------------------

def zippa(*its):
    if len(its) == 0:
        return []

    head_list, *rest_its = its

    if head_list:
        head, *rest = head_list
        return [head] + zippa(*rest_its, rest)
    else:
        return zippa(*rest_its)

time (s) => 40.0880948000000004
------------------------------

Answer 3

A classic way to handle recursion with lists is to split off the head of the list and then do something with the rest. This is a pattern you will see everywhere in functional languages the make recursion a first class citizen. It's not a first-class citizen in Python, but you can still use Python to learn these techniques.

Here we make a function that can zip any number of lists. This is handy, because once you exhaust the short list, you can continue calling it until there are no more lists without a lot of if/else.

def zippa(*lists):
    if len(lists) == 0:
        return []
    
    head_list, *rest_lists = lists
    
    if head_list:
        head, *rest = head_list
        return [head] + zippa(*rest_lists, rest)
    else:
        return zippa(*rest_lists)
    
print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10])) 

The only really complication in this assignment is that you are dealing with multiple lists. But the idea is the same, each call is responsible for taking the first list, then from the list take the first element. Then return that element with the result of recursion.

This works by rotating the lists as you recurse. By passing the rest of the original first list in last: zippa(*rest_lists, rest).

This along with a well-chosen base case allows you to pass in any number of lists, which in turn makes the code simpler. You don't have to deal with indices or helper arguments.

# works with a single list
print(zippa([1, 3, 5]) )
# [1, 3, 5]

# or multiple:
print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10], [0, 0, 0, 0])) 
# [1, 2, 0, 3, 4, 0, 5, 6, 0, 8, 0, 10]