Recursion

For interviews, the important decisions are what each recursive call returns, which calculations can be reused, and how much work and memory the calls require.

The core exercises cover nested data, fast power, and memoization. Specialized variations remain on the optional problem pages.

1. Define What Each Call Returns

Give the helper a precise job before writing its recursive calls. For Nested Array Sum, total(item) returns the sum of all integers inside that item, whether it is an integer or a nested array:

def total(item):
    if isinstance(item, int):
        return item
    answer = 0
    for child in item:
        answer += total(child)
    return answer

For [1, [2, 3], []], the child calls return 1, 5, and 0, so the parent returns 6. An integer is a base case; an empty array returns the initial sum of zero. Each recursive call descends into a contained item, so finite, acyclic input terminates. This visits N integers/array containers once: O(N) time and O(h) stack space, where h is the maximum number of simultaneously active calls.

Before coding, verify three things: smallest valid inputs produce the right answer; recursive calls make progress; the parent combines and returns their results. The combination depends on the question: sum child values for a total, take one plus the maximum child height for a tree height, or append results for an output sequence.

Return enough information for the parent

A helper sometimes needs to return more than the final answer. In Laminal Arrays, the array length is a power of two. The allowed ranges are the whole array, its exact halves, their halves, and single elements. The parent needs both the best allowed sum inside each half and each half's total:

total = left_total + right_total
best = max(left_best, right_best, total)
return (best, total)

A singleton returns (value, value). Returning the total avoids rescanning each range: constant combining work at 2n−1 calls gives O(n) time and O(log n) stack, instead of O(n log n) time from repeated summation. The empty range is not allowed, so initializing the answer to zero would fail on all-negative input.

For a helper that appends to shared output, the contract is different: run the helper, then return the buffer from the wrapper. In Python, return helper(...) returns None if that helper only appends; the wrapper should return the buffer instead. Create the buffer inside each public invocation so separate calls do not share results.

2. Avoid Copies and Repeated Calculations

Pass indices instead of copying suffixes

In Python, repeatedly passing arr[1:] copies n−1, n−2, … elements. An otherwise linear recursive sum becomes O(n²) time and O(n²) peak auxiliary space while those copies remain in active calls. Pass the original array plus an index, or a half-open range [left, right), to avoid that work. Go subslices share storage, so this cost depends on the language.

For output strings, append pieces to one buffer and join once instead of concatenating growing strings at every return. Robot Instructions applies both changes. An output of length L still requires Ω(L) time to produce; eliminating copies cannot make exponential output cheap.

Compute the half-power once

For nonnegative n, let half = x^(n // 2). Squaring it produces x^n when n is even; an odd n needs one extra factor of x:

def power(x, n):  # n >= 0
    if n == 0:
        return 1
    half = power(x, n // 2)
    squared = half * half
    return squared if n % 2 == 0 else squared * x

Saving half gives O(log n) time and stack space for n ≥ 2, with constant work for n=0 or 1. Calling the same half-power twice instead gives O(n) work. Pow(x, n) adds negative exponents; negating the minimum signed integer can overflow.

For Powers Mod M, reduce the base and intermediate products modulo m. Fixed-width multiplication can overflow before % m; the problem page includes a Go implementation that preserves the full product.

Cache answers reached through different calls

For Fibonacci, F(0)=0, F(1)=1, and F(n)=F(n−1)+F(n−2). Computing F(5) asks for F(4) and F(3), but F(4) also asks for F(3). A local variable in the F(5) call does not prevent that repeated calculation; a shared cache does.

Check the cache before expanding a state. If the key is absent, compute the answer from smaller states, store it, and return it. There are only n+1 distinct Fibonacci inputs, each requiring constant combining work: O(n) time and O(n) cache plus stack space. An iterative version retains only the previous two values and uses O(1) auxiliary space. Compare all three in Fibonacci Number.

The cache key must determine the answer. A helper depending on both position and remaining budget needs both in its key. Keep input-dependent caches local to the invocation, and check key presence: a cached zero is still an answer. Cache returned answers; skipping a call whose job is to append output would skip its required effect.

3. Analyze Time and Stack Space Separately

For time, count all calls and the non-recursive work inside each. For space, count calls active together plus their live buffers and caches. The complete call tree is an analysis tool; ordinary recursion only keeps the active call chain on its stack.

Two recursive calls do not imply exponential time. Merge sort splits into disjoint halves; naive Fibonacci repeats overlapping work. For unfamiliar branching, the BAD method gives a quick upper bound: at most b children per call, d levels, and O(A) extra work per call gives O(b^d · A) for b ≥ 2. With one child per call, use O(d · A). This can be loose; summing work per level gives the tighter merge-sort bound above. These estimates assume constant-cost arithmetic; large integers add bit-length costs.

Memoization reduces repeated computation, not the deepest call chain: Fibonacci can still descend through n, n−1, …, 1. Recursive Reverse String also uses O(n) stack despite modifying the original array. For very deep inputs, use iteration or an explicit stack; the latter still consumes memory. Do not assume tail-call optimization.

4. Key Takeaways

• Return the information the parent needs. In Laminal Arrays, returning both the best sum and total sum avoids scanning each half again.
• Avoid copying the remaining input at every call. For recursive summation, passing an index instead of Python's arr[1:] avoids O(n²) slicing work.
• Compute repeated answers once. Fast power saves one half-power in a variable; Fibonacci needs a cache shared across calls to reuse F(3), F(4), and other repeated inputs.
• Include the call stack in space complexity. Memoized Fibonacci takes O(n) time, but still needs O(n) memory. Recursive in-place reversal also needs O(n) stack space.

Where to Apply These Ideas