[Tutor] not understanding a recursion example

[Bill Allen]

Peter,

Thank you very much for the explanation.   I understand this much better
now.   You are correct, the implementation you show is easier for me to
understand.



--Bill









On Fri, Jan 21, 2011 at 03:43, Peter Otten <__peter__ at web.de> wrote:

> Bill Allen wrote:
>
> > I am not understanding the following code (I did not write it).  It
> > demonstrates walking a tree-like data structure using recursion.  It does
> > run and produces reasonable output.  I particularly do not understand the
> > "traverse.level" statements.  Can anyone give me an idea how this is
> > working
> > and the principles?  I would like understand recursive calls in Python
> > better as I have not used the technique previously.
>
> > def traverse(data):
> >     print(' ' * traverse.level + data['text'])
> >     for kid in data['kids']:
> >         traverse.level += 1
> >         traverse(kid)
> >         traverse.level -= 1
> >
> > if __name__ == '__main__':
> >     traverse.level = 1
> >     traverse(data)
>
>
> Functions are objects in python; you can tuck arbitrary attributes onto
> them, and the above uses a function attribute instead of a global variable.
> A more standard way to write the above would be
>
> def traverse(data):
>    global level
>    print(' ' * level + data['text'])
>     for kid in data['kids']:
>         level += 1
>        traverse(kid)
>         level -= 1
>
> if __name__ == '__main__':
>     level = 1
>    traverse(data)
>
> What it does:
> * call traverse with the outermost dictionary
> * print the data["text"] value indented by the current global level.
> * iterate over the data["kids"] list of dictionaries
> * for each entry in that list
>    - increment indentation level
>    - invoke traverse which will print the data["text"] value.
>      (Remember that traverse was called with the current value of kid, so
>       in terms of the outer traverse() the inner traverse() is printing
>       kid["text"]) Process the kid's kids in the same way.
>    - decrement the indentation level
>
> However using global variables is generally a bad practice.
> It is easy to leave them in an inconsistent state, and if you are using
> multiple threads (i. e. invoke traverse() a second time while the first
> call
> hasn't finished) you'll end up with a big mess.
>
> I would therefore write the traverse function as
>
> def traverse(data, level):
>    print(' ' * level + data['text'])
>     for kid in data['kids']:
>         traverse(kid, level+1)
>
> if __name__ == "__main__":
>    traverse(data, 1)
>
> which I think may also be easier to understand.
>
> Peter
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20110121/69022531/attachment.html>