[Tutor] not understanding a recursion example

[Peter Otten]

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