Recursion for Beginners: How to Think Recursively in Coding Interviews

Recursion is where many self-taught programmers hit a wall. Loops feel concrete: you can watch the variable change. Recursion feels like it works by magic, and the usual advice to "trace through the calls" makes it worse, because tracing a function that branches twice at each level, ten levels deep, is not something a human brain does well.

The fix is a different way of thinking, not more tracing. This guide teaches that way of thinking, shows what actually happens on the call stack so the "magic" goes away, and then builds the bridge that matters most for interviews: from a recursive solution to a memoised one to a dynamic programming table. Trees, backtracking, divide and conquer and DP all depend on this.

How to Think Recursively: The Three-Question Method

Before writing a recursive function, answer these in plain words:

1. The contract. What does f(input) return? Be precise. "Returns the sum of the elements of the list" is a contract; "processes the list" is not.
2. The base case. For which smallest input is the answer obvious without any further calls?
3. The reduction. Assuming f already works correctly on any smaller input, how do I build the answer for this input?

The third question contains the important mental move. You assume the recursive call is correct, the same way you assume len() or Math.max() is correct without reading its source. This is often called the recursive leap of faith, and it's justified by induction: if the base case is right and each step is right given smaller inputs, the whole function is right.

Example: sum of a list

• Contract: total(nums) returns the sum of all numbers in nums.
• Base case: the empty list sums to 0.
• Reduction: the sum is the first element plus the sum of the rest, and total(rest) gives me the sum of the rest.

def total(nums, i=0):
    """Sum of nums[i:]."""
    if i == len(nums):          # base case: nothing left
        return 0
    return nums[i] + total(nums, i + 1)

static int total(int[] nums, int i) {
    if (i == nums.length) return 0;
    return nums[i] + total(nums, i + 1);
}

Passing an index instead of slicing (nums[1:]) matters. A slice copies the list, so slicing at every level turns an O(n) function into O(n²) time and space. Interviewers notice this.

Example: Tower of Hanoi, where tracing truly fails

Move n disks from peg A to peg C using B, never putting a larger disk on a smaller one. Trying to trace this for n = 5 is miserable. Using the three questions, it takes three lines:

• Contract: hanoi(n, src, dst, via) prints the moves that transfer the top n disks from src to dst.
• Base case: n = 0, nothing to move.
• Reduction: move the top n−1 disks out of the way to via (trust the call), move the biggest disk to dst, then move the n−1 disks from via onto it (trust the call again).

def hanoi(n, src, dst, via):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst)
    print(f"move disk {n} from {src} to {dst}")
    hanoi(n - 1, via, dst, src)

The number of moves satisfies M(n) = 2·M(n−1) + 1 with M(0) = 0, which gives M(n) = 2ⁿ − 1. You never had to picture a single intermediate state of the pegs. That's the method working.

What Really Happens on the Call Stack

The leap of faith is a thinking tool; the machine does something very concrete. Every function call pushes a stack frame holding its parameters, local variables and the address to return to. The frame is popped when the function returns. Recursion is just a function whose frames happen to belong to the same function.

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

Two phases are visible. On the way down, each call is suspended mid-expression, waiting. On the way up, each frame finishes its multiplication with the value returned from below. Code placed before the recursive call runs on the way down; code after it runs on the way up. Knowing which phase you're in explains, for example, why pre-order and post-order tree traversals print in different orders with the same structure.

Stack depth limits by language

This is why "space complexity" for recursive code always includes the recursion depth. A recursive DFS on a balanced tree uses O(log n) stack; on a tree that's degenerated into a linked list it uses O(n). If an interviewer asks about a 10⁶-node skewed tree, they want to hear "recursion could overflow; I'd use an explicit stack".

Getting Base Cases Right

Most recursion bugs live in the base case. A few rules catch nearly all of them:

