recursion-visualizer

Stop drawing recursion trees by hand. RecursionVisualizer creates beautiful, interactive visualizations with a single line of code.

Visualize computing the n-th fibonacci number like this:

@RecursionVisualizer()
def fibonacci(n):
  if n <= 2: 
    return 1
  return fibonacci(n-1) + fibonacci(n-2)

fibonacci(5)

(None, 5)

Install

pip install recursion_visualizer

conda install -c conda-forge recursion_visualizer

How to Use

Simply add the RecursionVisualizer decorator to your recursive function and get a beautiful, interactive animation!

Toggle the DP button to visualize which function calls are evaluated with and without dynamic programming (DP).

Examples

Fibonacci

Visualize computing the n-th fibonacci number like this:

@RecursionVisualizer()
def fibonacci(n):
  if n <= 2: 
    return 1
  return fibonacci(n-1) + fibonacci(n-2)

fibonacci(5)

    <script type="text/javascript">
    window.PlotlyConfig = {MathJaxConfig: 'local'};
    if (window.MathJax && window.MathJax.Hub && window.MathJax.Hub.Config) {window.MathJax.Hub.Config({SVG: {font: "STIX-Web"}});}
    if (typeof require !== 'undefined') {
    require.undef("plotly");
    requirejs.config({
        paths: {
            'plotly': ['https://cdn.plot.ly/plotly-2.14.0.min']
        }
    });
    require(['plotly'], function(Plotly) {
        window._Plotly = Plotly;
    });
    }
    </script>

(None, 5)

There are several things to note:

Each node represents a single call to fibonacci
If fibonacci(i) calls fibonacci(i-1) and fibonacci(i-2), then the node i will have children i-1 and i-2
The tree is rooted at 5 because we initially called the function fibonacci(5)
1 and 2 are the the leaves of this tree because the base cases of fibonacci is when i=1 or i=2
The animation illustrates the order in which the computer evaluates all of the fibonacci calls
Toggle the DP button to see how using dynamic programming (DP) changes which function calls are evaluated

0-1 Knapsack

Visualzie the 0-1 knapsack problem like this:

@RecursionVisualizer(display_args=[0])
def knapsack(capacity, weights, values, i, edge_label=''):

  # create edge labels
  label_1 = 'skip W={}, V={}'.format(weights[i-1], values[i-1])
  label_2 = 'skip W={}, V={}'.format(weights[i-1], values[i-1])
  label_3 = 'take W={}, V={}'.format(weights[i-1], values[i-1])

  # base case
  if i == 0 or capacity == 0:
    return 0

  # if the weight of the current item is more than the capacity
  if weights[i-1] > capacity:
    return knapsack(capacity, weights, values, i-1, edge_label=label_1)

  # return the maximum of two cases: including the ith-item or not including it
  return max(knapsack(capacity, weights, values, i-1, edge_label=label_2),
             values[i-1] + knapsack(capacity-weights[i-1], weights, values, i-1, edge_label=label_3))

weights = [10, 20]
values = [60, 100]
capacity = 50

knapsack(capacity, weights, values, len(weights))

(None, 160)

There are several things to note:

Each node represents a single call to the knapsack function
The display_args=[0] parameter in @RecursionVisualizer means that even though knapsack takes in four arguments, we will only display the 0th argument in each node
Each node displays the the capacity, how much more weight you can add to your knapsack (this is the 0th argument to knapsack)
This tree has a branching factor of two because every level represents either taking or not taking the ith item

Edit Distance

Visualize computing the edit distance like this:

@RecursionVisualizer(display_args=[0, 1])
def edit_distance(m, n, str1, str2, edge_label=''):

    # edge labels
    replace_label = 's1={}, s2={}'.format(str1[:m], str2[:n])
    insert_label = 's1={}, s2={}'.format(str1[:m+1], str2[:n])
    remove_label = 's1={}, s2={}'.format(str1[:m], str2[:n+1])

    # base case
    if m == 0 or n == 0: 
        return max(n, m)

    # if the last characters are the same: compute distance for the remaining strings
    if str1[m-1] == str2[n-1]:
        return edit_distance(m-1, n-1, str1, str2, edge_label=replace_label)

    # if last characters are not the same: insert, remove, and replace the last character, and return the minimum
    return 1 + min(edit_distance(m, n-1, str1, str2, edge_label=insert_label),    # insert
                edit_distance(m-1, n, str1, str2, edge_label=remove_label),       # remove
                edit_distance(m-1, n-1, str1, str2, edge_label=replace_label)     # replace
                )

str1, str2 = "it", "hi"
edit_distance(len(str1), len(str2), str1, str2)

(None, 2)

Mergesort

Visualize the mergesort algorithm like this:

def mergesort_wrapper(nums):

  def merge(lo, mid, hi):
    "helper function for mergesort"
    L, R = nums[lo:mid+1] + [float('inf')], nums[mid+1:hi+1] + [float('inf')]
    i, j = 0, 0
    for k in range(lo, hi+1):
      if L[i] <= R[j]:
        nums[k] = L[i]
        i += 1
      else:
        nums[k] = R[j]
        j += 1

  @RecursionVisualizer()
  def mergesort(lo, hi, edge_label=''):

    if lo < hi:
      mid = lo + (hi-lo) // 2
      mergesort(lo, mid, edge_label='nums={}'.format(nums[lo:mid+1]))
      mergesort(mid+1, hi, edge_label='nums={}'.format(nums[mid+1:hi+1]))
      merge(lo, mid, hi)
      return nums[lo:hi+1]

  mergesort(0, len(nums)-1)  
  return nums

nums = [3, 1, 9, 4]
mergesort_wrapper(nums)

[1, 3, 4, 9]

Features

For all animations:

Each node represents a single recursive function call
The animation illustrates the order in which the computer evaluates each of these function calls
Toggle the DP button to see how using dynamic programming (DP) changes which function calls are evaluated

Extra features:

Hovering the cursor over a node displays additional information
The nodes have different colors:
- A node is unvisited if it is white
- We are visiting a node if it is medium blue
- A node is visited if it is dark blue
At any given time, the path of medium blue nodes illustrates the current functions in the call stack, ie the functions that are currently being executed
The leaf nodes represent the base case

Limitations

RecursionVisualizer is intended for educational purposes only. It is not intended for real world applications or commerical use.

To create an animation of a recursive function, RecursionVisualizer must run the brute force version of the recursive function with no dynamic programming. This means that RecursionVisualizer will often have an exponential runtime. For this reason, we recommend using RecursionVisualizer on inputs no larger than n=10. (n may be the length of a string/list or the number of vertices/edges in a graph.)

Contributions

All contributions are welcome. Simply create a pull request to begin contributing.

Note: RecursionVisualizer is made with nbdev, a tool to create software with notebooks. For more information on nbdev go to their homepage.

License

MIT

ez2rok / recursion-visualizer

readme