This visualization can visualize the recursion tree of any recursive algorithm or the recursion tree of a Divide and Conquer (D&C) algorithm recurrence (e.g., Master Theorem) that we can legally write in JavaScript.
We can also visualize the Directed Acyclic Graph (DAG) of a Dynamic Programming (DP) algorithm and compare the dramatic search-space difference of a DP problem versus when its overlapping sub-problems are naively recomputed, e.g., the exponential Ω(2n/2) recursive Fibonacci versus its O(n) DP version.
On some problems, we can also visualize the difference between what a Complete Search (recursive backtracking) that explores the entire search space, a greedy algorithm (that greedily picks one branch each time), versus Dynamic Programming look like in the same recursion tree, e.g., Coin-Change of v = 7 cents with 4 coins {4, 3, 1, 5} cents.
Most recursion trees require large drawing space, therefore view this visualization page on a large screen. For obvious reason, we cannot really visualize very big trees/DAGs. Therefore, we call our recursion with small parameter(s).
This is the Recursion Tree and Recursion Directed Acyclic Graph (DAG) visualization area. The Recursion Tree/DAG are drawn/animated as per how a real computer program that implements this recursion works, i.e., "depth-first".
The recursion starts from the initial state that is colored dark brown. The current parameter value is shown inside each vertex (comma-separated for recursion with two or more parameters). Active vertices will be colored orange. Vertices that are no longer calling any other recursive problem (the base cases) will be colored green. Vertices (subproblems) that are repeated will be colored lightblue for the second occurrence onwards. The return value of each recursive call is written as a red text below the vertex. This visualization is generic for any recursion that you can legally write in JavaScript.
Note that due to combinatorial explosion, it will be very hard to visualize the Recursion Tree for large instances.
For the Recursion DAG, it will also very hard to minimize the number of edge crossings in the event of overlapping subproblems. However, we try our best to give a custom DAG drawing layout for certain DP problems to improve the presentation.
For example, we currently show the recursion DAG of the computation of the n-th Fibonacci number. We layout the vertices from leftmost (the two green-colored base cases n = 0 and n = 1) to rightmost (the initial n). Ideally this is shown as a flat 1-D (memoization) array. However as VisuAlgo does not have curvy edge yet, we decided to put odd-numbered vertices slightly below the even-numbered vertices to get around the overlapping edges issue. To compute fib(n), we only need to know the result of two immediate results: fib(n-1) + fib(n-2) that is depicted as the two arrows from vertex n to vertices n-1 and n-2. The results of the summation, i.e., the values of each fib(n), are displayed as red text below the vertices. As there is no repeated subproblem computation, there is no lightblue vertex at all in this recursion DAG (such vertices/states will have more than one incoming arrows instead).
Select one of the example recursive algorithms in the drop-down list or write our own recursive code — in JavaScript. The final recursion Tree / DAG is immediately displayed. Note that this visualization can run any JavaScript code, including malicious code, so please be careful (it will only affect your own web browser, don't worry).
Click the 'Run' button at the top right corner of the action box to start the step-by-step visualization of the recursive function after you have selected (or written) a valid JavaScript code!
In the next sub-sections, we start with example recursive algorithms with just one sub-problem, i.e., not branching. For these one-subproblem examples, their recursion trees and recursion DAGs are 100% identical (they looked like Singly Linked Lists from the root (initial call) to the leaf (base case)). As there is no overlapping subproblem for the examples in this category, you will not see any lightblue-colored vertex and only one green-colored vertex (the base case). The default orientation for recursion Tree is top-right-to-bottom-left whereas the default orientation for recursion DAG is right-to-left.
The Factorial Numbers example computes the factorial of an integer n.
It is one of the simplest (tail) recursive function that can be easily rewritten into an iterative version. It's time complexity is also simply Θ(n).
The value of Factorial f(n) grows very fast, thus try only the small integers n ∈ [0..10]
(we randomize the value of the initial n between this range).
The Binary Search example finds the index of a2 in a sorted array a1[a..b]. We start binary search from the initial search space of a=0,b=a1.length-1 (the entire array a1, with n = (a1.length-1) - 0 + 1 = a1.length).
Only one of the two possible branches will be executed each time, resulting in a recursion tree = recursion DAG situation. The time complexity if Θ(log n) as we keep halving the search space each time. The worst-case happens when a2 is not found in sorted array a1.
In this visualization, we randomize the content of sorted array a1 and the value to be searched a2.
TBC: In the near future, we will draw the entire Θ(n) search space (both left and right branches at each vertex) and highlight the efficient Θ(log n) path taken by Binary Search on this search space. This is like seeing the animation of Search(v) function of a (balanced) Binary Search Tree.
The Modulo Power example computes the a1^p % a2 in efficient way.
This Divide & Conquer (D&C) algorithm runs in Θ(log p).
In this visualization, we randomize the values of a1 (the base, a small value ∈ [2..4]),
a2 (the modulo, a prime ∈ [7, 97, 997, 9973]), and power p (we want to raise a1 to its p-th power, modulo a2. Due to its low time complexity, it is OK to try very large 0 ≤ p ≤ 256.
TBC: In the near future, we may draw the comparison between this efficient D&C modulo power algorithm with the naive version that multiply a1 p times that runs in Θ(p).
The Greatest Common Divisor (GCD) example computes the GCD of two integers a and b.
This is the classic Euclid's algorithm that runs in O(log n) where n = min(a, b) — depending of the details, n = max(a, b) or n = a+b are also possible.
Euclid's algorithm is an example of Divide & Conquer (D&C) algorithm.
Due to its low time complexity, it should be OK to try 0 ≤ a, b ≤ 99.
(we randomize the values of a and b between this range and set a ≥ b).
Note that if we put a < b, technically the first recursive step will swap a and b.
Do explore various possible combinations of a and b and notice on what values f(a, b) terminates very quickly in 1 step (b = 0), 2 steps (b = gcd(a, b)), or the maximum number of steps (try this sequence) — to show the lowerbound Ω(log n).
The Max Range Sum example computes the value of the subarray with the maximum total sum inside the given (global) array a1 with n = a1.length integers (the first textbox below the code editor textbox). The value of a1 can be positive integers, zeroes, or negative integers (without negative integer, the answer will obviously the sum of the entire integers in a1).
Formally, let's define RSQ(i, j) = a1[i] + a1[i+1] + ... + a1[j], where 0 ≤ i ≤ j ≤ n-1 (RSQ stands for Range Sum Query). Max Range Sum problem seeks to find the optimal i and j such that RSQ(i, j) is the maximum.
We call f(n-1). The largest value of f(i) is the answer.
This is the classic Kadane's algorithm that runs in O(n).
The Catalan example computes the n-th Catalan number recursively.
This explanation is a stub that will be expanded later.
In the next sub-sections, we will see example recursive algorithms that have exactly two sub-problems, i.e., branching. The sizes of the subproblems can be identical or vary. For these two sub-problems examples, their recursion trees will usually be much bigger that their recursion DAGs (especially if there are (many) overlapping sub-problems, indicated with the lightblue vertices on the recursion tree drawing).
Currently shown on screen is the recursion tree of a Fibonacci recurrence.
The Fibonacci Numbers example computes the n-th Fibonacci number.
Unlike Factorial example, this time each recursive step recurses to two other smaller sub-problems (if we call f(n-1) first before f(n-2), then the left side of the recursion tree will be taller than the right side — try swapping the two sub-problems).
The value of Fibonacci f(n) grows very fast and its recursion tree — if implemented verbatim as defined above — also grows exponentially, i.e., at least Ω(2n/2), thus try only the small initial values of n ≤ 7 (to avoid crashing your web browser).
Fibonacci recursion tree is frequently used to showcase the basic idea of recursion, its inefficiency (due to the many overlapping subproblems), and the linkage to Dynamic Programming (DP) topic.
The recursion DAG (shown in the background) of Fibonacci computation only contains O(n) vertices and thus can go to a larger n ≤ 30 (so it still looks nice in this visualization; in practice n can go to millions with this DP solution).
Most of the time, the Fibonacci computation is written in iterative fashion after one understands the concept of DP.
It is probably rare to think this way, but this visualization shows that the computation of Fibonacci f(n) is basically counting the number of paths from n to vertex 1.
The C(n, k) example computes the binomial coefficient C(n, k).
The recursion tree of C(n, k) grows very fast, with the largest tree when k = n/2, smaller trees when k is close to 0 or n (a few path(s) with short leafs), and smallest trees when k is 0 or n (only one vertex).
The recursion DAG of C(n, k) is basically an inverted Pascal's Triangle. It only contains O((n/2)*(n/2)) = O(n^2/4) vertices at most (when k = n/2) although in practice we probably just use a DP/memo table of size O(n^2). Thus we can go to a larger n ≤ 15 (so it still looks nice in this visualization) and k∈[0..n], including when k≈n/2.
TBC: In the near future, we may draw a dummy vertex (0, 0) --- C(n, k) will not actually reach it unless started from C(0, 0) with return value of 1 to complete the inverted Pascal's Triangle visualization.
The 0-1 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]?
0-1 Knapsack has a classic DP recurrence f(i, w) which we call using f(n-1, max-w) where n = a1.length.
The recursion tree of this DP recurrence has a few (like currently shown on screen) to many (e.g., try all items having the same weight, i.e., ones) overlapping sub-problems.
The recursion DAG of 0-1 Knapsack only contains O(n * max-w) vertices. Thus we can go to a larger n ≤ 7 and max-w ≤ 15 (so it still looks nice in this visualization).
This DP recurrence basically tries to find the longest (weighted) path in this implicit DAG and has time complexity of O(n * max-w).
If the weights of each item in a2 vary a lot, the recursion DAG will look sparse. Try setting a2=[1,2,...,2^i] for a denser recursion DAG> (but no overlap) or a2=[1,1,...,1] (lots of overlap).
In the next sub-sections, we will see example recursive algorithms that have many sub-problems (1, 2, 3, ..., a certain limit). For many of these examples, the sizes of their Recursion Trees are exponential and we will really need to use Dynamic Programming to compute its Recursion DAGs instead.
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 recursion DAG of the default example (not randomized) is as follows: Vertex j ∈ [0..i-1] is laid out horizontally (along the x-axis from left/vertex 0 to right/vertex i-1), then placed vertically (along the y-axis according to the value of a1[j]). We draw an edge between two indices j and k if a1[j] < a1[k] (with all vertices having hidden edge to the dummy max(a1)+1 value at the top-right cell so that all LIS ends at this dummy vertex and we can start the recursion with f(i) where i = a1.length-1). Then this LIS problem can be visualized as finding the longest path in this (implicit) recursion DAG.
As there are |V| = n vertices and |E| = O(n^2) edges (use sorted ascending test case, e.g., {1,2,4,8,16,...} to have nice visualization), the overall time complexity to solve LIS using DP is O(n^2). Since early 2000s, we should use the faster O(n log k) greedy+binary search solution for LIS (not explained in this slide).
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 recursion tree of the default example (not randomized) has v = 7 cents and 4 coins that are specifically selected to be {4, 3, 1, 5}. What is shown on-screen is the entire recursion tree of Coin-Change recursive function.
A typical greedy algorithm for Coin-Change that always take the largest coin value that does not exceed current value v will be trapped into taking the rightmost branch: 7 cents (take 5 cents coin) → 2 cents (take 1 cent coin) → 1 cent (take another 1 cent coin) → 0 (total 3 coins).
DP algorithm that explores this recursion tree (but avoiding repeated computations on the lightblue vertices will find the lefmost branch: 7 cents (take 4 cents coin) → 3 cents (take 3 cents coin) → 0 (total 2 coins). Alternative solution: 7 → 4 → 0 (also 2 coins).
The Cutting Rod example solves the 'fictional' introductory problem in Chapter 14.1 - Dynamic Programming of the "Introductions to Algorithms" (CLRS 4th edition) textbook: Given a rod of length n inches and a table of prices a1 for length 1,2,...,n inches, determine the maximum revenue obtainable by cutting up the rod and selling the pieces.
The recursion tree of the default example (not randomized) has n = 4 inches. What is shown on-screen is the entire recursion tree of Cut-Rod recursive function.
The Matrix Chain Mult(iplication) example solves the second DP introductory problem in Chapter 14.2 of the "Introductions to Algorithms" (CLRS 4th edition) textbook: Given a sequence (chain)
The recursion tree of the default example (not randomized) has i=1,j=4. What is shown on-screen is the entire recursion tree of MCM recursive function.
The Longest Common Subsequence (LCS) example solves the Longest Common Subsequence problem: Given two strings (character arrays) a1 (of length n = a1.length) and a2 (of length m = a2.length), how long is the Longest Common Subsequence between the two strings?
We call f(n-1, m-1), from the last character of both strings.
The recursion tree of this DP recurrence has an exponential (like currently shown on screen) number of overlapping sub-problems if both strings have many different characters (but do try a1 == a2; we will see a single-branch recursion tree).
The recursion DAG of LCS only contains O(n * m) vertices. Thus we can use longer strings with n ≤ 10 and m ≤ 10 (so it still looks nice in this visualization).
This DP recurrence basically tries to find the longest (0/1-weighted) path in this implicit DAG and has time complexity of O(n * m).
The Graph Matching problem computes the maximum number of matching on a small graph, which is given in the adjacency matrix a1.
This slide is a stub and will be expanded in the future.
The Traveling Salesperson example solves the Traveling Salesperson 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].
This slide is a stub and will be expanded in the future.
In the next sub-sections, instead of visualizing the recursion tree of a recursive algorithm, we visualize the recursion tree of the recurrence (equation) to help analyze the time complexity of certain Divide and Conquer (D&C) algorithms.
The value computed by f(n) (the red label underneath each vertex that signifies the return value of that recursive function/that subproblem) is thus the total number of operations taken by that recursive algorithm when its problem size is n (the value drawn inside each vertex). Most textbooks will say the function name of this recurrence as T(n), but we choose not to change our default f(n) function name that is used in all other recursive algorithm visualizations. Some other textbooks (e.g., CLRS) also put the cost of each vertex only, not the cost of the entire subproblem.
In Sorting visualization, we learn about merge sort. It's time complexity recurrences are:
Please check the recursion tree of the default example (n = 16). We will use the same recursion tree for the next few sub-slides. You should see the initial problem size of n = 16 written inside the root vertex and its return value (total amount of work done by f(16) is 32+32+1*16 = 80). This value of f(n) is consistent throughout the recursion tree, e.g., f(8) = f(4)+f(4)+1*4 = 12+12+1*8 = 32.
我们看到这个递归树的高度是 log2 n 因为我们一直将 n 除以 2 直到我们达到大小为 1 的基本情况。
对于 n = 16，我们有16->8->4->2->1 (log2 16 = 4 步)。
PS: 树的高度 = 从根到最深叶子的边的数量。
As the effort done in the recursive step per subproblem of size n is c*n (the divide (trivial, Θ(1)) and the conquer (merge) operation, the Θ(n)), we will perform exactly c*n operations per each recursion level of this specific recursion tree.
The root of size (n) does c*n operations during the merge step.
The two children of the root of size (n/2) both do c*n/2, and 2*c*n/2 = c*n too.
The grandchildren level is 4*c*n/4 = c*n too.
And so on until the last level (the leaves).
As the red label underneath each vertex in this visualization reports the value of the entire subproblem (including the subtrees below), these identical costs per level are not easily seen, e.g., from root to leaf, we see 80, 2x32 = 64, 4x12 = 48, 8x4 = 32, 16x1 = 16 and may get different conclusion... However, if we discounted the values of its subproblems, we will get the same conclusion, e.g., for the root, we do 80-2x32 = 16 operations, for the children of the root, we do 2x(32-2x12) = 2x8 = 16 operations too, etc.
Soon, we will show 'work-done-in-each-level' info in the visualization directly.
绿色叶子的数量是 2log2 n = nlog2 2 = n。
这些叶子每个都做 Θ(1) 步，因此最后一层（叶子层）的总工作量也是 Θ(n)。
因此，归并排序所做的总工作量是每层 c*n，乘以递归树的高度（log2 n + 1 更多的叶子），或 Θ(n log n)。
对于这个例子，f(16) = 80 来自 1x16 x (log2 16 + 1) = 16 x (4 + 1) = 16 x 5 = 80。
In Sorting visualization, we also learn about the non-random(ized) quick sort.
It may have a worst case behavior of O(n2) on certain kind of (trivial) instances of (nearly-) sorted input and it may have the following time complexity recurrence (with a = 1):
Note that writing the recurrence in the other direction does not matter much asymptotically, other than the recursion tree will be mirrored.
Please observe the currently drawn recursion tree.
We want to show that this recursion tree has f(n) = O(n2).
We see that
the height of
this recursion tree
is rather tall, i.e., n/a - 1
as we only reduces n
by a per level.
Thus, we need n/a - 1 steps
to reach the base case
(n = 1).
For n = 16, a = 1, we have
16->
15->
14->
...->
2->
1 (16/1 - 1 = 15 steps).
在每个大小为 n 的子问题的递归步骤中，我们所做的工作量是 c*n（在 Θ(n) 中划分（分区）操作；征服步骤是微不足道的 — Θ(1)），我们将在每个递归级别执行精确的 c*n 操作。
根的大小 (n) 在分区步骤中进行 c*n 操作。
根的子节点的大小 (n-a) 执行 c*(n-1)，另一个执行 f(a)。
孙子级别执行 c*(n-2)，另一个执行 f(a)。
等等，直到最后一级（叶子都执行 f(a)）。
快速排序在这种最坏情况的输入上所做的总工作是等差级数1+2+...+n的总和，再加上一些其他常数因子操作（所有的f(a)都是Θ(1)）。这简化为f(n) = Θ(n2)。
For recurrences of the form:
f(n) = a*f(n/b) + g(n)where a ≥ 1, b > 1, and g(n) is asymptotically positive,
we maybe able to apply the master theorem (also called as master method).
PS: In this visualization, we have to rename CLRS function names to our convention:
f(n) → g(n) and T(n) → f(n).
We compare the driving function g(n) (the amount of divide and conquer work in each recursive step of size n) with nlogba (the watershed function — also the asymptotic number of leaves of the recursion tree), if g(n) = O(nlogba-ε) for ε > 0, it means that the driving function g(n) grows polynomially slower than the watershed function nlogba (by a factor of nε), thus the watershed function nlogba will dominate and the solution of the recurrence is f(n) = θ(nlogba).
Visually, if you see the recursion tree for recurrence that falls into case 1 category, the cost per level grows exponentially from root level to the leaves (in this picture, 1*4*4 = 16, 7*2*2 = 28, 49*1*1 = 49, ..., 16+28+49 = 93), and the total cost of the leaves dominates the total cost of all internal vertices.
The most popular example is Strassen's algorithm for matrix multiplication where case 1 of master theorem is applicable. The recurrence is: f(n) = 7*f(n/2) + c*n*n.
n2 = O(n2.807-ε) for ε = 0.807... — case 1 — Thus f(n) = Θ(n2.807)
Exercise: You can try changing the demo code by setting a = 8 and set g(n) = c*1 to change the recurrence of Strassen's algorithm to the recurrence of the simple recursive matrix multiplication algorithm that has f(n) = Θ(n3).
The detailed analysis of the Merge sort algorithm from a few slides earlier can be simplified using master theorem, e.g., f(n) = 2*f(n/2) + c*n.
Thus a = 2, b = 2, watershed = nlog2 2 = n, driving = g(n) = Θ(n).
n = Θ(n logk n) for k = 0
The watershed and driving functions have the same asymptotic growth — case 2
Thus f(n) = Θ(n log n).
Visually, if you see the recursion tree for recurrence that falls into case 2 category, the cost per level is ~the same, i.e., Θ(nlogba logk n) and there are logb n levels. We claim that the solution is f(n) = Θ(nlogba logk+1 n). That's it, the solution of the recurrence that falls under case 2 is to add an extra log factor to g(n).
Exercise: You can try changing the demo code by setting a = 1 and set g(n) = c*1 to change the recurrence of Merge sort algorithm to the recurrence of the binary search algorithm. For binary search version, f(n) = Θ(log n). Notice that for most of real-life case 2 algorithm recurrences (e.g., Merge Sort and Binary Search), k = 0.
Case 3 is the opposite of Case 1, where the driving function g(n) grows polynomially faster than the watershed function nlogba. Thus the bulk of the operations is done by the driving function at the root level (but check the regularity condition too, to be elaborated below). This case 3 is actually rarely appear in real algorithms so we use an example fictional recurrence: f(n) = 4*f(n/2) + c*n^3.
Thus a = 4, b = 2, watershed = nlog2 4 = n2, driving = g(n) = Θ(n3).
n^3 = Ω(n2+ε) for ε = 1 and
4*(n/2)3 ≤ c*n3 (regularity condition) for c = 1/2 — case 3
Thus f(n) = Θ(n3).
Visually, if you see the recursion tree for recurrence that falls into case 3 category, the cost per level drops exponentially from root level to the leaves (in this picture, 1*4*4*4 = 64, 4*2*2*2 = 32, 16*1*1*1 = 16, ..., 64+32+16 = 112), and the total cost of the root dominates the total cost of all other internal vertices (including the (many) leaves).