Recursion Foundations
6 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.
What is Recursion?
Recursion is when a function calls itself to solve a smaller version of the same problem. Instead of solving the whole thing at once, you break it into a tiny piece you CAN solve (the base case) and a smaller version of the original problem (the recursive case). The function keeps calling itself with smaller and smaller inputs until it hits the base case, then all the answers bubble back up. Let's see this in action with a classic example: computing factorial, given a number n, compute n! = n × (n-1) × ... × 1.
The intuition
Imagine you're in a line of people and someone asks 'What row am I in?' You don't count everyone. You just ask the person in front of you 'What row are YOU in?' They ask the person in front of them, and so on, until the person at the front says 'Row 1!' Then each person adds 1 and passes the answer back. That's recursion: delegating the work to a smaller version of yourself.
- A recursive function calls ITSELF with a smaller/simpler input
- Every recursion needs a BASE CASE. A condition where it stops and returns directly
- Every recursion needs a RECURSIVE CASE. Where it calls itself with a reduced problem
- The key mindset: 'If I can solve it for n-1, can I use that to solve it for n?'
- Recursion is NOT magic, it's just a function call. The same rules apply (parameters, return values, call stack)
A real-world analogy
Russian nesting dolls (Matryoshka): to find the smallest doll, you open the outer one, then the next, then the next… until you find one that doesn't open. That's the base case. Then you close them back up, that's the unwinding.
function factorial(n):
if n <= 1: // BASE CASE, stop here!
return 1
return n * factorial(n - 1) // RECURSIVE CASE, smaller problemThe Call Stack
Every time a function calls another function (or itself), the computer saves a 'frame' on the call stack, like stacking plates. Each frame remembers the function's local variables, where it was in the code, and what it's waiting for. When the function returns, its frame is popped off the stack. In recursion, each recursive call adds a new frame. Too many calls without returning = Stack Overflow!
The intuition
Think of a stack of sticky notes. Each time you make a recursive call, you write 'come back to this later' on a new sticky note and put it on top. When you hit the base case, you start peeling sticky notes off the top, finishing each task as you go. If you never stop adding sticky notes (no base case), you run out of desk space, that's a stack overflow.
- Each recursive call creates a NEW stack frame with its own copy of local variables
- Frames stack up as calls go deeper, then pop off as functions return (LIFO, Last In, First Out)
- The call stack has a limited size: too deep recursion causes Stack Overflow
- Understanding the stack helps you trace bugs: 'which call am I in? what are my local values?'
- Tail recursion (where the recursive call is the LAST thing) can sometimes be optimized by the compiler to reuse the same frame
A real-world analogy
A stack of cafeteria trays: you add trays on top (function calls) and remove from the top (function returns). If someone keeps adding trays without removing any, the stack topples over (stack overflow).
function sum_to(n):
if n <= 0: return 0 // Base case: pop frame, return 0
return n + sum_to(n-1) // Push new frame, wait for result
// sum_to(4) builds this stack:
// [sum_to(4)] waits for sum_to(3)
// [sum_to(3)] waits for sum_to(2)
// [sum_to(2)] waits for sum_to(1)
// [sum_to(1)] waits for sum_to(0)
// [sum_to(0)] returns 0 ← base case, start popping!
// [sum_to(1)] returns 1+0 = 1
// [sum_to(2)] returns 2+1 = 3
// [sum_to(3)] returns 3+3 = 6
// [sum_to(4)] returns 4+6 = 10Base Case: The Safety Net
The base case is the condition where your recursive function STOPS calling itself and returns a value directly. Without it, recursion never ends: the function calls itself forever until the stack overflows. Every recursive function MUST have at least one base case. The base case answers: 'What's the simplest input I can solve immediately without any further recursion?'
The intuition
Imagine you're walking down a staircase in the dark. Each step, you feel for the next stair. The base case is the floor, solid ground where you stop. Without a floor, you'd fall forever. The base case is your safety net that guarantees the recursion terminates.
- Every recursive function MUST have a base case, no exceptions!
- The base case handles the SMALLEST/SIMPLEST possible input
- Common base cases: n=0, n=1, empty array, null node, empty string
- Missing or wrong base cases = infinite recursion = stack overflow crash
- Some problems need MULTIPLE base cases (e.g., Fibonacci needs n=0 AND n=1)
- The base case should return a meaningful value that the recursive calls can build upon
A real-world analogy
A mirror facing another mirror creates infinite reflections: that's recursion without a base case. Put a piece of cardboard behind one mirror (base case) and the reflections stop at a finite point.
// ❌ BAD: No base case, infinite recursion!
function broken(n):
return broken(n - 1) // Never stops!
// ✅ GOOD: Clear base case
function sum(n):
if n == 0: return 0 // Base case: sum of nothing is 0
return n + sum(n - 1) // Recursive case
// ✅ Multiple base cases (Fibonacci)
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)The Leap of Faith
The Leap of Faith is the #1 tip for writing recursive code. Here's the idea: ASSUME your recursive function already works correctly for smaller inputs. Don't trace through every call. Instead, focus on just THREE things: (1) What's the base case? (2) What does THIS one call need to do? (3) How do I combine my work with the result of the recursive call? If you get these three right, the recursion WILL work. Trust it.
The intuition
Imagine you're a manager. You don't do all the work yourself: you delegate to your team and trust they'll deliver. You only focus on: What's MY part? What do I do with THEIR result? If each person in the chain does their small part correctly and trusts the person below them, the whole chain works. That's the leap of faith.
- DO NOT trace through every recursive call mentally, you'll get lost and confused
- ASSUME the recursive call returns the correct answer for the smaller problem
- Focus ONLY on: (1) Base case, (2) What this call does, (3) How to combine
- If each level does its job correctly, the whole recursion works by mathematical induction
- This is the single most important mindset shift for mastering recursion
- Example: 'If reverseList(head.next) correctly reverses the rest, how do I attach head to make the whole thing reversed?'
A real-world analogy
You're organizing a line of 100 people. Instead of organizing all 100, you tell the first person: 'Organize the 99 people behind you, then stand at the end.' You TRUST person 2 will do the same for the 98 behind them, and so on. Person 100 has nobody behind them (base case). The whole line gets organized without anyone thinking about all 100 people.
// Sum of array using Leap of Faith
def sum_array(arr):
if len(arr) == 0: # Q1: simplest input → return 0
return 0
# Q2: TRUST sum_array(arr[1:]) gives correct sum of the rest
return arr[0] + sum_array(arr[1:])
# Q3: arr[1:] shrinks by 1 each time → guaranteed to reach []Recursion vs Iteration
Every recursion can be converted to a loop (iteration), and vice versa. Recursion uses the call stack implicitly; iteration uses an explicit loop variable. Recursion is more natural for problems with a tree/branching structure (trees, graphs, backtracking). Iteration is simpler and more efficient for linear problems (summing an array, Fibonacci). Knowing WHEN to use each is a key skill.
The intuition
Recursion is like giving instructions by saying 'do this, then repeat from step 1 with a smaller version.' Iteration is like saying 'keep doing this until done.' Both get you to the same place, but some paths are easier to walk than others.
- Recursion = implicit stack (call stack manages state for you)
- Iteration = explicit loop (YOU manage state with variables)
- Recursion shines for: trees, graphs, divide & conquer, backtracking
- Iteration shines for: linear scans, simple counting, DP with small state
- Recursion has overhead: each call creates a stack frame (memory + time)
- When a problem has BRANCHING (multiple choices per step), recursion is usually more natural
A real-world analogy
Washing dishes: Iteration is 'wash dish, grab next, wash dish, grab next...' Recursion is 'wash this dish, then tell your clone to wash the rest.' Both work, but you wouldn't clone yourself for dishes, you'd just loop. But for exploring a maze with multiple paths? Cloning yourself at each fork (recursion) makes more sense than backtracking manually (iteration with explicit stack).
// Factorial: both approaches
// RECURSIVE (implicit stack):
function factRec(n):
if n <= 1: return 1
return n * factRec(n - 1)
// ITERATIVE (explicit loop):
function factIter(n):
result = 1
for i = 2 to n:
result = result * i
return result
// Both compute the same thing!
// Iterative: O(1) space, no stack overhead
// Recursive: O(n) space from call stackCommon Recursion Patterns
Most recursive problems follow a few recurring patterns. Once you recognize which pattern a problem fits, writing the solution becomes formulaic. The main patterns are: (1) Counting down. Reduce n by 1 each call, (2) Building up return values. Accumulate results as calls return, (3) Passing state via parameters. Carry information DOWN the recursion, (4) Divide & conquer, split the problem in half. Learning these patterns gives you a toolkit for any recursive problem.
The intuition
Think of recursion patterns like recipe templates. A 'stir-fry' template works for hundreds of dishes, you just swap the ingredients. Similarly, once you know the 'accumulator pattern' template, you can apply it to sum, product, string building, and many more problems just by changing what you accumulate.
- Pattern 1, Reduce & Return: reduce input by 1, combine result on the way back (factorial, sum)
- Pattern 2, Accumulator: pass a running result as a parameter, return it at base case (tail recursion)
- Pattern 3, Divide & Conquer: split in half, recurse on both halves, merge results (merge sort)
- Pattern 4, Build & Collect: build partial solutions, collect at base case (permutations, subsets)
- Pattern 5, Tree Recursion: make TWO+ recursive calls per function call (Fibonacci, tree traversal)
- Identifying the pattern is 80% of the work: the code follows naturally from the pattern
A real-world analogy
Like recognizing that 'find the tallest person' follows the same pattern whether it's 'find the max number,' 'find the longest string,' or 'find the heaviest box.' Once you see the pattern, the specific problem doesn't matter.
// Pattern 1: Reduce & Return (factorial)
function factorial(n):
if n <= 1: return 1
return n * factorial(n - 1) // combine on way BACK
// Pattern 2: Accumulator (tail-recursive sum)
function sum(arr, i, acc=0):
if i == arr.length: return acc
return sum(arr, i+1, acc + arr[i]) // carry state DOWN
// Pattern 3: Divide & Conquer (merge sort)
function mergeSort(arr):
if arr.length <= 1: return arr
mid = arr.length / 2
left = mergeSort(arr[0..mid])
right = mergeSort(arr[mid..])
return merge(left, right)
// Pattern 4: Build & Collect (subsets)
function subsets(nums, i, current, result):
if i == nums.length:
result.add(copy(current))
return
current.add(nums[i]) // include nums[i]
subsets(nums, i+1, current, result)
current.removeLast() // exclude nums[i] (backtrack!)
subsets(nums, i+1, current, result)