DevPath
Tracks

Recursion

Solve a problem by solving smaller copies of it: base cases, the call stack, divide and conquer, and memoization as a first step to dynamic programming.

beginner40 min#recursion#call-stack#base-case#memoization#divide-and-conquer

Prerequisites: Stacks and Queues, How Computers Run Programs

Why it matters

Recursion is the natural way to process anything that contains smaller copies of itself: nested folders, JSON, expression trees, and the branching choices in puzzles. Trees, graph traversals, merge sort, quicksort, backtracking and dynamic programming all rest on it. If you can describe a problem as "do a little work, then solve a smaller version of the same problem", the code is often just a few lines.

Intuition

Russian nesting dolls: to count the dolls, open the outer one. If it is empty, the count is 1. Otherwise the count is 1 plus the count for the doll inside. You never need the whole plan; you only need to trust that the smaller call returns the right answer and then combine it with your own step.

Every recursive function has two parts:

  1. Base case: an input so small that the answer is immediate. Without it the function calls itself forever.
  2. Recursive case: reduce the input (strictly toward the base case), call yourself, and combine the result.

How it works

The call stack. Each call gets its own frame holding its parameters, local variables and where to return. Calls pile up until the base case answers, then frames pop off one by one as each caller finishes its combination step.

depth(3)
  -> 1 + depth(2)
          -> 1 + depth(1)
                  -> 1 + depth(0)
                          -> 0          base case returns
                  <- 1 + 0 = 1
          <- 1 + 1 = 2
  <- 1 + 2 = 3

At the deepest point of depth(3), four frames are waiting on the stack. The top frame answers first, then each one below it can finish.

depth(0)top: base case, returns 0 right now
depth(1)waiting: will return 1 + 0
depth(2)waiting: will return 1 + 1
depth(3)bottom: waiting, will return 1 + 2
Each call adds a frame until the base case, then frames pop off from the top. Four frames for n = 3 is why depth(n) uses O(n) stack space.

The stack has finite size. Python's default limit is about 1000 frames (it raises a RecursionError) and JavaScript engines allow roughly ten thousand or so before a RangeError. Recursion depth, not just time, is a cost: depth(n) uses O(n) stack space.

The power(2, 30) call from the code below halves the exponent each time, so it stacks up only 6 frames. Each number in the cells is one frame's exponent; the rightmost cell is the top of the stack.

30
0
top
power(2, 30) starts. It needs power(2, 15) first.
step 1 / 8

The stack grows while the exponent halves, then unwinds as each frame combines its half with its own step.

Divide and conquer. If each call halves the input (like power below, or merge sort), the depth is only O(log n) and the code is both short and fast.

Overlapping subproblems. A naive recursive Fibonacci recomputes the same values exponentially many times: fib(5) calls fib(3) twice, fib(2) three times, and so on, giving about 1.6^n calls. Memoization fixes this: store each result in a map keyed by the arguments, and return the stored answer on repeat calls. The calls drop from exponential to linear, because each distinct input is computed once. This is top-down dynamic programming, covered in its own lesson.

Here is that blow-up for fib(4), which makes 9 calls, and then the memoized version. Step through all four views.

fib(4)fib(3)fib(2)fib(1)fib(0)fib(1)fib(2)fib(1)fib(0)
Naive recursion tree for fib(4). Every node is a call, 9 calls in total.
step 1 / 4

Overlapping subproblems: the same fib(k) appears in many branches. Memoization prunes every repeat branch down to one cached lookup.

Recursion versus loops. Any recursion can be rewritten with a loop and an explicit stack. Prefer a loop when the recursion is simple tail-style repetition or when depth could be huge. Neither Python nor most JavaScript engines optimize tail calls, so do not rely on that.

OperationTimeNotes
Linear recursion (depth(n))O(n) time, O(n) stackOne call per level
Halving (power, binary search)O(log n)Depth is log n
Naive FibonacciO(2^n) roughlyOverlapping subproblems recomputed
Fibonacci with memoizationO(n) time, O(n) spaceEach n solved once
Divide and conquer (merge sort)O(n log n)Two halves plus linear merge