• Choose the smallest valid input, not the smallest interesting one. For lists, that's empty, not length 1. For trees, it's null, not a leaf. Handling the empty case usually makes the leaf case fall out for free.
• Make sure every recursive call moves toward a base case. f(n) calling f(n // 2) reaches 0; f(n) calling f(n - 2) skips 0 when n is odd, so check for n <= 0 or n < 2 instead of n == 0.
• Handle every branch of the reduction. If you recurse on n − 1 and n − 2, you need base cases for both 0 and 1.
• Return the identity for the combining operation. Sum of nothing is 0, product of nothing is 1, max of nothing is −∞, the count of ways to do nothing is 1.

That last rule is subtle and comes up constantly in DP. "How many ways to climb 0 stairs?" is 1 (the empty sequence of steps), not 0. Getting it wrong shifts every answer.

Example: maximum depth of a binary tree

def maxDepth(root):
    if root is None:                # empty tree has depth 0
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Because the base case is null, there's no special handling for leaves or nodes with one child. Compare that with a version whose base case is "leaf returns 1": it needs extra checks for one-child nodes and crashes on an empty tree. Most of the problems in binary tree interview problems follow this null-base-case shape.

Five Shapes of Recursive Functions

Most interview recursion fits one of five shapes. Recognising the shape tells you the complexity before you write any code.

1. Linear recursion: one call, input shrinks by one

Sum of a list, factorial, reversing a linked list. Depth n, O(n) time if each step is O(1).

def reverseList(head):
    if head is None or head.next is None:
        return head                    # empty or single node: already reversed
    new_head = reverseList(head.next)  # trust: rest is reversed, returns its head
    head.next.next = head              # old next node now points back at us
    head.next = None
    return new_head

Applying the method: the contract is "reverse the list starting at head and return the new head". After the recursive call, head.next is the tail of the reversed rest, so we hang head after it. The O(n) stack depth is why the iterative version is usually preferred in production; more variants are in the linked list problems guide.

2. Halving recursion: one call, input halves

Binary search and fast exponentiation. Depth log n.

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    if n == 0:
        return 1.0
    half = my_pow(x, n // 2)           # computed ONCE, then reused
    return half * half if n % 2 == 0 else half * half * x

public double myPow(double x, int n) {
    long N = n;                       // -Integer.MIN_VALUE overflows int
    if (N < 0) { x = 1 / x; N = -N; }
    return pow(x, N);
}

private double pow(double x, long n) {
    if (n == 0) return 1.0;
    double half = pow(x, n / 2);
    return (n % 2 == 0) ? half * half : half * half * x;
}

If you write my_pow(x, n // 2) * my_pow(x, n // 2) instead of storing half, the function makes two calls per level and becomes O(n) again. A one-line difference turns a log-depth chain into a full binary tree, which leads directly into recursion trees below.

3. Divide and conquer: two calls on halves, then combine

Merge sort is the canonical example: sort each half, merge in O(n). Depth log n, O(n) work per level, O(n log n) total. The code and the combine step are in sorting algorithms compared.

4. Tree recursion: one call per child

Any function on a binary tree that visits both subtrees. Each node is visited once, so O(n) time, O(height) space.

5. Branching (choice) recursion: one call per choice

At each step you choose among options and recurse for each: include or exclude an element, pick the next character, place a queen. The number of calls grows exponentially, and this is the foundation of backtracking.

def subsets(nums):
    res = []

    def go(i, current):
        if i == len(nums):              # decided every element
            res.append(current[:])      # copy, since current keeps changing
            return
        current.append(nums[i])         # choice 1: include nums[i]
        go(i + 1, current)
        current.pop()                   # undo the choice
        go(i + 1, current)              # choice 2: exclude nums[i]

    go(0, [])
    return res

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    go(nums, 0, new ArrayList<>(), res);
    return res;
}

private void go(int[] nums, int i, List<Integer> cur, List<List<Integer>> res) {
    if (i == nums.length) {
        res.add(new ArrayList<>(cur));
        return;
    }
    cur.add(nums[i]);
    go(nums, i + 1, cur, res);
    cur.remove(cur.size() - 1);
    go(nums, i + 1, cur, res);
}

2ⁿ leaves, each copying up to n elements: O(n·2ⁿ) time. The "append, recurse, pop" rhythm is the core of every problem in the backtracking guide.

Recursion Trees: Seeing the Complexity

A recursion tree draws each call as a node and its recursive calls as children. Two numbers give you the time complexity: how many nodes there are, and how much work each node does outside its recursive calls.

Naive Fibonacci is the standard example:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The call count C(n) satisfies C(n) = 1 + C(n−1) + C(n−2), which works out to C(n) = 2·F(n+1) − 1, where F is the Fibonacci sequence itself. For n = 40 that's 2 × 165,580,141 − 1, about 331 million calls, to compute a number you could get with 40 additions. The tree grows roughly like 1.618ⁿ, which is commonly written as the looser bound O(2ⁿ).

For the divide-and-conquer rows, the Master Theorem gives these answers mechanically; it's worked through in time and space complexity explained. For interviews, drawing two or three levels of the tree and summing per level is usually faster and more convincing than citing the theorem.

Tail Recursion and Why It Rarely Saves You

A call is a tail call if it's the very last thing the function does, with nothing left to compute after it returns. return n * fact(n − 1) is not a tail call, because the multiplication happens after the call returns. Rewriting with an accumulator makes it one:

def fact_tail(n, acc=1):
    if n <= 1:
        return acc
    return fact_tail(n - 1, acc * n)    # nothing left to do after this call

In a language that performs tail call elimination, such as Scheme, the runtime reuses the current frame instead of pushing a new one, so a tail-recursive function runs in O(1) stack like a loop. The catch for interviews:

• CPython does not eliminate tail calls. fact_tail(5000) still raises RecursionError.
• The standard JVM does not either, so Java behaves the same way. (Kotlin and Scala offer opt-in tailrec/@tailrec that compiles to a loop.)
• C and C++ compilers often optimise tail calls at -O2, but the language doesn't guarantee it and debug builds won't.

So the real value of tail recursion is that it shows the function is trivially convertible to a loop. The accumulator becomes a variable, the parameter update becomes the loop step:

def fact_loop(n):
    acc = 1
    while n > 1:
        acc *= n
        n -= 1
    return acc

From Recursion to Dynamic Programming

This is the most valuable bridge in interview prep. A huge share of DP problems are solved, in practice, by writing the recursive solution first and then mechanically optimising it. Here are the steps, on Fibonacci first, then on a 2D problem.

Step 1: notice repeated subproblems

In the fib(5) tree above, fib(3) appears twice and fib(2) three times. If a recursive function depends only on its arguments (no global state changing between calls) and the same arguments show up repeatedly, you have overlapping subproblems.

Step 2: memoise

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

private final Map<Integer, Long> memo = new HashMap<>();

long fib(int n) {
    if (n < 2) return n;
    Long cached = memo.get(n);
    if (cached != null) return cached;
    long val = fib(n - 1) + fib(n - 2);
    memo.put(n, val);
    return val;
}

Each distinct n is now computed once: n + 1 states, O(1) work each, O(n) time. Note that recursion depth is still O(n), so fib(10⁵) memoised will still overflow the stack in Python.

Step 3: tabulate (bottom-up)

Fill the table in an order where each entry's dependencies are already computed. For fib, that's increasing n:

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Step 4: shrink the space

dp[i] only reads the previous two entries, so keep two variables: a, b = b, a + b. O(n) time, O(1) space, no recursion. Same pattern solves Climbing Stairs and House Robber.

The same four steps on a grid: Unique Paths (LeetCode 62)

Count paths from the top-left to the bottom-right of an m×n grid moving only right or down.

• Contract: paths(r, c) = number of ways to reach cell (r, c) from (0, 0).
• Base case: any cell in row 0 or column 0 has exactly one path.
• Reduction: you arrive at (r, c) from above or from the left, so paths(r, c) = paths(r−1, c) + paths(r, c−1).

from functools import lru_cache

def unique_paths_memo(m, n):
    @lru_cache(maxsize=None)
    def paths(r, c):
        if r == 0 or c == 0:
            return 1
        return paths(r - 1, c) + paths(r, c - 1)
    return paths(m - 1, n - 1)

def unique_paths_table(m, n):
    row = [1] * n                     # row 0: all ones
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]      # above (old row[c]) + left (new row[c-1])
    return row[-1]

Without memo, the recursion is exponential. With memo, it's m·n states and O(m·n) time. The table version also drops to O(n) space by reusing one row. Once this conversion feels routine, the problems in dynamic programming interview questions become a matter of finding the right state, which is the actual hard part.

Converting Recursion to Iteration with an Explicit Stack

Any recursion can be made iterative by managing the stack yourself. You'd do this when depth could overflow the call stack, or when an interviewer asks for it as a follow-up (very common for tree traversals).

def inorder(root):
    res, stack = [], []
    node = root
    while node or stack:
        while node:                 # simulate the "go left" recursive calls
            stack.append(node)
            node = node.left
        node = stack.pop()          # simulate returning from the left call
        res.append(node.val)        # the work between the two calls
        node = node.right           # simulate the "go right" call
    return res

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        res.add(node.val);
        node = node.right;
    }
    return res;
}

