Python recursion visualization with rcviz

rcviz is a small python module for recursive call graph visualization, which i wrote a few weekends ago. It differs from regular call graph visualizations 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.


@viz
def factorial(n):

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

callgraph.render("outfile.png")

== Fibonacci visualization


from rcviz import callgraph, viz

@viz
def fibonacci(number):
    if number <= 1:
        return number
    else:
        return fibonacci(number-1) + fibonacci(number-2)
        
print fibonacci(5)        
callgraph.render("fibonacci.png")

renders
fibonacci

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 rd.py 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.

 

rd

 

 

To generate the above image, I added the decorator @viz to all six functions in rd.py, 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.

 

.

 

Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s