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.

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.

It is obvious while looking at the call trees that the original function is much less complex and therefore much faster.