Recursion ladder coding interview walkthrough, from base case to nested lists

In this article

1. Before you start
2. Why interviewers ask this
3. Recursion from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one rung of the coding interview questions path. If you also want the question-by-question Python material, the Python interview questions page covers it.

Why interviewers ask this

Recursion questions separate candidates who can state a rule from candidates who can show it ends. Candidates report recursion-flavoured prompts such as power of a number, flattening nested data, deleting nodes from a binary tree and the Nested List Weight Sum family (reported by candidates, not a statement about any company's practice).

A weak answer writes a function that calls itself and hopes. A strong answer names the base case first, says what shrinks on every call, and states the cost in calls and in stack depth. A Staff-level answer adds what breaks: a depth limit, repeated work in branching calls, and the option to rewrite the recursion with an explicit stack. The ladder below is built so each of those points is one rung.

Recursion from first principles

Recursion

Recursion is a way of solving a problem in which a function calls itself on a smaller version of the same problem, and combines the smaller answer into its own, until a case small enough to answer directly is reached.

Base case

A base case is the input of a recursive function that is answered directly, without a further self-call, so the chain of calls ends there. Every recursive function needs at least one, and every self-call must move the input toward it.

Recursion ladder

A recursion ladder is a teaching order of four problems that each add one idea (base case, faster shrinking, caching, nested data), so a beginner can climb without a gap. It is this page's own framing, not an industry standard.

In plain words

Think of a set of nested boxes. To count the boxes, open the outer one, and if the next thing inside is another box, ask the same question of that smaller box. You stop at an empty box, because there is nothing left to open. The analogy breaks in one place: a computer does not forget the outer boxes while it works on the inner one. It keeps each unfinished call on the call stack, which is the area of memory that holds one frame per call that has started and not yet returned.

In one precise sentence, a recursive function has a base case that returns directly and a step that calls the same function on an input closer to that base case (Princeton, Sedgewick and Wayne, accessed 2026-10-26).

Rung one is a base case plus one self-call that shrinks the input. Rung two shrinks the input faster, so the depth of calls falls. Rung three has branching calls, and a cache stops repeated work. Rung four walks nested data and carries the depth as an argument.

Step 1: A base case and one self-call that shrinks the input

Start with the smallest useful example: compute x to the power n by repeated multiplication. The base case is n equal to 0, which returns 1. Every other call returns x times the answer for n minus 1.

def power(x, n):
    if n == 0:          # base case: answered directly
        return 1
    return x * power(x, n - 1)   # the input n moves toward the base case

Input: x and n. Output: one number. Each call hands a smaller n to the next, so the chain must end. For x of 2 and n of 30, this makes 31 calls and the result is 1,073,741,824.¹ The depth of the stack equals the number of calls here, 31 frames, because each call waits for the next. You now know the whole skeleton: a stopping rule and a shrinking step. Without the stopping rule the function never ends; without the shrink it never gets there. Interviewers often also expect a negative n to be handled: return 1 divided by the power for minus n, before the base case is reached.

Step 2: Shrink the input faster and the depth falls

Rung two asks the interviewer's usual follow-up: can you do better than n calls? Yes, by halving n instead of subtracting one. If n is even, x to the n is the square of x to the n over 2. If n is odd, multiply one more x on.

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)      # one call on half the input
    return half * half if n % 2 == 0 else half * half * x

