This visualization can visualize the recursion tree of a recursive algorithm.
But you can also visualize the Directed Acyclic Graph (DAG) of a DP algorithm.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
This is the Recursion Tree/DAG visualization area.
Note that due to combinatorial explosion, it will be very hard to visualize Recursion Tree for large instances.
And for Recursion DAG, it will also very hard to minimize the number of edge crossings in the event of overlapping subproblems.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
Select one of the examples, or write your own code.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
The Factorial example computes the factorial of a number N.
It is one of the simplest (tail) recursive function that can actually be rewritten into iterative version.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
The Fibonacci example computes the N-th Fibonacci number.
Unlike Factorial example, this time each recursive step recurses to two other smaller sub-problems. It can still be written in iterative fashion after one understands the concept of Dynamic Programming. Fibonacci recursion tree (and DAG) are frequently used to showcase the basic idea of recursion.
The Catalan example computes the N-th catalan number recursively.
The GCD example computes the Greatest Common Divisor of two numbers A and B recursively.
The N Choose K computes the binomial coefficient C(N, K).
The Range Sum Query example computes the maximum value of S(l,r), where S(l,r) = a1[l] + a1[l+1] + ... + a1[r], where 1≤l≤r≤i.
The Knapsack example solves the 0/1 Knapsack Problem: What is the maximum value that we can get, given a knapsack that can hold a maximum weight of w, where the value of the i-th item is a1[i], the weight of the i-th item is a2[i]?
The Coin Change example solves the Coin Change problem: Given a list of coin values in a1, what is the minimum number of coins needed to get the value v?
The Longest Increasing Subsequence example solves the Longest Increasing Subsequence problem: Given an array a1, how long is the Longest Increasing Subsequnce of the array?
The Traveling Salesman example solves the Traveling Salesman Problem on small graph: How long is the shortest path that goes from city 0, passes through every city once, and goes back again to 0? The distance between city i and city j is denoted by a1[i][j].
The Matching problem computes the maximum number of matching on a small graph, which is given in the adjacency matrix a1.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
var a2 =