Code: nested sums, fast power, and memoization

def total(nested):
    """Sum a list that may contain lists, to any depth."""
    result = 0
    for item in nested:
        if isinstance(item, list):
            result += total(item)   # smaller sub-problem
        else:
            result += item          # base case: a plain number
    return result
 
 
def power(base, exp):
    if exp == 0:                    # base case
        return 1
    half = power(base, exp // 2)    # halve the problem each call
    return half * half if exp % 2 == 0 else half * half * base
 
 
calls = 0
 
 
def fib_slow(n):
    global calls
    calls += 1
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
 
 
def fib_memo(n, memo=None, counter=None):
    memo = {} if memo is None else memo
    counter = [0] if counter is None else counter
    counter[0] += 1
    if n < 2:
        return n, counter[0]
    if n not in memo:
        a, _ = fib_memo(n - 1, memo, counter)
        b, _ = fib_memo(n - 2, memo, counter)
        memo[n] = a + b
    return memo[n], counter[0]
 
 
def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)
 
 
print(total([1, [2, [3, 4]], [], 5]))
print(power(2, 30), power(3, 5))
print(fib_slow(25), calls)
print(fib_memo(25))
print(depth(500))

Both versions print:

15
1073741824 243
75025 242785
(75025, 49)
500

fib(25) is 75025. The naive version needed 242,785 calls to compute it, while the memoized version used only 49 (one call per value from 25 down to 0, plus the repeat calls that hit the stored answer immediately). power(2, 30) needs only 6 nested calls (exponents 30, 15, 7, 3, 1, 0) instead of 30 multiplications.

Common pitfalls

  • Missing or unreachable base case: leads to infinite recursion and a stack overflow. Check empty inputs, zero, null.
  • Not shrinking the problem: calling with the same arguments, or growing them, never terminates.
  • Mutable default arguments (Python): def f(x, memo={}) shares one dict across all calls forever. Use None and create it inside, or functools.lru_cache.
  • Exponential blowup: two recursive calls on overlapping inputs need memoization.
  • Deep recursion on big input: a linked list or skewed tree with 100,000 nodes can overflow the stack. Convert to a loop or an explicit stack.
  • Forgetting to return the recursive result: the function runs but returns None or undefined.

Practice

Sum of digits easy

Hint

What is the base case, and how do you peel off one digit?

Show solution

If n < 10 return n. Otherwise return n % 10 + sum_digits(n // 10). The depth equals the number of digits, so O(d) time and stack space.

Reverse a string recursively easy

Hint

Reverse the rest and put the first character at the end.

Show solution

If the string has at most one character, return it. Otherwise return reverse(s[1:]) + s[0]. It is O(n^2) in practice because of slicing and concatenation; a loop or index-based version is better, but this shows the pattern.

Generate all subsets medium

Hint

For each item you have two choices. How does the problem shrink?

Show solution

For item i, recurse twice: once without it and once with it added to the current subset. When i == n, record the subset. There are 2^n subsets, so O(n * 2^n) time. This is the template for backtracking.

Climbing stairs and its memoized form hard

Hint

To reach step n you came from step n - 1 or n - 2. Does this look like another famous sequence?

Show solution

ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. The naive version is exponential. Add a memo map to make it O(n) time and space, or keep only the last two values in a loop for O(1) space. Recognizing that this is Fibonacci in disguise is the point.

Interview questions

  1. What happens if there is no base case? Calls pile up until the stack overflows (RecursionError in Python, RangeError in JavaScript).
  2. How do you convert recursion into iteration? Use an explicit stack holding what the call frames held, or restructure into a loop if the recursion is linear.
  3. Why is naive Fibonacci exponential, and how do you fix it? It re-solves overlapping subproblems; memoize or build bottom-up.
  4. What is the space cost of recursion? At least the maximum call depth, even if you allocate nothing else.

Interviewers look for: naming the base case first, proving the input shrinks, stating time and stack space, and spotting overlapping subproblems before being asked.

Quick check

A recursive function halves its input each call and does O(1) other work. About how many calls happen for n = 1,000,000?

Finished this lesson?

Further resources

Related lessons