Read the comments: each line corresponds to a point in the recursive version. That correspondence is the general recipe. The stack holds the frames that would have been suspended, and the loop body does what the function would do at the point of resumption.

Recursion in Coding Interviews: What Gets Evaluated

Recursion rarely appears as "write a recursive function" by itself. It shows up inside tree, graph, backtracking and DP questions, and the evaluation focuses on a few things:

• A clear contract. Say out loud what the function returns. "dfs(node) returns the height of the subtree rooted at node" lets the interviewer check your logic as you write it.
• Correct base cases. Null nodes, empty strings, index equal to length, negative targets.
• Honest complexity. Time from the recursion tree, space including recursion depth.
• Recognising repeated work. If you write an exponential recursion, the next question is "can we do better?", and the answer is usually memoisation.

A practice ladder

1. Linear: sum of digits, reverse a string, palindrome check, power of two, reverse linked list (206).
2. Halving: Pow(x, n) (50), binary search written recursively.
3. Trees: max depth (104), same tree (100), invert tree (226), path sum (112), diameter (543).
4. Branching: subsets (78), permutations (46), letter combinations of a phone number (17), generate parentheses (22).
5. Recursion to DP: climbing stairs (70), unique paths (62), house robber (198), coin change (322).

For each, write the three answers (contract, base case, reduction) as comments before writing code. It feels slow for a week. After that it becomes how you think, and recursion stops feeling like magic.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.