Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #54761 > unrolled thread

Understanding how is a function evaluated using recursion

Back to article view | Back to comp.lang.python

Contents

  Understanding how is a function evaluated using recursion Arturo B <a7xrturodev@gmail.com> - 2013-09-25 16:24 -0700
    Re: Understanding how is a function evaluated using recursion Josh English <Joshua.R.English@gmail.com> - 2013-09-25 16:59 -0700
    Re: Understanding how is a function evaluated using recursion MRAB <python@mrabarnett.plus.com> - 2013-09-26 01:07 +0100
    Re: Understanding how is a function evaluated using recursion Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-09-26 00:10 +0000
    Re: Understanding how is a function evaluated using recursion Dave Angel <davea@davea.name> - 2013-09-26 00:26 +0000
    Re: Understanding how is a function evaluated using recursion Terry Reedy <tjreedy@udel.edu> - 2013-09-25 21:12 -0400
    Re: Understanding how is a function evaluated using recursion rusi <rustompmody@gmail.com> - 2013-09-25 21:04 -0700
    Re: Understanding how is a function evaluated using recursion Neil Cerutti <neilc@norwich.edu> - 2013-09-26 14:18 +0000
      Re: Understanding how is a function evaluated using recursion Neil Cerutti <neilc@norwich.edu> - 2013-09-26 14:23 +0000
        Re: Understanding how is a function evaluated using recursion Peter Cacioppi <peter.cacioppi@gmail.com> - 2013-09-28 13:24 -0700
    Re: Understanding how is a function evaluated using recursion rusi <rustompmody@gmail.com> - 2013-09-29 20:41 -0700

#54761 — Understanding how is a function evaluated using recursion

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

[toc] | [next] | [standalone]

#54764

On Wednesday, September 25, 2013 4:24:22 PM UTC-7, Arturo B wrote:
> 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

[toc] | [prev] | [next] | [standalone]

#54765

On 26/09/2013 00:24, 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?
>
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.

[toc] | [prev] | [next] | [standalone]

#54766

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

[toc] | [prev] | [next] | [standalone]

#54769

On 25/9/2013 19:24, 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:

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.


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#54772

On 9/25/2013 7:24 PM, 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?

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.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#54779

On Thursday, September 26, 2013 4:54:22 AM UTC+5:30, Arturo B wrote:
> 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!

[toc] | [prev] | [next] | [standalone]

#54824

On 2013-09-25, Arturo B <a7xrturodev@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

[toc] | [prev] | [next] | [standalone]

#54826

On 2013-09-26, Neil Cerutti <neilc@norwich.edu> wrote:
> 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.

-- 
Neil Cerutti

[toc] | [prev] | [next] | [standalone]

#54977

On Thursday, September 26, 2013 7:23:47 AM UTC-7, Neil Cerutti wrote:
> On 2013-09-26, Neil Cerutti <neilc@norwich.edu> wrote:
> 
> > 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.
> 
> 
> 
> -- 
> 
> Neil Cerutti


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.

[toc] | [prev] | [next] | [standalone]

#55049

On Thursday, September 26, 2013 4:54:22 AM UTC+5:30, Arturo B wrote:
> 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 [i] 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)))

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web