[Chicago] Counting recursive calls.

[Robare, Phillip (Randstant)]

Douglas,
Depth of recursion is the height of the stack of recursive calls.  In a tree traversal it would only be equal to the number of recursive calls only if the tree at every level has only one child.  Depth of recursion is important in a non-tail-recursive language where the local variables from the caller are kept in memory until the callee returns. (See the Wikipedia article on Tail Calls https://en.wikipedia.org/wiki/Tail_call for a more detailed discussion than you are ready for.)  If you go down one branch and return, the memory used by the calls made when you went down the branch is released when you get back.
Your tree class (called Node) mixes up structure and operations.  For instance add(), size(), and height() are good structure operations. The InOrder and preOrder functions are operations done to a particular tree and could be moved into another class with a has-a relationship to the tree structure.  That is, the TraversalTree class would be passed a Tree in its __init__() function.  In modern Python the traversal functions should be written as generators that return a node.  This would result in your addUp function collapsing down to a one liner that just is a function of a particular tree.
def addUp(traversal_tree_instance):
return sum([node.parameter for node in traversal_tree_instance.inOrder()])
This obviously adds up the entire tree instead of doing what your function does, decorating each node of the tree with the sum of its sub-tree.  I will leave it up to you to make the modifications that will visit each node and add the derived value.   Since the value is derived, and not fundamental, you should consider how you might separate this aspect from the elements of a tree that are fundamental.  (Think a bit before reading on…)

A common way to do this is have a Node class that is outside of the Tree class but has operations that the tree uses, such as left(), and right(). The terminal would be a Leaf class instance that would not have a left or right operation but instead have a value() call.  If you want to store some derived property the Node can also have a value().  Think about how you would redo your tree to store strings instead of integers.
Your FormattableInt class is unneeded, and much too Java-like. The ability to format int’s with comma grouping is already in the language.
(https://docs.python.org/2.7/library/string.html#formatspec)
Using the comma as a thousand’s separator:
>>> '{:,}'.format(1234567890)
'1,234,567,890'

Even if that didn’t exist, something more pythonic could be cobbled together with lists, generators and slicing.
>>> def by_3s(int_str):
...     a=int_str
...     while a:
...         yield(a[-3:]) # return the last 3 characters
...         a = a[:-3] # chop off the last 3 and loop again
...
>>> a=1234567890
>>> int_str = str(a)
>>> ','.join(reversed(list(by_3s(int_str))))
'1,234,567,890'

I hope you find this helpful and educational.  You have obviously worked hard on your code and the struggle is where you do your learning.

Phil Robare
probare at rcnchicago.com

From: Chicago [mailto:chicago-bounces+proba=allstate.com at python.org] On Behalf Of Lewit, Douglas
Sent: Saturday, April 11, 2015 3:45 AM
To: The Chicago Python Users Group
Subject: [Chicago] Counting recursive calls.

Hi everyone,

If you've got time could you run my TreeNode_Main.py script.  I think it runs just fine, but I'm wondering about the number of recursive calls to generate the binary tree.  That number seems rather large, especially when you consider that Python's default recursion limit is 1000.  (Although in my code I change the recursion limit to 2000.)  If my number of recursion calls is correct, that means then that there's a difference between "number of recursive calls" and "recursion depth".  But..... what's the difference?  I thought that "recursion depth" really refers to the number of recursive calls.....the number of times that a method is called, or..... the number of times that a method has to call itself?  I'm a little confused!

Thanks for the advice.

Best,

Douglas.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150413/24d2b5fd/attachment.html>