Understanding how is a function evaluated using recursion

[Steven D'Aprano]

On Wed, 25 Sep 2013 16:24:22 -0700, Arturo B 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?

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.


-- 
Steven