On 2013-09-25, Arturo B <a7xrturo...@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 -- https://mail.python.org/mailman/listinfo/python-list