   # Understanding how is a function evaluated using recursion in python

172 views

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? posted Sep 25, 2013

+1 vote

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 Sep 26, 2013
+1 vote

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 Sep 26, 2013
+1 vote

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. answer Sep 26, 2013
Similar Questions

Can we consider `"a car a man a maraca"` as palindrome string?
Are they really a palindrome?

+1 vote

Write a recursive function:

``````int sum( int x, int max )
{
/* complete the code */
}
``````

that calculates the sum of the numbers from x to max (inclusive). For example, sum (4, 7) would compute 4 + 5 + 6 + 7 and return the value 22.

Note: The function must be recursive.