Visualizing Computation/Call Trees

Call trees are visual representations of the functions being called upon in a particular instance. For example, consider the recursive function: def even(i): # return True iff i is an even number return i % 2 == 0 def power(base, exp): if exp == 1: return base elif even(exp): base_to_half_exp = power(base, exp//2) return base_to_half_exp * base_to_half_exp else::Image: return base * power(base, exp-1) print power(2, 7) The power(2, 7) function will call on both the even() function and the power() function multiple times. This diagram shows the progression of the function. 250px Each time a function calls on another function, an arrow points from the function to the function it is calling. Multiple arrows can, of course, originate from the same function. Call trees can be designed utilizing different conventions to emphasize different points of the function. If the values each function is returning are important to the problem, those values can be placed in the call tree with arrows pointing upwards toward the function that will use that value. If the timing is most important and multiple arrows are originating from the same function, the first function called upon should be placed furthest to the left. Additionally, call trees can help to show the complexity of a function. Consider this power function: def even(i): # return True iff i is an even number return i % 2 == 0 def power(base, exp): if exp == 1: return base elif even(exp): return power(base, exp//2) * power(base, exp//2) else: return base * power(base, exp-1) print power(2, 7) This function forms the following call tree. 1000px It is obvious while looking at the call trees that the original function is much less complex and therefore much faster.