week 7 Impressions of tracing recursion

Until this week, I have learnt two different types of tracing recursion, the first one is taking a list of list as parameter and the second one is about python Tree.

Taking a list of list is not hard to trace, for example:

let x = [[2,3], 3 , 4, 5], then f(x) will return 5. To trace recursion, there are 4 items in x and the first item itself contains 2 item. The tracing of this recursion is shown below:

>>> sum(f([2,3], f(3), f(4), f(5))

>>> sum(f(2), f(3), 1, 1, 1)

>>> sum(1, 1, 1, 1, 1)

5

This kind of recursion is simple. f(x) will  need to check if x is a list, (in this case x is a list) then it will sum all f(a) where a is every element in x. Further more, this function will continue to check if item in x is a list, finally reach the inner-most list.

This kind of recursion seems easy for me, because I have experienced this kind of logic. However, to trace recursion for python Tree is difficult for me. The structure of Tree is new and I don't know how computer will process the data in what order and logic. There is an example in Lab.

For tracing the BTNode tree, I was so confused how computer will process data from tree structure. I read some others slogs and I got some idea about tracing recursion. 

http://fifislog148.blogspot.ca/

In the function insert, it will insert a data in BTNode in appropriate position. The function will first check if node is empty, if not, it will compare data with node.data, and if data is smaller, then data will be posited on left, otherwise right. Here we need a recursion to get the right position for data. In the recursion, function will take node.left as a central position and check its left and right, until no children is left.