"Don't split a problem into 'the first' and 'the rest.' Instead, split a problem into roughly equal pieces; recursively solve subproblems, then combine subsolutions."

def interleave(xs, ys):
    for x, y in zip(xs, ys):
        yield x
        yield y

def scan(f, xs):
    if len(xs) < 2:
        return [0]
    sums = [f(xs[2*i], xs[2*i+1]) for i in range(len(xs)/2)]
    evens = scan(f, sums)
    odds = [f(evens[i], xs[2*i]) for i in range(len(xs)/2)]
    return interleave(evens, odds)

# (transliterated from NESL into Python)