Python-сообщество

f = lambda ls: reduce(lambda res, x: res+[x] if not isinstance(x,list) else res + f(x),ls,[])

def flatten(src_ls):
    res = []
    def make_flat(ls):
        for elt in ls:
            make_flat(elt) if (isinstance(elt,list)) else res.append(elt)
    make_flat(src_ls)
    return res

def hardcore(ls):
    res = []
    nested_elements = []
    positions = []
    for elt in ls:
        if isinstance(elt,list):
            nested_elements.append(elt)
        else:
            res.append(elt)
        idx = None
        offset = 0
        while nested_elements:
            nested_ls = nested_elements.pop()
            if positions:
                idx = positions.pop()
            got_nested = False 
            for nested_elt in nested_ls:
                if isinstance(nested_elt, list):
                    nested_elements.append(nested_elt)
                    positions.append(len(res)-offset)
                    got_nested = True
                else:
                    if got_nested:
                        offset += 1 
                    if idx:
                        res.insert(idx,nested_elt)
                        idx += 1
                    else:
                        res.append(nested_elt)
    return res

%%timeit
f([1,[2,3,4,[5,[6],7,8],9],10,11,[12,[13]]])
100000 loops, best of 3: 8.07 us per loop
%%timeit
flatten([1,[2,3,4,[5,[6],7,8],9],10,11,[12,[13]]])
100000 loops, best of 3: 5.48 us per loop
%%timeit
hardcore([1,[2,3,4,[5,[6],7,8],9],10,11,[12,[13]]])
100000 loops, best of 3: 8.38 us per loop

def recur(n):
...   if not n == 0:
...     hardwork()
...     recur(n - 1)

def loop(n):
     for i in range(n):
          hardwork()

>>> timeit.timeit('req(10)','from __main__ import req')
10.308371383998747
timeit.timeit('loop(10)','from __main__ import loop')
6.014963355999498