Recursion
Watch the call stack grow and shrink, and see the recursion tree branch out — with pseudocode highlighting the line that's executing right now.
Factorial
The textbook first example of recursion. n! is defined by a base case (0! = 1) and a recursive case (n! = n × (n-1)!). Each call pushes a new frame and waits for its single recursive child to return before it can multiply and hand its own result back down the stack — a straight chain n frames deep.
Open visualizer
O(log(min(a, b))) · O(log(min(a, b))) spaceEuclid's GCD
Computes the greatest common divisor with Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), until b reaches 0 — at which point a is the answer. Each step's arguments shrink fast (by at least the golden ratio), so the call stack never gets deep even for large numbers.
Open visualizer
O(2ⁿ) · O(n) spaceFibonacci (naive)
The classic example of exponential recursion. fib(n) = fib(n-1) + fib(n-2) branches into two recursive calls every time, and because fib(n-2) gets fully recomputed inside both branches — nothing is remembered between calls — the same sub-calls repeat over and over. The recursion tree's size explodes exponentially with n, which is exactly why memoization exists.
Open visualizer
O(2ⁿ) · O(n) spaceTower of Hanoi
Move n disks from one peg to another, one at a time, never placing a larger disk on a smaller one. The recursive insight: to move n disks from A to C, first move the top n-1 disks out of the way onto the spare peg, move the largest disk directly, then move those n-1 disks onto it. Each call branches into exactly two same-sized recursive calls around one move, giving 2ⁿ - 1 moves in total.
Open visualizer