A simple recursion visualizer for python
One programming paradigm, that is hardest to visualize, as almost every single programmer out there will agree on, is Recursion. We usually use pen and paper to visualize the flow and check how recursion is behaving. But what if, this could be done programmatically, and today we address this very problem and try to come up with a simple yet effective solution.
This essay is going to be a little different from the usuals; instead of taking a look into a research paper or an algorithm, we will implement a simple and easy recursion visualizer for Python.
Recursion Tree
Recursion helps in solving a larger problem by breaking it into smaller similar ones. The classic implementation of recursion in the world of programming is when a function invokes itself using reduced parameters while having a base terminating condition.
The most common problem that is solved using recursion is computing the nth Fibonacci Number. A trivial recursive Python function that spits out nth Fibonacci Number is as shown below
The most effective way of visualizing recursion is by drawing a recursion tree. It is very useful for visualizing what happens when a recurrence is iterated. The recursion tree for the above function fib for input n = 3 is as illustrated below
Decorating to visualize
Instead of printing an actual tree-like recursion tree, we take some liberty and print a close-enough version of it running top-down. To keep track of recursive function calls we use Python Decorators that essentially wraps the function allowing us to invoke statements before and after the function call.
The decorator that wraps the recursive function and prints the recursion tree is as illustrated below.
We use recursion_level to keep track of the current recursion level using which we decide the indentation. The value of this variable is increased every time we are about the invoke the function while it is reduced post the execution. In order to pretty-print the invoked function, we have a helper method called pretty_func whose implementation can be found here.
When we decorate our previously defined fib function and invoke it with n = 3 we get the following output.
The above output renders how recurrence is evaluated and is pretty printed to make it more human-readable. The right arrow -> defines a function invocation while the left arrow <- indicates the return value post invocation.
Publishing it on PyPI
Everything mentioned above is published in a Python Package and hosted on PyPI at pypi/recviz. So in order to use this, simply install the package recviz like a usual Python package using pip and decorate the recursive function.
References
Other essays you might like
If you liked what you read, consider subscribing to my weekly newsletter at arpitbhayani.me/newsletter where, once a week, I write an essay about programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.
You can always find me browsing through Twitter @arpit_bhayani.
If my work adds value, consider supporting me
