Recursion
Last updated
Recursion is a function calling itself on a smaller version of the same problem, until it reaches a case so small it can be answered directly. That directly-answerable case is the base case, and every recursive function needs one: fib(n) keeps splitting into fib(n - 1) and fib(n - 2) until it hits fib(1) or fib(0), which simply return themselves. The visualizer above runs exactly this: press Play and watch the calls branch out into a tree, reach the base cases at the leaves, and then return their values back up, combining at every level.
The second thing the animation shows is the call stack: every call that has started but not yet returned. The stack grows as the calls go deeper, peaks at the recursion depth, and unwinds as results come back, which is why deep recursion can hit a stack overflow while an iterative loop never grows the stack. The same call-shape drives depth-first search, merge sort, and most operations on a binary tree.
Time & space complexity
For the naive recursive Fibonacci shown above, and the two standard fixes:
| Approach | Time | Space | Notes |
|---|---|---|---|
| Naive recursion | O(2^n) | O(n) | The call tree doubles at every level; space is the deepest stack, not the whole tree. |
| With memoization | O(n) | O(n) | Each fib(k) is computed once and cached; repeated subtrees collapse into lookups. |
| Iterative loop | O(n) | O(1) | Two rolling variables replace the stack entirely. |
| Any recursion, in general | calls × work per call | O(max depth) | The stack holds one frame per call that has started but not returned. |
Step by step
| Step | What happens |
|---|---|
| 1 | The first call fib(n) goes on the call stack. |
| 2 | It needs fib(n - 1), so that call goes on the stack too; the parent waits. |
| 3 | Calls keep nesting until one asks about n <= 1: the base case answers immediately, no deeper call. |
| 4 | The base case's value returns to its parent, which may now start its second call, fib(n - 2). |
| 5 | When both children have returned, the parent adds them and returns too; its frame leaves the stack. |
| 6 | Returning repeats up the tree until the first call's frame pops with the final answer and the stack is empty. |
Worked example
Evaluating fib(4) in exact call order, as the animation plays it:
| Call | Stack at that moment | Returns |
|---|---|---|
fib(4) | fib(4) | waits for children |
fib(3) | fib(4) > fib(3) | waits for children |
fib(2) | fib(4) > fib(3) > fib(2) | waits for children |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (base case) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (base case) |
fib(2) combines | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (base case) |
fib(3) combines | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) again | fib(4) > fib(2) | 1, recomputed from scratch |
fib(4) combines | fib(4) | 2 + 1 = 3 |
When to use recursion
| Use it when | Avoid it when |
|---|---|
| The problem is self-similar: trees, nested structures, divide and conquer | A simple loop expresses the same thing without stack frames |
The depth is bounded and modest, like O(log n) in merge sort | The depth can reach the input size on huge inputs, risking a stack overflow |
| Backtracking needs the stack to remember where to resume | The same subproblems repeat and you are not caching them |
| The recursive version is clearly easier to read and verify | You are in a hot loop where call overhead measurably matters |
Recursion code
A clean, runnable Recursion implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Recursion code in Python
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Recursion code in JavaScript
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Recursion code in Java
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Recursion code in C++
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Recursion code in C
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Recursion FAQ
What is a base case in recursion?
The input small enough to answer without another recursive call. For
fib(n) it is n <= 1, which returns n directly. Without a reachable base case the calls never stop, the stack keeps growing, and the program crashes with a stack overflow.What is the call stack and why does it matter?
The runtime keeps one frame per call that has started but not yet returned, holding its arguments and local variables. Recursion depth equals stack height, so a recursion that goes
n levels deep uses O(n) memory even if each call does almost no work. The chip row under the animation shows exactly this stack growing and unwinding.Why does recursive Fibonacci take exponential time?
Because the same subproblems are recomputed again and again: in the worked example above,
fib(2) is evaluated twice inside fib(4), and the duplication doubles roughly every level, giving O(2^n) calls. Caching each result the first time it is computed, called memoization, collapses the tree to O(n).Is recursion better than iteration?
Neither is universally better. Every recursion can be rewritten as a loop with an explicit stack, and every loop as a recursion. Recursion wins on readability for self-similar problems like tree traversal and depth-first search; iteration wins on memory and call overhead for linear passes.
What causes a stack overflow in a recursive function?
Either a missing or unreachable base case, so the calls never stop, or a correct recursion whose depth is simply too large for the runtime's stack limit, like recursing once per element on an input of millions. The fixes are guaranteeing the base case, bounding the depth, or converting to iteration.
Which algorithms are naturally recursive?
Divide-and-conquer sorts like merge sort and quicksort, traversals of a binary tree and of graphs, binary search, backtracking puzzles like N-queens, and anything defined over nested structure such as JSON or a file system.
Related resources
More visualizations
