What Is the Complexity of Recursive Calls?

Naive recursion recomputes the same subproblems over and over. Computing fib of twenty-five calls fib of twenty-three twice, and each of those calls its own smaller values again, so the number of calls grows exponentially in the input. Memoisation computes each value once and stores it, so the total work becomes linear in the size of the input.

def fib_naive(n, counter):
    counter[0] += 1
    if n < 2:
        return n
    return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)

def fib_memo(n, memo):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

counter = [0]
print(fib_naive(25, counter), counter[0])
print(fib_memo(25, {}))

Both return 75025, but the naive version needed 242785 calls while the memoised one needed about twenty-six. Doubling the input from twenty-five to thirty would multiply the naive call count by roughly a factor of ten, while the memoised version would add only a handful of calls. That difference is the whole point.

Formally, the naive version satisfies the recurrence T of n equals T of n minus one plus T of n minus two plus a constant, which solves to O of two to the n. The memoised version satisfies T of n equals T of n minus one plus a constant, because the second branch hits the cache immediately, which solves to O of n.

The trade-off to mention is the space. Memoisation adds a cache of size n, so it turns exponential time into linear time at the cost of linear memory and a hash lookup per call. The right structure to reach for is not recursion over raw integers but an explicit bottom-up table or an iterative loop, which keeps the linear time and drops the recursion depth, because a naive recursive Fibonacci with a large n will also blow the call stack.

Write the recurrence down first, in terms of the cost of the recursive calls plus the cost of the work you do in the body. For a function that calls itself twice on n minus one, the recurrence is T of n equals two times T of n minus one plus a constant. Then you look at the shape of that recurrence and recognise a pattern.

Three shapes cover most interview cases. If the function makes one call on n minus one, the recurrence unfolds into a chain of n calls and the work is linear. If it makes two calls on n minus one, each level doubles the number of calls and the work is exponential. If it makes two calls on roughly n divided by two, the work at each level is proportional to n and there are logarithmically many levels, giving O of n log n.

The master theorem is the formal shortcut for the last shape. You identify the cost of the recursive subproblems, the factor by which the problem shrinks, and the cost of the work at each node. For the merge sort recurrence, T of n equals two times T of n divided by two plus n, the answer is linear times logarithmic, because the per-level work and the number of levels exactly balance.

Two practical notes. First, check the base case, since a function that recurses twice stays exponential no matter where the base case sits. Second, remember that space complexity has its own recurrence: the naive Fibonacci needs O of n stack space even though it takes exponential time, because the call stack depth grows linearly even though the total call count is exponential. Interviewers like that contrast.