Recursion

Recursion is not just a theoretical concept. In technical interviews, it shows up far more often than most candidates expect. If you look at common interview problem sets such as LeetCode Top 100, Blind 75, or typical FAANG interview prep lists, you will notice something important: roughly 30 to 40 percent of medium-level problems rely directly on recursion or a recursive thinking pattern. This includes nearly all binary tree problems, most backtracking problems, many divide-and-conquer algorithms, and the starting point for many dynamic programming solutions.

Despite how common it is, recursion is also one of the top three topics candidates struggle with. The difficulty usually comes from tracing calls instead of understanding structure. However, the reality is simple: recursion is a structured way of breaking a problem into smaller copies of itself. Once you understand that structure, many “hard” problems suddenly become manageable.

Understanding the recursive behavior

Imagine you are holding a large Russian nesting doll. You open it and find a smaller doll inside. You open that smaller doll and find an even smaller one inside it. You keep repeating the same action until you reach the smallest doll, which cannot be opened.

This nesting-doll setup mirrors these patterns:

• Each doll contains a smaller version of itself.
• Each step repeats the same action.
• And, there is a clear stopping point.

This is nothing but recursion.

What is Recursion

Recursion is a programming technique where a function calls itself to solve a smaller version of the same problem, and continues doing so until it reaches a base case.

If we connect this formal definition back to the nesting doll example we wrote above:

• A function calling itself is equivalent to opening the next smaller doll. The same action is repeated, just on a smaller version.
• A smaller version of the same problem is equivalent to a smaller doll inside. The structure remains the same, only the size changes.
• The base case is equivalent to the smallest doll that cannot be opened. It is the clear stopping point of the process.
• Returning the result is equivalent to closing the dolls one by one. Each layer finishes its work as the process moves back outward.

So, when you think about recursion in interviews, do not think about complex call stacks or abstract theory first. Think about nesting dolls. You handle one layer, trust the smaller layer to handle itself, and stop when there is nothing left to open. That is recursion in its simplest and most intuitive form.

Code example of recursion

Fibonacci numbers form a sequence where each number is the sum of the two numbers before it.

The sequence starts like this:

0, 1, 1, 2, 3, 5, 8, 13, …

This definition naturally fits recursion because the problem “compute Fibonacci(n)” depends on two smaller versions of the same problem: “compute Fibonacci(n-1)” and “compute Fibonacci(n-2)”.

Let’s look at the Python implementation of the Fibonacci numbers.

def fib(n):
    # Base case 1: fib(0) is 0
    if n == 0:
        return 0
    
    # Base case 2: fib(1) is 1
    if n == 1:
        return 1
    
    # Recursive step: solve the smaller problems and add results
    return fib(n - 1) + fib(n - 2)


# Example run
print("Fibonacci of 6 is:", fib(6))  # Output should be 8

How recursion works internally: The call stack

When a function calls itself, your program needs a way to remember where it left off. It does this by using a structure called the call stack.

A call stack works like a real stack of plates.

• Each time a function is called, a new “plate” is placed on top of the stack.
• Each plate stores the function’s local details, such as parameters, local variables, and return address.
• When the function finishes, its plate is removed from the top of the stack.

This matters because recursion creates many function calls, which means the stack can grow quickly.

For factorial(3), the program first calls factorial(3), then factorial(2), then factorial(1). Once it reaches factorial(1), it starts returning back up: factorial(1) returns 1, then factorial(2) returns 2, and finally factorial(3) returns 6.

Why interviewers care about the call stack

The deeper the recursion, the more memory the call stack uses. If recursion becomes too deep, the program can run out of stack space and crash. This is called a stack overflow.

That is why interview answers often mention:

• Time complexity (how many calls happen)
• Space complexity (how deep the stack becomes)

In recursive solutions, the space complexity is O(recursion depth), because that is how many function calls sit on the stack at the same time.

Important recursion patterns

In interviews, recursion problems are rarely random. Most of them follow a small number of repeating patterns. Once you learn to recognize these patterns, writing the solution becomes much easier. Instead of thinking from scratch every time, you simply identify the pattern and apply the right structure.

The table below summarizes the five most important recursion patterns you should know for coding interviews.

How to analyze time complexity in recursion

Time complexity questions are common in interviews, and recursion can feel tricky unless you follow a simple rule: focus on how many calls happen.

The three common cases are:

• Linear recursion (one call per level): If each function call makes one smaller call (like n → n-1), the total work is usually O(n).
• Exponential recursion (branching calls): If each call makes two or more recursive calls (like Fibonacci calling fib(n-1) and fib(n-2)), the number of calls grows fast and is often O(2ⁿ) (or similar exponential growth).

• Divide and conquer (split into halves): In divide-and-conquer, total time depends on how many subproblems you create, how much work is done per level, and how many levels (usually log n) the recursion has. For example, Merge Sort does O(n) work per level, i.e., O(n log n), while Binary Search does O(1) work per level, i.e., O(log n).

The two questions to always ask are:

• How many recursive calls does each call create? (1 call, 2 calls, k calls?)
• How many levels deep does the recursion go? (how many times can you shrink before stopping?)

These two answers usually give you the time complexity.

Recursion vs. Iteration

One of the most common follow-up questions in interviews is:

“Can you solve this without recursion?”

This is why it is important to understand the difference between recursion and iteration. In practice, both approaches can solve many of the same problems. The difference lies in how the solution is structured and how memory is used.

Recursion solves a problem by breaking it into smaller versions of itself and letting the function call itself. Iteration solves a problem by repeating a set of instructions using loops such as for or while.

Both are valid tools. The key is knowing when one is more appropriate than the other.

If you want to see the iteration in action, let’s look at the iterative version of Fibonacci numbers:

def fib_iterative(n):
    # Handle small inputs directly
    if n == 0:
        return 0
    if n == 1:
        return 1

    # Start from fib(0) and fib(1)
    prev2 = 0  # fib(i-2)
    prev1 = 1  # fib(i-1)

    # Build up from 2 to n
    for _ in range(2, n + 1):
        curr = prev1 + prev2  # fib(i)
        prev2 = prev1         # shift forward
        prev1 = curr          # shift forward

    return prev1


print("Fibonacci of 6 is:", fib_iterative(6))  # 8

When to prefer iteration

Iteration is usually better when:

• The problem is linear and easy to handle with a loop
• Recursion depth could become very large
• You want more control over memory and performance
• You want to avoid stack overflow risks

A simple memory trick for recursion: BASE

To quickly check if your recursive solution is correct, remember the word BASE:

• B—Base case: Define the clear stopping point.
• A—Advance: Make sure each step moves closer to the base case.
• S—Smaller subproblem: Solve a smaller version of the same problem.
• E—Exit condition: Ensure recursion eventually stops and returns.

If all four are present, your recursion is structurally sound.

Common mistakes to avoid for recursion

Even strong candidates lose points on recursion because of small structural mistakes. Watch out for these:

• Forgetting the base case: Without a stopping condition, the recursion never ends and leads to a stack overflow.
• Incorrect base case: A wrong or incomplete base case can return incorrect results, even if the recursive logic looks right.
• Not reducing the input: Each recursive call must move closer to the base case. If the input does not shrink, the recursion will loop forever.
• Forgetting to undo changes in backtracking: In backtracking problems, you must revert choices before exploring the next option. Missing this step causes wrong answers.
• Not understanding what the function returns: Always be clear about what each recursive call returns and how results are combined.
• Ignoring space complexity: Recursive solutions use the call stack. Deep recursion increases memory usage and may cause stack overflow.

Avoiding these mistakes makes your recursive solutions safer, cleaner, and interview-ready.