iterative-vs-recursive.py

'''
    For a tree of nested lists with integer leaves, calculate the sum of all leaves.
'''

def recurse(root):
    # Slow because it creates a lot of lists (generators are even slower)
    return sum([child if isinstance(child, int) else recurse(child) for child in root])

def recurse2(root):
    # Faster because less intermediate objects are created.
    r = 0;
    for child in root:
        if isinstance(child, int):
             r += child
        else:
             r += recurse2(child)
    return r

def stack(root):
    # The stack approach. Faster than recurse(), slower than recurse2()
    stack = [root]
    result = 0
    while stack:
        for node in stack.pop():
            if isinstance(node, int):
                result += node
            else:
                stack.append(node)
    return result

def mktree(root, d, n):
    if d > 0:
        root.extend(mktree([], d-1, n) for x in range(n))
    else:
        root.extend(range(n))
    return root

# Binary tree with depth of 10
tree = mktree([], 10, 2)
print(tree)

import timeit
print(min(timeit.repeat(lambda: recurse(tree), number=1000, repeat=10)))
# 1.49238705635
print(min(timeit.repeat(lambda: recurse2(tree), number=1000, repeat=10)))
# 1.2206799984
print(min(timeit.repeat(lambda: stack(tree), number=1000, repeat=10)))
# 1.23453998566