Recursion and Base Cases

Recursion solves a problem by having a function call itself on a smaller version of the same problem, until the input is so small the answer is obvious. That obvious answer is the base case, and it is what stops the calls from going on forever. Interviewers like it because it shows whether you can trust a function to do its job on smaller input and combine the results, which is the core idea behind trees, backtracking, divide and conquer, and dynamic programming.

When to use it

  • The problem has a natural 'smaller version of itself', such as a list minus its first item, or a tree's left and right subtrees.
  • The data is a tree, a nested structure, or a linked list, and you need to visit or summarize every part of it.
  • You are asked to generate all combinations, permutations, or subsets (usually recursion with backtracking).
  • The answer for size n can be built from the answer for size n-1 or n/2 (factorials, Fibonacci, powers, merge sort).
  • You find yourself writing a loop inside a loop inside a loop and the depth depends on the input.

See it work

  1. Problem: compute the sum of the list [3, 1, 4, 2] recursively. Define sum(i) as the sum of everything from index i to the end. The big idea: sum(i) = nums[i] + sum(i+1). We start at i = 0. [3, 1, 4, 2]
  2. We can't finish sum(0) yet, so it waits and calls sum(1). The call stack grows: sum(0) is paused, sum(1) is now running and needs 1 + sum(2). [3, 1, 4, 2]
  3. The same thing happens at index 2 and then index 3. Each call pauses and waits for a smaller call. Now the stack holds sum(0), sum(1), sum(2), sum(3). [3, 1, 4, 2]
  4. Base case: i = 4 is past the end of the list, so there is nothing left to add. sum(4) returns 0 right away without calling anything. This is what stops the recursion. [3, 1, 4, 2]
  5. Now the calls unwind and each paused call finishes: sum(3) = 2 + 0 = 2, then sum(2) = 4 + 2 = 6, then sum(1) = 1 + 6 = 7, then sum(0) = 3 + 7 = 10. [3, 1, 4, 2]
  6. The final answer is 10. Remember the recipe: (1) write the base case first, (2) make the call on a strictly smaller input, (3) combine the smaller answer with the current piece. [3, 1, 4, 2]

Code template

Python

def solve(state):
    # 1. Base case: input is small enough to answer directly
    if is_smallest(state):
        return base_answer

    # 2. Shrink the problem: make a strictly smaller input
    smaller = shrink(state)

    # 3. Trust the recursive call to solve the smaller input
    result = solve(smaller)

    # 4. Combine the small answer with the current piece
    return combine(state, result)

# Example: sum of a list from index i
def list_sum(nums, i=0):
    if i == len(nums):          # base case
        return 0
    return nums[i] + list_sum(nums, i + 1)

C

/* Generic shape of a recursive solution */
int solve(State state) {
    /* 1. Base case: input is small enough to answer directly */
    if (is_smallest(state)) return base_answer;

    /* 2. Shrink the problem: make a strictly smaller input */
    State smaller = shrink(state);

    /* 3. Trust the recursive call to solve the smaller input */
    int result = solve(smaller);

    /* 4. Combine the small answer with the current piece */
    return combine(state, result);
}

/* Example: sum of an array from index i */
int list_sum(const int *nums, int n, int i) {
    if (i == n) return 0;             /* base case */
    return nums[i] + list_sum(nums, n, i + 1);
}

Java

// Generic shape of a recursive solution
int solve(State state) {
    // 1. Base case: input is small enough to answer directly
    if (isSmallest(state)) return baseAnswer;

    // 2. Shrink the problem: make a strictly smaller input
    State smaller = shrink(state);

    // 3. Trust the recursive call to solve the smaller input
    int result = solve(smaller);

    // 4. Combine the small answer with the current piece
    return combine(state, result);
}

// Example: sum of an array from index i
int listSum(int[] nums, int i) {
    if (i == nums.length) return 0;   // base case
    return nums[i] + listSum(nums, i + 1);
}

Complexity: Time is usually (number of calls) × (work per call), for example O(n) for list sum and O(2^n) for naive Fibonacci; space is O(depth of recursion) for the call stack, so O(n) for list sum and O(log n) for a balanced tree or binary search.

Programs that use it

Interview problems that use it

  • Factorial / Power of x to the n: Base case is n = 0 (answer 1); otherwise multiply by the result for n-1, or halve n for fast exponentiation.
  • Maximum depth of a binary tree: An empty node has depth 0; otherwise the depth is 1 plus the larger depth of the left and right subtrees.
  • Reverse a linked list: Base case is an empty list or a single node; reverse the rest, then attach the current node at the end.
  • Generate all subsets of a list: At each item, branch into 'include it' and 'skip it'; when you pass the last item, record the subset built so far.
  • Merge sort: A list of 0 or 1 items is already sorted; otherwise sort each half recursively and merge the two sorted halves.
  • Palindrome check on a string: Base case is length 0 or 1 (true); otherwise the ends must match and the inner substring must also be a palindrome.

Common mistakes

  • Forgetting the base case or writing one that is never reached, which causes infinite recursion and a stack overflow. Always ask: does every call move closer to the base case?
  • Not covering every base case, such as handling only the empty list but crashing on a single element, or handling a null node in a tree only on one side.
  • Recomputing the same subproblems over and over (as in naive Fibonacci, which takes O(2^n) time). If the same inputs repeat, add memoization to cache results.

Frequently asked questions

What is a base case in recursion?

A base case is the simplest version of the problem, one you can answer directly without another recursive call, like an empty list returning 0 or n = 0 returning 1. Without it the function keeps calling itself until the program crashes with a stack overflow.

How do I know when to use recursion instead of a loop?

Use recursion when the problem has a self-similar structure, such as trees, nested data, or choices that branch (subsets, permutations). A simple loop is usually better for flat, linear tasks. Any recursion can be rewritten with a loop and an explicit stack if needed.

Why do I get a stack overflow or 'maximum recursion depth exceeded' error?

Every call uses space on the call stack, and the stack has a limited size. You get this error when the base case is missing or never reached, or when the input is so deep (for example, a list of 100,000 items) that the stack runs out. Fix the base case first, then consider an iterative solution for very deep inputs.

← All interview patterns

Try AI Flowchart free →