Recursion Visualizer -- Watch the Call Stack Build and Unwind

How Recursion Works

Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller, similar subproblems. Every recursive function needs two essential components:

• Base case: The simplest version of the problem that can be solved directly without further recursion. This prevents infinite loops.
• Recursive case: The part where the function calls itself with a modified input, moving toward the base case.

When a function calls itself, the current execution pauses and a new stack frame is created. This frame stores the function's arguments, local variables, and return address. When the recursive call completes and returns a value, the frame is removed (popped) from the stack, and execution resumes in the previous frame.

Understanding the Call Stack

The call stack is a Last-In-First-Out (LIFO) data structure that tracks active function calls. In the visualizer above:

• Each colored box represents a stack frame.
• Frames stack upward as new recursive calls are made.
• When a call returns, its frame disappears from the top of the stack.
• The color indicates the frame's state: active (currently executing), waiting (paused for a deeper call), returned (value computed), or base case.

The Functions Explained

Fibonacci

Calculates the nth Fibonacci number by recursively summing fib(n-1) + fib(n-2). This illustrates the inefficiency of naive recursion: many values are computed multiple times. For example, fib(5) calls fib(3) twice and fib(2) three times. Time complexity: O(2^n).

Factorial

Calculates n! = n * (n-1)! recursively. Each call multiplies the current value by the result of the next smaller factorial. This is a simple linear recursion with O(n) time complexity and O(n) space for the call stack.

Tower of Hanoi

A classic puzzle: move n disks from one peg to another using a third auxiliary peg. Only one disk can be moved at a time, and a larger disk can never sit on a smaller one. The recursive solution moves n-1 disks to the auxiliary peg, moves the largest disk to the destination, then moves the n-1 disks to the destination. Requires 2^n - 1 moves.

Binary Search

Searches for a target value in a sorted array by repeatedly dividing the search space in half. If the middle element is the target, return it. Otherwise, recurse on the left or right half. Time complexity: O(log n). This demonstrates how recursion can efficiently solve divide-and-conquer problems.

Power (Exponentiation)

Computes a^n using fast exponentiation (exponentiation by squaring). If n is even, compute (a^(n/2))^2. If odd, compute a * a^(n-1). This reduces time complexity from O(n) for naive iteration to O(log n).

When to Use Recursion

Recursion vs Iteration

Any recursive algorithm can be rewritten using iteration (loops), and vice versa. Recursion is often more elegant and easier to understand for problems with a natural recursive structure (like trees). However, recursion has overhead: each call consumes stack space, and deep recursion can cause stack overflow errors.

Iteration uses less memory and is faster for simple repetitive tasks. For problems like Fibonacci, an iterative or dynamic programming approach is far more efficient than naive recursion.

Time Complexity of Each Function

Frequently Asked Questions

What recursive functions does this visualizer support?

This visualizer supports Fibonacci sequence, factorial, Tower of Hanoi, binary search, and fast exponentiation. Each function animates the call stack showing how frames are pushed and popped.

What is a call stack?

A call stack is a data structure that tracks active function calls. When a function calls itself recursively, a new frame is pushed onto the stack. When a call returns, its frame is popped. The visualizer shows this process step by step.

Why is recursive Fibonacci slow?

Naive recursive Fibonacci has O(2^n) time complexity because it recalculates the same subproblems many times. For example, fib(5) calls fib(3) twice and fib(2) three times. This is why memoization or dynamic programming is preferred.

What is a base case in recursion?

A base case is the condition that stops the recursion. Without a base case, the function would call itself infinitely and cause a stack overflow. For factorial, the base case is n = 0 or n = 1, which returns 1 directly.

How deep can the call stack go?

The maximum call stack depth depends on your browser and available memory. Most browsers support thousands of frames, but deeply recursive algorithms (like fib(30)) can quickly exceed limits. This is why iteration or tail-call optimization is preferred for deep recursion.

Does this tool store any data?

No. All visualizations run entirely in your browser. No data is sent to any server.

Related Tools

• Sorting Algorithm Visualizer -- watch bubble sort, merge sort, quick sort animate step by step
• Binary Calculator -- perform binary arithmetic and bitwise operations
• Number Line Visualizer -- plot points and intervals on an interactive number line
• Probability Distribution Visualizer -- visualize normal, binomial, and other distributions

Privacy

This tool runs entirely in your browser. No recursion data or interaction history is sent to any server. Nothing is stored.