A Simple Recursion Tree 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.

def fib(n):
  # base condition mimicking the first two numbers
  # in the sequence
  if n == 0: return 0
  if n == 1: return 1

  # every number is summation of the previous two
  return fib(n - 1) + fib(n - 2)

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

https://user-images.githubusercontent.com/4745789/102004754-74fb7980-3d39-11eb-991e-0f54fa7f20c6.png

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.

def recviz(fn):
    """Decorator that pretty prints the recursion tree with
       args, kwargs, and return values.
    """

    # holds the current recursion level
    recursion_level = 1

    def wrapper(*args, **kwargs):

        # we register a nonlocal recursion_level so that
        # it binds with the recursion_level variable.
        # in this case, it will bind to the one defined
        # in recviz function.
        nonlocal recursion_level

        # Generate the pretty printed function string
        fn_str = pretty_func(fn, args, kwargs)

        # Generate the whitespaces as per the recursion level
        whitespace = "   " * (recursion_level - 1)

        # Pretty print the function with the whitespace
        print(f"{whitespace} -> {fn_str}")

        # increment the recursion level
        recursion_level += 1

        # Invoke the wrapped function and hold the return value
        return_value = fn(*args, **kwargs)

        # Post function evaluation we decrease the recursion
        # level by 1
        recursion_level -= 1

        # Pretty print the return value
        print(f"{whitespace} <- {repr(return_value)}")

        # Return the return value of the wrapped function
        return return_value

    return wrapper

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.

 -> fib(3)
    -> fib(2)
       -> fib(1)
       <- 1
       -> fib(0)
       <- 1
    <- 2
    -> fib(1)
    <- 1
 <- 3

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.

from recviz import recviz

@recviz
def fib(n):
  # base condition mimicking the first two numbers
  # in the sequence
  if n == 0: return 0
  if n == 1: return 1

  # every number is summation of the previous two
  return fib(n - 1) + fib(n - 2)

fib(3)

References


Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 21000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.




Other essays that you might like


Constant Folding in Python

3917 reads 2021-01-10

Every programming language aims to be performant and Python is no exception. In this essay, we dive deep into Python int...

Making Python Integers Iterable

1790 reads 2020-06-14

In Python, Integers are not iterables but we can make them iterable by implementing __iter__ function. In this essay, we...

Building Finite State Machines with Python Coroutines

7625 reads 2020-04-19

The most intuitive way of building and implementing Finite State Machines is by using Python Coroutines and in this arti...

Inverse Document Frequency

417 reads 2020-03-06

TF-IDF is extensively used in search engines and in various document classification and clustering techniques. Instead o...


Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.


Paid Courses

System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

1000+ learners

Details →

Redis Internals

Learn internals of Redis by re-implementing some of the core features in Golang.

28+ learners

Details →

Free Courses

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.





  • v13.8.5
  • © Arpit Bhayani, 2022

Powered by this tech stack.