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.
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
== 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")
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.
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.
- For reversing recursive functions in snippets of assembler