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

Groups > comp.lang.python > #54824

Re: Understanding how is a function evaluated using recursion

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web