Recursion is when a function calls itself to solve a smaller version of the same problem. It keeps calling itself until it hits a stopping condition, then works its way back up with the answers.
In simple language, think of it like Russian nesting dolls. We keep opening dolls until we find the smallest one (the base case), then we put them back together one by one.
The Two Ingredients
Every recursive function needs exactly two things:
- Base case — the condition where we STOP recursing. Without it, we get infinite recursion and a stack overflow.
- Recursive case — the part where the function calls itself with a smaller/simpler input.
function countdown(n) {
if (n <= 0) { // base case -- stop here
console.log("Done!");
return;
}
console.log(n);
countdown(n - 1); // recursive case -- smaller input
}
// countdown(3) prints: 3, 2, 1, Done!def countdown(n):
if n <= 0: # base case -- stop here
print("Done!")
return
print(n)
countdown(n - 1) # recursive case -- smaller input
# countdown(3) prints: 3, 2, 1, Done!static void countdown(int n) {
if (n <= 0) { // base case -- stop here
System.out.println("Done!");
return;
}
System.out.println(n);
countdown(n - 1); // recursive case -- smaller input
}
// countdown(3) prints: 3, 2, 1, Done!The Call Stack
When a function calls itself, the current call gets paused and pushed onto the call stack. Each call waits for the one below it to return before it can finish.
Here’s what happens when we call factorial(4):
Each call adds a frame to the stack. Once the base case returns, the frames start popping off one by one, combining their results.
Classic Examples
Factorial
n! = n * (n-1) * (n-2) * … * 1. The base case is 1! = 1.
function factorial(n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // n * (n-1)!
}
// factorial(5) => 5 * 4 * 3 * 2 * 1 => 120def factorial(n):
if n <= 1:
return 1 # base case
return n * factorial(n - 1) # n * (n-1)!
# factorial(5) => 5 * 4 * 3 * 2 * 1 => 120static int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // n * (n-1)!
}
// factorial(5) => 5 * 4 * 3 * 2 * 1 => 120Time: O(n) — we make n calls. Space: O(n) — n frames on the call stack.
Fibonacci
Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13…
function fib(n) {
if (n <= 0) return 0; // base case 1
if (n === 1) return 1; // base case 2
return fib(n - 1) + fib(n - 2);
}
// fib(6) => 8def fib(n):
if n <= 0:
return 0 # base case 1
if n == 1:
return 1 # base case 2
return fib(n - 1) + fib(n - 2)
# fib(6) => 8static int fib(int n) {
if (n <= 0) return 0; // base case 1
if (n == 1) return 1; // base case 2
return fib(n - 1) + fib(n - 2);
}
// fib(6) => 8Time: O(2^n) — each call branches into two more. Extremely slow for large n. We’ll fix this with memoization (dynamic programming) later.
Sum of an Array
Break the problem down: the sum of an array is the first element plus the sum of the rest.
function sumArray(arr) {
if (arr.length === 0) return 0; // base case: empty array
return arr[0] + sumArray(arr.slice(1)); // first + sum of rest
}
// sumArray([1, 2, 3, 4]) => 10def sum_array(arr):
if len(arr) == 0:
return 0 # base case: empty list
return arr[0] + sum_array(arr[1:]) # first + sum of rest
# sum_array([1, 2, 3, 4]) => 10static int sumArray(int[] arr, int i) {
if (i >= arr.length) return 0; // base case: past the end
return arr[i] + sumArray(arr, i + 1); // current + sum of rest
}
// sumArray(new int[]{1, 2, 3, 4}, 0) => 10Recursion vs Iteration
Every recursive solution can be rewritten as a loop (and vice versa). So when do we pick which?
| Recursion | Iteration |
|---|---|
| Cleaner for tree/graph traversal | Better for simple linear problems |
| Uses call stack memory (O(n) space) | Usually O(1) space |
| Risk of stack overflow for deep recursion | No stack overflow risk |
| Easier to express divide-and-conquer | More performant in most languages |
Think of it like this: if the problem has a tree-like structure (sub-problems branching out), recursion is natural. If it’s a straight-line walk through data, a loop is simpler.
Common Pitfalls
1. Missing or Wrong Base Case
Without a base case, the function calls itself forever until the stack overflows.
// BAD -- no base case, infinite recursion
function oops(n) {
return n + oops(n - 1); // never stops!
}
// GOOD -- base case stops the recursion
function sum(n) {
if (n <= 0) return 0; // this is what saves us
return n + sum(n - 1);
}# BAD -- no base case, infinite recursion
def oops(n):
return n + oops(n - 1) # never stops!
# GOOD -- base case stops the recursion
def sum_n(n):
if n <= 0:
return 0 # this is what saves us
return n + sum_n(n - 1)// BAD -- no base case, infinite recursion
static int oops(int n) {
return n + oops(n - 1); // never stops!
}
// GOOD -- base case stops the recursion
static int sum(int n) {
if (n <= 0) return 0; // this is what saves us
return n + sum(n - 1);
}2. Not Shrinking the Problem
Each recursive call MUST make the problem smaller. If we pass the same input, we loop forever.
3. Stack Overflow
Deep recursion (say, factorial(100000)) can crash the program. Most languages have a call stack limit (around 10,000-15,000 frames). For deep recursion, either convert to iteration or use tail-call optimization (where supported).
In simple language, recursion is powerful but we need to respect its limits. Start with the base case, make sure we’re always moving toward it, and watch the call stack depth.