Recursion tree visualiser

Paste a small recursive JavaScript function and see every call it makes as a tree, with exact call counts and the arguments that repeat. Or enter a divide-and-conquer recurrence and get its recursion tree, the work per level and the master-theorem bound.

Interactive: Call-tree drawer for JavaScript functions and recurrencesUpdated 31 October 2026

Recursion tree from a functionWrite one named recursive function. It runs in a sandboxed worker in your browser, stopped after 2 seconds or 5,000 calls.

Running
Waiting on a call
Returned
Cache hit

Totals

0Calls

0Max depth

0Distinct

Result: —

Call stack (top is running)

Most repeated calls

1 / 1

Recursion tree from a recurrence

Levels are shown for n = b⁶ with T(1) = 1. The ratio column settles towards a constant when the bound is right.

Tracing a function

Write one named function with the function keyword, then say what to call it with. The examples cover the common shapes: linear recursion (factorial, gcd), branching recursion (Fibonacci, binomial coefficients, Towers of Hanoi) and divide and conquer (fast power, merge-sort splitting). The tool opens on the finished tree; use the controls to rewind and replay the calls in order.

Calls is the total number of times the function was entered, the size of the tree.
Max depth is the deepest the call stack went, the height of the tree. It tells you how much stack memory the recursion needs.
Distinct is the number of different argument lists. When it is much smaller than the call count, the function repeats work, and memoisation will help.

Tick Memoise to cache each result by its arguments. Repeated calls then return immediately and show up as dashed purple leaves. For fib(5) the call count drops from 15 to 9; for fib(25) it drops from 242,785 to 49, and the naive tree is too large to draw.

Safety and limits Your code runs in a separate Web Worker in this browser tab. It is stopped after 2 seconds or 5,000 calls, so an infinite loop or a missing base case cannot freeze the page. Trees with more than 400 calls are counted but not drawn. Nothing is sent to a server.

Solving a recurrence

The second tab handles recurrences of the form

T(n) = a\,T(n/b) + f(n), \qquad T(1) = 1,

which describe algorithms that split a problem of size $n$ into $a$ subproblems of size $n/b$ and spend $f(n)$ splitting and combining. Level $i$ of the recursion tree has $a^i$ nodes of size $n/b^i$ , and the tree has about $\log_b n$ levels, ending in $a^{\log_b n} = n^{\log_b a}$ leaves.

The master theorem

Compare $f(n)$ with $n^{\log_b a}$ , the number of leaves.

If $f(n)$ grows polynomially slower, the leaves dominate: $T(n) = \Theta(n^{\log_b a})$ .
If they grow at the same rate, every level does about the same work: $T(n) = \Theta(n^{\log_b a} \log n)$ . More generally, if $f(n) = \Theta(n^{\log_b a}\log^k n)$ then $T(n) = \Theta(n^{\log_b a}\log^{k+1} n)$ .
If $f(n)$ grows polynomially faster (and satisfies a mild regularity condition, which polynomials do), the root dominates: $T(n) = \Theta(f(n))$ .

Worked examples

Merge sort, $T(n) = 2T(n/2) + n$ . Here $n^{\log_2 2} = n$ , the same as $f(n)$ : case 2, $\Theta(n \log n)$ .
Binary search, $T(n) = T(n/2) + 1$ . $n^{\log_2 1} = n^0 = 1$ , the same as $f(n)$ : case 2, $\Theta(\log n)$ .
Karatsuba multiplication, $T(n) = 3T(n/2) + n$ . $n^{\log_2 3} \approx n^{1.585}$ beats $n$ : case 1, $\Theta(n^{1.585})$ , better than the schoolbook $\Theta(n^2)$ .
Strassen’s matrix multiplication, $T(n) = 7T(n/2) + n^2$ . $n^{\log_2 7} \approx n^{2.807}$ beats $n^2$ : case 1. With 8 subproblems instead of 7 it would be $\Theta(n^3)$ .
$T(n) = 2T(n/2) + n^2$ . $n^2$ beats $n^{\log_2 2} = n$ : case 3, $\Theta(n^2)$ . The top level already does half of all the work.

The table of exact values computes $T(n)$ directly from the recurrence for $n = b, b^2, \dots, b^{10}$ and divides by the bound. If the bound is right, the ratio settles towards a constant, which is a good way to convince yourself of the answer without trusting the theorem.

Recurrences of other shapes, such as $T(n) = T(n-1) + n$ (selection sort, $\Theta(n^2)$ ) or $T(n) = T(n-1) + T(n-2) + 1$ (naive Fibonacci, exponential), are outside the master theorem. Write them as a function in the first tab to see their trees.

Learn the background

The recursion explainer walks through the call stack for factorial and Fibonacci line by line, and Big-O notation explains the growth rates the master theorem produces.

References

J. L. Bentley, D. Haken and J. B. Saxe, “A general method for solving divide-and-conquer recurrences”, ACM SIGACT News 12(3), 1980. doi:10.1145/1008861.1008865
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 4.