Input: x and n. Output: one number. The key detail is that the code calls power once and reuses half; writing power(x, n // 2) * power(x, n // 2) would call twice and give back the savings. For n of 30 the chain is 30, 15, 7, 3, 1, 0, which is 6 calls instead of 31, with the same result.¹ The cost now grows with the logarithm of n, not with n itself. This is also what keeps recursion inside the language's depth cap, which Python documents as a recursion limit on the interpreter stack (Python docs, sys, accessed 2026-10-26).

Step 3: Branching calls repeat work until a cache removes it

Rung three has a function that calls itself twice, the classic case being Fibonacci: the base cases are 0 and 1, and every other value is the sum of the previous two.

from functools import cache

def fib(n):
    if n < 2:                      # base cases
        return n
    return fib(n - 1) + fib(n - 2) # two self-calls: the calls branch

@cache                             # memoization: each n is computed once
def fib_fast(n):
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

Without the cache, fib(10) makes 177 calls, fib(20) makes 21,891 and fib(30) makes 2,692,537, because the same smaller values are recomputed in many branches.¹ With the cache, fib_fast(30) runs its body 31 times, once per value of n from 0 to 30.¹ The standard library provides this as cache and lru_cache, and the arguments must be hashable (Python docs, functools, accessed 2026-10-26). The answer for n of 30 is 832,040, and naive recursion makes about 3.2 times that many calls, because the call count follows the same growth as the answer; the cached version needs only 31 body runs.¹

Step 4: Nested data needs the depth carried as an argument

Rung four is the shape behind the Nested List Weight Sum problems on LeetCode: a list whose items are integers or further lists. The base case is an item that is an integer; the recursive case is an item that is a list, handled by calling the function on it with the depth increased by one.

def depth_sum(items, depth=1):
    total = 0
    for item in items:
        if isinstance(item, int):          # base case: a plain integer
            total += item * depth
        else:                              # a list: recurse one level deeper
            total += depth_sum(item, depth + 1)
    return total

Input: a nested list and the current depth. Output: the sum of each integer times its depth. The input does not shrink by a number here; it shrinks by structure, because each call receives a strictly smaller part of the data. The same pattern, one call per child, handles trees, which is why it reappears in the lowest common ancestor of a binary tree problem.

1 · Base case2 · Faster shrink3 · Cache4 · Nested dataReplay

Step-by-step description

1. A stopping rule and one shrinking self-call.
2. Halving the input cuts the call depth.
3. Branching calls reuse stored answers.
4. Recurse on each inner part, carry depth.

• Rung one is a base case plus one self-call that shrinks the input.
• Rung two shrinks the input faster, so the depth of calls falls.
• Rung three has branching calls, and a cache stops repeated work.
• Rung four walks nested data and carries the depth as an argument.

Worked example

Take the nested list [[1,1],2,[1,1]] (illustrative input). The integer 2 sits at depth 1 and the four 1s sit at depth 2. The depth-weighted sum is four 1s times 2, plus 2 times 1, which is 10.¹

For the inverse-depth version, the weight of an integer is the maximum depth minus its depth plus 1. The maximum depth here is 2, so each 1 has weight 1 and the 2 has weight 2. The sum is four 1s times 1, plus 2 times 2, which is 8.¹ It needs two passes: one recursive function finds the maximum depth, and a second applies the weights.

def max_depth(items):
    deepest = 1
    for item in items:
        if not isinstance(item, int):
            deepest = max(deepest, 1 + max_depth(item))
    return deepest

def inverse_depth_sum(items, depth=1, top=None):
    top = max_depth(items) if top is None else top
    total = 0
    for item in items:
        if isinstance(item, int):
            total += item * (top - depth + 1)
        else:
            total += inverse_depth_sum(item, depth + 1, top)
    return total

The count for naive Fibonacci follows its own recurrence: the calls for n are one plus the calls for n minus 1 plus the calls for n minus 2.¹

Text description of the diagram

• Naive recursion makes 177 calls for n of 10 and 2,692,537 calls for n of 30.
• A cache cuts the 30 case to 31 calls.

Naive recursion makes 177 calls for n of 10 and 2,692,537 calls for n of 30, and a cache cuts the 30 case to 31 calls.¹

Trade-offs and edge cases

Recursion is not slower in the asymptotic sense. The costs are call-stack overhead and a depth limit, so a function that recurses once per element of a long list can hit Python's recursion limit even when the algorithm is correct (Python docs, sys, accessed 2026-10-26). The same page warns that raising the limit too far can crash the interpreter, so raising it is a patch, not a design.

Tail-call elimination, which would reuse a frame when the last action is the self-call, is not done by the standard Python interpreter, and its designer explained why (Guido van Rossum, accessed 2026-10-26). Rewriting a tail-recursive function as a loop is the usual fix in Python.

Any recursion can be rewritten with an explicit stack that you manage yourself. That moves the depth from the call stack into a list you control, using an explicit stack (the structure behind the monotonic stack technique). Graph problems make the edge case sharper: recursion on a graph with a cycle never reaches a base case unless you track visited nodes, as in detecting a cycle in a directed graph and topological sort.

Text description of the diagram

• Each rung adds one idea to the last, and each prevents one failure.
• The failures are endless calls, a deep stack, repeated work and wrong weights.

Each rung adds one idea to the last, and each prevents one failure: endless calls, a deep stack, repeated work and wrong weights. The sibling greedy ladder walkthrough uses the same one-idea-per-rung structure for a different family of problems.

How to answer it in an interview

The spoken structure: name the base case, say what shrinks, state the cost in calls and in depth, then name the one failure you guard against.

Common mistakes

• "I will just call the function on the rest of the problem." (wrong) There is no stopping rule. (right) "The base case is an integer, and every call receives a strictly smaller part of the data."
• "Fibonacci recursion is linear because it is only a sum." (wrong) Two self-calls branch, and the calls grow exponentially without a cache. (right) "Naive recursion repeats subproblems; memoization makes each one run once."
• "Python will optimise my tail call." (wrong) The standard interpreter does not eliminate tail calls. (right) "I would write this as a loop, or an explicit stack, if the depth can be large."
• "Recursion is always worse than iteration." (wrong) The costs are stack overhead and a depth limit, not a different time order. (right) "Same time order; I pick recursion when the data is itself nested."
• "I halved n, so I can call twice." (wrong) Two calls on half the input brings back the cost you removed. (right) "Call once and reuse the result."

Follow-up questions

How do you turn a recursive solution into an iterative one?

Replace the call stack with a list you manage: push the starting input, then repeatedly pop an item, handle it, and push the smaller pieces it would have recursed on. For nested lists, push each inner list together with its depth. The result matches the recursion and avoids the depth limit.

What happens when Python hits the recursion limit?

The interpreter stops the chain of calls and raises a RecursionError rather than growing the stack without bound; the limit is the maximum depth of the interpreter stack. Raise it only with care, because a limit set too high can crash the interpreter. See the Python interview questions page for neighbouring language questions.

Does Python optimise tail recursion?

No. The standard interpreter does not eliminate tail calls, so a tail-recursive function still uses one frame per call; convert it to a loop when the depth could be large.

What is the time complexity of recursive Fibonacci?

Naive recursion is exponential in n: O(2 to the n) loosely, and Θ(φⁿ) tightly, where φ is the golden ratio, about 1.618.¹ The call counts of 177, 21,891 and 2,692,537 for n of 10, 20 and 30 show it.¹ With memoization it runs once per value of n, so the time grows linearly with n, though it still recurses n deep, so fib_fast of a large n hits the recursion limit.

How do you solve Nested List Weight Sum with inverse depth?

Run one recursive pass to find the maximum depth, then a second pass that weights each integer by the maximum depth minus its depth plus 1. For [[1,1],2,[1,1]] the result is 8.¹ A Staff-level alternative is one pass, level by level: keep a running sum of the integers seen so far and add it to the total at each level.

How do you flatten nested JSON in Python?

The base case is a primitive value, which is written out under its accumulated key path. A dict recurses on each key with the path extended as "path.key", and a list recurses on each index with "path.0" and so on. Here JSON (JavaScript Object Notation) is the nested data; the cost is one call per value, and the stack depth equals the nesting depth.

Sources

1. sys: system-specific parameters and functions (recursion limit) — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026
2. functools: lru_cache and cache — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026
3. Recursion, Computer Science: An Interdisciplinary Approach — Princeton University (Sedgewick and Wayne, accessed 2026-10-26), 26 Oct 2026
4. Tail Recursion Elimination — Guido van Rossum, Neopythonic (accessed 2026-10-26), 22 Apr 2009
5. Nested List Weight Sum II (problem 364) — LeetCode (accessed 2026-10-26), 26 Oct 2026