What Do Recursion Questions Test?

Three things, and none of them is the syntax. First, can you find the base case, the smallest input where the answer is known without further work. Second, can you shrink the problem so that each recursive call is strictly smaller, which is what guarantees termination. Third, can you keep the state that has to travel with the call, whether that is an accumulator, a path, or a set of used items.

def flatten(nested):
    output = []
    for item in nested:
        if isinstance(item, list):
            output.extend(flatten(item))
        else:
            output.append(item)
    return output


print(flatten([1, [2, [3, [4]]], 5]))

The output is 1, 2, 3, 4, 5. The function flattens an arbitrarily nested list, and it works because each nested list is strictly smaller than the list that contains it, so the recursion is guaranteed to bottom out.

The mechanism is that a recursive call does two things: it frames a smaller version of the same question, and it combines the answers. The first part is where the base case matters, because without it the recursion never stops. The second part is where the interesting work happens, and that is usually a single line such as an append, a sum or a max.

The trade-off to name is that recursion costs more than a loop in constant factors and it puts the call stack depth in your complexity analysis. A recursion of depth n needs O of n stack space, so a naive recursive solution to a problem with n of the order of a hundred thousand will overflow the stack. Interviewers are watching for whether you notice the exponential trap as well, since a naive recursive solution that recomputes the same subproblems can be far worse than the loop version it replaces.

The base case is the empty list, which sums to zero. Every other list sums to its first element plus the sum of the rest, which is a strictly smaller list.

def total(values):
    if not values:
        return 0
    return values[0] + total(values[1:])


print(total([1, 2, 3, 4]))

The output is 10. The call stack builds up through total of four elements, then three, then two, then one, then the empty list, and the results unwind as ten.

The mechanism is the recurrence. The function reduces one element from the list at each level, so the depth of the recursion equals the length of the list. That gives O of n time and, importantly, O of n stack space, which is the part people forget when they quote the complexity of a recursive function.

The trade-off to name is that the slicing creates a new list on every call, so the time is O of n squared even though the arithmetic is linear. That is a subtle and worthwhile observation: the recursion visits n elements but copies them as well. A version that takes an index instead of a slice avoids the copying and is genuinely linear, at the cost of a slightly less elegant signature. Mentioning that distinction is exactly the kind of detail that shows you understand what the code is doing rather than reciting a pattern.

Memoise the results of the recursive calls. If the same subproblem is computed more than once, store the answer the first time and reuse it afterwards, so each distinct subproblem is solved exactly once.

def count_paths(rows, cols):
    memo = {}

    def walk(r, c):
        if r == rows - 1 or c == cols - 1:
            return 1
        key = (r, c)
        if key not in memo:
            memo[key] = walk(r + 1, c) + walk(r, c + 1)
        return memo[key]

    return walk(0, 0)


print(count_paths(3, 3))

The output is 6, the number of ways to walk from the top left to the bottom right of a three by three grid moving only right or down. Without memoisation the same subproblems are recomputed over and over and the cost explodes exponentially with the size of the grid.

The mechanism is that a naive recursive walk on a grid visits each cell many times through different routes. The memo table records the answer for each cell the first time it is computed, so subsequent visits are a dictionary lookup. The number of distinct subproblems is the number of cells, so the work becomes linear in the number of cells rather than exponential in it.

The trade-off to name is space for time. The memo table stores one entry per subproblem, so the extra space is proportional to the number of states. That is normally a good trade, but it stops being one when the number of states is larger than the input itself, for example when the key is a whole path rather than a position. In that case a bottom-up table over a carefully chosen state space is usually better, because it computes every state once and in a predictable order, and it can be freed as soon as the answer is known.