Understanding how is a function evaluated using recursion

[Neil Cerutti]

On 2013-09-25, Arturo B <a7xrturodev at gmail.com> wrote:
> Hi, I'm doing Python exercises and I need to write a function
> to flat nested lists as this one: 
>
> [[1,2,3],4,5,[6,[7,8]]]
>
> To the result:
>
> [1,2,3,4,5,6,7,8]
>
> So I searched for example code and I found this one that uses
> recursion (that I don't understand):
>
> def flatten(l):
>     ret = []
>     for i in l:
>         if isinstance(i, list) or isinstance(i, tuple):
>             ret.extend(flatten(i)) #How is flatten(i) evaluated?
>         else:
>             ret.append(i)
>     return ret
>
> So I know what recursion is, but I don't know how is 
>
>                        flatten(i)
>  
> evaluated, what value does it returns?

It only *looks* like magic, as others have explained.

I keep a file callled bikeshed.py for these occasions. The
flatten function has been to the bike shed a lot [1]. Here's a
non-recursive version of flatten for comparison:

from collections import Sequence

def flatten(seq):
    stack = []
    i = 0
    result = []
    while True:
        if i >= len(seq):
            if stack:
                seq, i = stack.pop()
            else:
                return result
        elif isinstance(seq[i], Sequence):
            stack.append((seq, i+1)) # Store the continue point
            seq = seq[i]
            i = 0
        else:
            result.append(seq[i])
            i += 1

When this version encounters a nested list, it keeps a stack of
sequences and indices to continue on with after processing the
nested list. The code at the start of the while loop, when a
sequence is exhausted, pops the continue points fromt he stack,
returning if the stack is empty.

It's simpler and cleaner to call flatten on itself, as in the
recursive version, because the stack frames do all the
bookkeeping for you. CPython has a limited number of stack frames
though, so the version above might be preferable for certain
levels of nesting.

[1] http://en.wiktionary.org/wiki/bikeshed

-- 
Neil Cerutti