Understanding how is a function evaluated using recursion in python

Question

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?

Answer 1

In this case, flatten always returns a list. When it hits the recursion, it calls itself to get another list, that it uses to extend the current list.

Answer 2

Try a simpler version first:

def flatten(l):
 ret = []
 for i in l:
 if isinstance(i, list) or isinstance(i, tuple):
 # Append the contents of the item.
 ret.extend(i)
 else:
 # Append the item itself.
 ret.append(i)
 return ret

In this example, flatten([[1,2,3],4,5,[6,[7,8]]]) returns [1,2,3,4,5,6, [7,8]].

The problem here is that a sublist can itself contain a list.

It would be nice if there were a function which, when given [6,[7,8]], would return [6,7,8] so that you could append those items. But that's exactly what flatten does! Try adding prints to tell you what was passed in and what is returned.

Answer 3

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 [http://en.wiktionary.org/wiki/bikeshed]. 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 from the 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.