Skip to main content

Recursion

Recursion is one of the most powerful—and most misunderstood—ideas in programming.

Many candidates can write recursive code, but struggle to explain:

  • Why it works
  • What happens behind the scenes
  • Why it sometimes crashes with a stack overflow

This lesson focuses on clarity, intuition, and mental models, so recursion stops feeling like magic and starts feeling predictable.

What Is Recursion?​

Recursion is when a function calls itself to solve a smaller version of the same problem.

Instead of solving the entire problem at once, you:

  1. Solve one piece of the problem
  2. Delegate the rest to a recursive call

Every recursive solution must have two parts.

Think Functions​

What is a function? A container that produces an output based on some input. With recursion, you can generate the output for some function(A) = some_logic combined with function(B).

The Two Required Parts of Recursion​

1. Base Case (Stopping Condition)​

The base case tells the function when to stop recursing.

Without a base case:

  • The function calls itself forever
  • The program eventually crashes

2. Recursive Case​

The recursive case:

  • Calls the same function
  • Uses a smaller or simpler input
  • Moves closer to the base case

If the problem does not get smaller, recursion will not terminate.

A Simple Mental Model​

Think of recursion as delegation:

“I’ll do my small part of the work,

and trust the same function to handle the rest.”

Each function call:

  • Handles one step
  • Passes the remaining work to the next call

Classic Example: Factorial​

Definition:

5! = 5 × 4 × 3 × 2 × 1

Recursive idea:

  • 5! = 5 × 4!
  • 4! = 4 × 3!
  • ...
  • 1! = 1 ← base case

Recursive Structure​

recursion

factorial(n):
  if n == 1:
    return 1
  return n * factorial(n - 1)

Notice:

  • The problem size decreases (n - 1)
  • There is a clear stopping point

What Actually Happens: The Call Stack​

This is the most important concept to understand recursion.

Every function call:

  • Is pushed onto the call stack
  • Stores its own local variables and execution state

Example: factorial(3)​

Call stack grows like this, function calls are pushed into the stack with inputs:

factorial(3)
  → factorial(2)
      → factorial(1)

Once the base case returns, functions are popped and outputs get computed:

factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6

This process is called stack unwinding.

Stack Growth vs Stack Unwinding​

Stack Growth (Going Down)​

  • Recursive calls are being added
  • No results yet
  • Memory usage increases

Stack Unwinding (Coming Back Up)​

  • Base case is reached
  • Return values flow upward
  • Final answer is computed

Many recursion bugs happen because candidates lose track of which phase they are in.

Stack Overflow (Why Recursion Can Crash)​

A stack overflow occurs when:

  • Too many recursive calls are made
  • The base case is missing or incorrect
  • The input is too large

Example of a broken recursion:

recurse(n):
  return recurse(n - 1)

❌ No base case → infinite recursion → crash

Interview Insight​

If asked:

“What are the downsides of recursion?”

Strong answers mention:

  • Risk of stack overflow
  • Extra memory from call stack
  • Harder debugging compared to loops

How to Think Recursively (Interview Strategy)​

Instead of asking:

“How do I loop through everything?”

Ask:

  1. What is one step of the problem?
  2. What is the rest of the problem?
  3. When should this process stop?

A helpful question:

“If this works for a smaller input, can I use it to solve the current one?”

Recursion vs Iteration​

RecursionIteration
Uses the call stackUses loops
Natural for hierarchical dataOften more memory efficient
Cleaner for treesLess risk of stack overflow

Rule of thumb:

  • Trees & graphs → recursion
  • Simple array processing → iteration

Recursion in Tree Traversal​

Trees are inherently recursive:

  • A tree is a node
  • Each node has child subtrees

Depth-First Traversal Pattern​

dfs(node):
  if node is null:
    return

  process(node)
  dfs(node.left)
  dfs(node.right)

Each call:

  • Handles one node
  • Delegates traversal to children

This pattern shows up constantly in interviews.

Recursion in Graph Traversal​

Graphs also use recursion, but require infinite cycle protection.

dfs(node):
  if node is visited:
    return

  mark node visited
  for neighbor in node.neighbors:
    dfs(neighbor)

Key idea:

  • Recursion explores depth
  • A visited set prevents infinite loops

Quiz​

Question: What does f(3) return for the pseudo-code below?

f(n):
  if n == 0:
    return 1
  return 2 * f(n - 1)

A. 4
B. 6
C. 8
D. 16

Answer
C

Question: Given the pseudo-code, what is sum(4)?

sum(n):
  if n == 1:
    return 1
  return n + sum(n - 1)

A. 4
B. 10
C. 7
D. 1

Answer
B

Question: How many numbers are printed by countDown(3)?

countDown(n):
  if n < 0:
    return
  print(n)
  countDown(n - 1)

A. 2
B. 3
C. 4
D. 5

Answer
C

Question: What is the time complexity of the pseudo-code?

h(n):
  if n == 0:
    return
  h(n - 1)
  h(n - 1)

A. O(n)
B. O(n log n)
C. O(2ⁿ)
D. O(n²)

Answer
C

Question: What does this dfs function compute on a binary tree?

dfs(node):
  if node is null:
    return 0
  left = dfs(node.left)
  right = dfs(node.right)
  return 1 + max(left, right)

A. Number of leaves
B. Tree height
C. Sum of node values
D. Inorder traversal

Answer
B