Python recursion visualization with rcviz

rcviz is a small python module for recursive call graph visualisation, which i wrote a few weekends ago. It differs from regular call graph visualisations because i) it shows the recursion tree with each invocation of the function as a different node  ii)  it also shows the args and return values at each node, and iii)  it allows you track and graph the execution of just the function/s you are interested in without affecting or slowing down the rest of the codebase.

It’s probably only useful for visual intuition and debugging of recursive algorithms, not general purpose call graphs. Below, I show the usage and output for a Fibonacci numbers routine, and then a recursive descent parser (parser code due to Dr. Tim Finin from here).  For another example, see the quicksort visualizations on rcviz github readme.

== Usage

1. Use the @viz decorator to instrument the recursive function.

def factorial(n):

2. At the end of the calling program  render the recursion with


== Fibonacci visualization

from rcviz import callgraph, viz

def fibonacci(number):
 if number <= 1:
    return number
    return fibonacci(number-1) + fibonacci(number-2)

print fibonacci(5)


The edges are numbered with the order of invocation and the order of unwinding ( in brackets with the up arrow ). The edge colors fade from black to light gray with the invocation order (black invoked first, light grey last).

== Recursive descent visualization

The code and grammar can be viewed in here. It is a top down recursive descent parser that takes a string such as “1 + (4*5) – 3” and returns a parse tree or error on bad syntax. The parse tree is represented as a nested tuple of the form  ( left_tree, node, right_tree ), for the above example it is (‘+’, 1, (‘-‘, (‘*’, 4, 5), 3)) , rooted at 1. The output is below.





To generate the above image, I added the decorator @viz to all six functions in, and rendered to png. It should be trivial to extend rcviz to programatically decorate all functions in a module.


== Some rcviz examples from the web

  • The Ackermann function (french, scroll down for visual) – Shows Ackermann(3,2) growing to a 541 node graph.




2 thoughts on “Python recursion visualization with rcviz

  1. I was trying this out. works nicely for standalone functions. I wanted to test for a method within a class but was running into errors.
    say, Class A has method b implemented recursively. now, I instantiate the class and call this method b and want to see the recursive visualization for the method.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s