Understanding how is a function evaluated using recursion

[Arturo B]

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?

Thank you

 

[Josh English]

Hi, I'm doing Python exercises and I need to write a function to flat nested lists

So I know what recursion is, but I don't know how is

flatten(i)

evaluated, what value does it returns?

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.

Josh

 

[MRAB]

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?

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.

 

[Steven D'Aprano]

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?

You have the source code to flatten right there in front of you. The very
last line says:

return ret


The first line of the function sets:

ret = []

and it is a list which accumulates all the items seen. If you follow the
code with a simple non-nested list:

flatten([1, 2, 3])

flatten sets the return result "ret" to the empty list, then walks the
argument list extracting each item in turn, which results in this
sequence of calls:

ret = []
ret.append(1)
ret.append(2)
ret.append(3)
return ret # [1, 2, 3, 4]


Now if we do the same thing with a nested list:

flatten([1, [2, 3], 4])

the call to flatten does the same thing, walks the input list, only this
time it has a recursive call:

# outer call
ret = []
ret.append(1)

At this point, the item found is a list, so flatten([2, 3]) is called, so
Python drops into into a new call, building a new list called "ret",
leaving the old one untouched:

# inner call
ret = []
ret.append(2)
ret.append(3)
return ret # [2, 3]

At this point Python drops back to the first call again:

# outer call
ret.extend([2, 3])
ret.append(4)
return ret # [1, 2, 3, 4]

But it all together in one chunk, without the commentary:



flatten([1, [2, 3], 4]) =>
# outer call
ret = []
ret.append(1)
flatten([2, 3]) =>
# inner call
ret = []
ret.append(2)
ret.append(3)
return ret # [2, 3]
# outer call
ret.extend([2, 3])
ret.append(4)
return ret # [1, 2, 3, 4]


In principle, you can nest as many function calls as needed. In practice,
Python will stop after 1000 nested calls by default, although you can
tune it up and down.

 

[Dave Angel]

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:

I can't imagine why you'd use either i or l in this context, but
especially use them both when they look so much alike.

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?

flatten() returns a list, of course. The value of 'ret' in the inner
function.

What don't you understand about recursion? You write a function that's
valid for the simple case (a simple list, with none of the elements
being lists or tuples). Then you use that function inside itself to
handle the more complex cases.

 

[Terry Reedy]

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 is not clear what part of 'how' you do not understand this. Perhaps
that fact that a new execution frame with a new set of locals is created
for each call. So calling flatten from flatten is no different than
call flatten from anywhere else.

If a language creates just one execution frame for the function,
attached to the function (as with original Fortran, for instance), then
recursion is not allowed as a 2nd call would interfere with the use of
the locals by the 1st call, etc.

 

[rusi]

So I know what recursion is, but I don't know how is

flatten(i)

evaluated, what value does it returns?

When you are a noob, who do you ask? The gurus.
When you are a guru who do you ask? The computer!

And its really quite easy to ask the computer directly. Here's your code with a extra prints

def flatten(l):
print ("Received: %s" % 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)
print ("Returning: %s" % ret)
return ret

Now run it with a couple of different inputs (not neglecting the trivial cases) and see if it does not self-explain.

If still confusing, come back and ask!

 

[Neil Cerutti]

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, Sequence):
stack.append((seq, i+1)) # Store the continue point
seq = seq
i = 0
else:
result.append(seq)
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]

def flatten(seq):

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

In that spirit, it occurs to me that given current Python
nomenclature, 'flattened' would be a better name.

 

[Peter Cacioppi]

def flatten(seq):
[1] http://en.wiktionary.org/wiki/bikeshed

In that spirit, it occurs to me that given current Python

nomenclature, 'flattened' would be a better name.

The example presented here is simple enough for someone who is confident with recursion and somewhat new to Python. So perhaps a refresher on recursion would help.


The way to grok recursion for the first time is (a) to read some general info about it (Wikipedia has some decent stuff here, but there are many other sources) and (b) find a simple recursion example and play around with it in the debugger.

Python has some decent debugger solutions - I like using ipdb with iPython.

The factorial function is a good one to play around with if you're new to recursion. The Fibonacci sequence is also good. Find a .py example, or, better yet, write your own based on psuedo code.

If you're a recursion expert already, then I don't know what to tell you other than Python seems to have implemented recursion faithfully and there are no gotchas that I can see.

 

[rusi]

So I know what recursion is, but I don't know how is

flatten(i)

evaluated, what value does it returns?

There is a folklore in CS that recursion is hard
[To iterate is human, to recurse divine -- Peter Deutsch]

This is unfortunate and inaccurate as students brought up on functional programming dont seem to find it hard.

What is hard is mixing imperative programming and recursion.

So here are some non-imperative versions of flatten

# At first pull out the recursion-checking predicate
def isrec(x): return isinstance(x, list) or isinstance(x, tuple)

# And we need a cutdown version of flatten -- concat.
# concat flattens exactly one level. More it does not go into, less and it errors out

def concat(l): return [y for x in l for y in x]

# Version 0
def flat0(l):
if not isrec(l): return [l]
else: return concat([flat0(i) for i in l])

# Push the if into the return -- more functional
def flat1(l):
return ([l] if not isrec(l) else concat([flat1(i) for i in l]))

# push the if expression into the comprehension
def flat2(l):
return concat([flat2(i) if isrec(i) else for i in l])


### Lisp-y solution
def hd(l) : return l[0]
def tl(l) : return l[1:]
def null(l): return l==[]

def flat4(l):
return ( [] if null(l) else
[l] if not isrec(l) else
flat4(hd(l)) + flat4(tl(l)))