Skip to content
Data Structures & Algorithms

Recursion interview questions and answers

53 questions, 39 with code. About 4 h 36 min to read them all.

By TestLab · Updated

Plan for an interview
53 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

How does dynamic programming differ from recursion and memoization?

Dynamic programming (DP) is an algorithmic strategy for problems with overlapping subproblems and optimal substructure. Recursion is a control-flow technique in which a function calls itself, while memoization caches previously computed results and can be used to implement top-down DP.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Differences

Approach How it works Typical use
Plain recursion A function calls itself until it reaches a base case Tree traversal, factorials, backtracking
Memoized recursion Recursion is combined with a cache so repeated states are computed once Top-down DP for problems with overlapping subproblems
Bottom-up DP States are computed iteratively in dependency order DP when recursion depth is large or all states are needed
  • Recursion describes how control flow is organized; it does not imply exponential time.

  • Dynamic programming describes how the algorithm avoids repeated work, usually through either top-down memoization or bottom-up tabulation.

  • Memoization is a caching technique, not a synonym for DP. It can be applied to a recursive function, but a memoized solution is DP only when its states, dependencies, and recurrence form a valid DP decomposition.

  • Bottom-up DP does not use recursion, so it avoids Python’s recursion-depth limit.

How It Works

A DP solution identifies:

  1. State: The information required to solve one subproblem.

  2. Recurrence: How the current state is calculated from smaller states.

  3. Base cases: The states that require no further calculation.

  4. Evaluation order: Whether dependencies are calculated on demand with memoization or iteratively from smaller states.

For Fibonacci, the recurrence is F(n) = F(n - 1) + F(n - 2) for n >= 2, with F(0) = 0 and F(1) = 1.

A memoized evaluation of fibonacci(5) proceeds as follows:

  • fibonacci(5)

  • fibonacci(4)

    • fibonacci(3)

    • fibonacci(2)

      • fibonacci(1) computes 1

      • fibonacci(0) computes 0

    • fibonacci(1) returns the cached 1

    • fibonacci(2) returns the cached 1

  • fibonacci(3) returns the cached 2

Each unfinished recursive call occupies one activation record on the call stack. Python’s default recursion limit is approximately 1,000, and Python has no tail-call optimization, so deeply nested inputs may require bottom-up evaluation or an explicit stack.

To convert recursive memoization to an explicit stack, push each state together with a marker indicating whether it has been expanded. On the first visit, push the marker and its dependencies; when the expanded marker is reached, compute the state from its now-cached dependencies. This avoids the recursion limit, although the memoization cache still requires space.

In Python, functools.cache provides memoization for hashable arguments. The cache key must include every argument that affects the result.

Complexity

For Fibonacci, let n be the input and phi be the golden ratio:

Approach Best time Average time Worst time Auxiliary space
Plain recursion O(phi^n) O(phi^n) O(phi^n) O(n) for the call stack
Memoized recursion O(n) O(n) O(n) O(n) cache plus O(n) stack
Bottom-up DP O(n) O(n) O(n) O(1) for Fibonacci
Explicit-stack memoization O(n) O(n) O(n) O(n) cache plus O(n) stack

These are auxiliary complexities and do not count the input itself. Memoized recursion and bottom-up DP take O(n) time because each Fibonacci state is computed once. Plain recursion takes O(phi^n) because it repeatedly evaluates overlapping states.

For a general top-down DP problem, let R be the number of reachable states, C the maximum number of transitions per state, and d the maximum recursion depth. Under the standard constant-time-average cache lookup assumption, evaluation takes O(R × C) time and at most O(R + d) auxiliary space. The best case is O(1) when the requested state is already a base case. With adversarial hash collisions, a strict dictionary-based worst case can degrade to O(R² × C).

A bottom-up evaluation of N possible states takes O(N × C) time and O(N) auxiliary space in the full-evaluation case; a rolling-state optimization may reduce the space to O(k), where k is the number of retained states.

Common Pitfalls

  • Confusing recursion with DP: Recursion is a mechanism; overlapping subproblems and a well-defined recurrence are what justify DP.

  • Using an incomplete state: Omitting information that affects the answer can produce incorrect cache hits.

  • Caching mutable arguments: Mutating a value after it has been cached can make the cached result incorrect.

  • Ignoring base cases: An incorrect base case can cause infinite recursion or an incorrect result.

  • Exceeding Python’s recursion limit: Use bottom-up DP or an explicit stack for deep inputs.

  • Ignoring problem-specific edge cases: For Fibonacci, n = 0 and n = 1 are base cases, while negative inputs should be rejected.

Interviewers commonly follow up by asking for the DP state and recurrence, a comparison of top-down and bottom-up implementations, or a proof that the recurrence uses optimal substructure.

2

What are common recursion examples in computer science?

Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler input. It is especially common in divide-and-conquer algorithms, tree and graph traversals, backtracking, and dynamic programming.

Read full answer

Applies tolanguage-independent

How It Works

Every useful recursive function has two essential parts:

  • Base case: The condition under which the function returns without making another recursive call.

  • Recursive case: The function performs some work and then calls itself with input that moves toward the base case.

Conceptually, execution follows this pattern:

Solve(problem) → Do work → Solve(smaller problem) → Combine or return result

Each active call occupies a frame in the call stack. The stack is unwound as base cases are reached and results are returned to their callers. Python 3.12 has a default recursion limit of approximately 1,000, inspectable with sys.getrecursionlimit(), and it has no general tail-call optimization.

Common Recursive Problems

Problem Recursive idea Typical use
Factorial Calculate n × factorial(n - 1) Mathematical algorithms
List summation Add one element to the sum of the remaining elements Sequence processing
Fibonacci Add the results for n - 1 and n - 2 Memoization and dynamic programming
Tree traversal Visit a node, then recursively visit its children Trees, XML, and file systems
Tree depth Take one plus the deeper child’s depth Tree analysis
Permutations Choose an element, then recursively arrange the others Backtracking
Flood fill Recolor a cell and recursively visit valid neighbors Grids and image processing
Tower of Hanoi Move n - 1 disks, move the largest, then move n - 1 disks Complexity analysis
Quicksort Partition a sequence and recursively sort each partition Divide and conquer

Memoization is important when recursive calls repeat the same inputs. Naive Fibonacci repeats substantial work, while Python’s functools.cache stores previously computed results.

Call Stack Trace

For factorial, the recurrence is factorial(n) = n × factorial(n - 1) for n > 1; factorial(0) and factorial(1) are the base cases.

  1. factorial(4) calls factorial(3).

  2. factorial(3) calls factorial(2).

  3. factorial(2) calls factorial(1).

  4. factorial(1) reaches the base case and returns 1.

  5. The calls unwind, producing 2, then 6, then 24.

Each call moves toward the base case because the argument decreases by one. The maximum number of simultaneously active calls is the recursion depth.

Complexity and Limits

Auxiliary space includes the recursion stack but excludes the input and any generated output.

Example Best time Average time Worst time Auxiliary space
Factorial O(n) O(n) O(n) O(n) stack
List summation O(n) O(n) O(n) O(n) stack
String reversal O(n) O(n) O(n) O(n) stack and result buffer
Fibonacci without caching O(φⁿ) O(φⁿ) O(φⁿ) O(n) stack
Fibonacci with caching O(n) O(n) O(n) O(n) cache and stack
Tree traversal O(n) O(n) O(n) O(h) stack, where h is tree height
Generate all permutations O(n · n!) O(n · n!) O(n · n!) O(n), excluding generated output
Flood fill O(N) O(N) O(N) O(N) stack
Tower of Hanoi O(2ⁿ) O(2ⁿ) O(2ⁿ) O(n) stack
Quicksort with standard partitioning O(n log n) O(n log n) O(n²) O(log n) average, O(n) worst

Memoization changes repeated Fibonacci subproblems from exponential time to linear time because only O(n) distinct states are computed.

Common Pitfalls and Interview Tips

  • Base case: Always identify it and explain how every recursive call moves toward it.

  • Empty and one-element inputs: These are base cases for many sequence and tree algorithms.

  • Invalid values: Factorial and Fibonacci normally require non-negative integers.

  • Duplicates: Permutation algorithms must avoid generating duplicate arrangements.

  • Already sorted input: Poor pivot selection can make quicksort quadratic.

  • Cycles and disconnected graphs: Use a visited set and start traversals from every unvisited vertex when required.

  • Flood-fill boundaries: Check neighboring coordinates and avoid recoloring cells that already have the target color.

  • Large recursion depth: Rewrite the traversal with an explicit stack. For example, a preorder traversal pops a node, processes it, and pushes its children; postorder can store an additional visited-state flag with each node.

  • Repeated subproblems: Consider memoization with functools.cache.

  • Complexity analysis: Include stack depth in auxiliary-space analysis.

3

How do backtracking and recursion differ in algorithms?

Recursion is a control-flow technique in which a function solves a problem by calling itself with smaller or simpler inputs. Backtracking is an algorithmic strategy that explores possible choices, recursively or iteratively, and abandons branches that cannot lead to a valid solution.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

Aspect Recursion Backtracking
Purpose Reuse a function to solve smaller instances of the same problem Search a space of possible decisions
State changes May or may not modify state Often modifies state temporarily and restores it when a branch fails
Termination Stops when the base case is reached Ends a branch when a solution is found, no choices remain, or pruning rejects it
Relationship A programming technique An algorithmic strategy commonly implemented with recursion
Typical examples Factorial, tree traversal, recursive divide-and-conquer Permutations, subsets, Sudoku, N-Queens, simple-path enumeration

A recursive function does not necessarily perform backtracking. Calculating factorial follows one recursive path, while generating permutations explores many paths and abandons invalid or unwanted branches.

How Backtracking Uses Recursion

A typical backtracking algorithm maintains:

  • Current path or partial solution: The choices selected so far.

  • Remaining choices: Values or moves that may still be selected.

  • Validity check: Determines whether the current partial solution can still succeed.

  • Base case: Records the solution when all required choices have been made.

  • Recursive case: Selects another choice, explores it, and then restores the previous state when necessary.

For permutations of [1, 2], the exploration can be represented as a nested trace:

  • Choose 1.

  • Choose 2.

    • Record [1, 2].

  • Abandon the branch containing 2.

  • Abandon the branch containing 1.

  • Choose 2.

  • Choose 1.

    • Record [2, 1].

  • Abandon the branch containing 1.

  • Abandon the branch containing 2.

In mutable-state implementations, the abandonment operations restore the earlier state. Backtracking can also use copied or immutable state, so an explicit undo operation is not required in every design.

Call Stack and Iterative Conversion

For factorial(4), the call stack grows until the base case:

  • factorial(4)

  • factorial(3)

    • factorial(2)

    • factorial(1) — base case

Each recursive call moves closer to the base case. Python has no tail-call optimization, and its default recursion limit is approximately 1,000, as reported by sys.getrecursionlimit(). Deep recursive workloads may therefore require a carefully increased limit or an explicit stack.

To convert recursion to iteration:

  • Replace each pending function call with a stack frame containing its remaining work.

  • Pop a frame and process it.

  • For a base case, record the result.

  • For a recursive case, push child frames in the required order.

For backtracking, each frame must also preserve the current path and the next choice to examine. An explicit trail can record modifications so they can be restored when a branch is abandoned. This avoids Python’s recursion-depth limit, although the explicit stack can consume comparable memory.

Complexity

Recursion and backtracking have no universal complexity because it depends on the underlying problem. The figures below use auxiliary space, which includes the recursion stack but excludes the original input and stored output.

Approach Best Time Average Time Worst Time Auxiliary Space
One recursive path of depth n, with constant work per call O(n) O(n) O(n) O(n) stack
Unpruned branching with b >= 2 choices at depth d O(b^d) O(b^d) O(b^d) O(d) stack
Exhaustive permutations of n distinct items O(n × n!) O(n × n!) O(n × n!) O(n) stack
  • Single path: Every call performs constant work and creates one smaller call.

  • Branching: The search tree can contain exponentially many states.

  • Permutations: There are n! results, and copying each permutation can require O(n) work.

  • Stored output: Exhaustive permutations additionally require O(n × n!) space.

  • Pruned backtracking: The best case can be substantially smaller, but its exact complexity depends on the pruning rules.

  • Memoization: For repeated recursive subproblems, functools.cache can prevent recomputation. Path-dependent backtracking should not be memoized blindly; any cache key must include all state that affects valid continuations.

Common Pitfalls

  • Treating them as synonyms: Recursion organizes control flow; backtracking explores and abandons decision branches.

  • Failing to restore state: A failed mutable-state branch must restore paths, counters, or other affected state.

  • Incorrect base cases: An off-by-one error can produce invalid results or prevent termination.

  • Ignoring stack depth: Large trees, permutations, or graph searches can exceed Python’s default recursion limit.

  • Using the wrong visited scope: When enumerating simple paths in a cyclic graph, use a current-path visited set or equivalent state; a global visited set can suppress valid paths.

  • Memoizing indiscriminately: Memoization helps only when calls repeat identical subproblems, and it adds storage overhead.

  • Mutating input accidentally: Copy mutable input before arranging or generating alternatives.

  • Ignoring duplicates: Decide whether duplicate solutions are allowed and prune duplicate branches when necessary.

Interviewers commonly follow up by asking for factorial, subset generation, permutations, N-Queens, or graph-search implementation, followed by a request to convert the recursive solution to an explicit-stack version.

4

What is a base case in a recursive function?

A base case is the condition that tells a recursive function when to stop calling itself and return a final result. It prevents unnecessary recursion and must be reachable on every valid recursive path.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Base Case Works

A recursive function generally contains two parts:

  • Base case: A condition that returns immediately without making another recursive call.

  • Recursive case: Computes part of the answer by calling the function with input that moves closer to the base case.

For example, a function that sums from 1 through limit stops when limit becomes 0. Each recursive call decreases limit by one, so the base case is eventually reached.

A base case is not necessarily an empty-input check. It could be:

  • An empty collection

  • A single element

  • A threshold such as value == 0

  • A character that marks the end of a string

  • Any condition where further recursion is unnecessary

A function can also have multiple base cases. For example, recursive binary-tree processing may treat either a missing child or a leaf node as a stopping condition, depending on whether work is performed at the leaf before returning.

Call Stack Trace

For a recursive summation called with 3, the calls proceed as follows:

  1. sum_to(3) calls sum_to(2).

  2. sum_to(2) calls sum_to(1).

  3. sum_to(1) calls sum_to(0).

  4. sum_to(0) matches the base case and returns 0.

  5. The return values unwind the stack: sum_to(1) returns 1, sum_to(2) returns 3, and sum_to(3) returns 6.

The base case is limit == 0. Every recursive call moves toward it by decreasing limit by one.

To convert this recursion to iteration, use an explicit stack: push the initial limit, pop a value, add it to the total unless it is the base-case value, and then push the next smaller value. This removes reliance on Python’s call stack while preserving the same progression toward the base case.

Correctness and Termination

The base case must both:

  1. Terminate the recursion by returning without another recursive call.

  2. Produce the correct result for that input.

Correctness is commonly argued using induction:

  • The function is correct for the base-case input.

  • If it is correct for a smaller input, the recursive case uses that result and combines it with the current input to produce the correct answer.

  • Because every recursive call moves toward the base case, the function eventually terminates.

For a branching recursion, every possible branch must reach a base case. One missing path can still cause infinite recursion. When calls repeat, memoization such as functools.cache can reduce repeated computation, but it does not replace the base case.

Complexity

For the recursive summation example, where n is the limit:

  • Best, average, and worst-case time: O(n) under the standard unit-cost integer-arithmetic model. There are n + 1 calls, and each performs constant work.

  • Auxiliary space: O(n). The recursion stack contains up to n + 1 frames.

  • Input space: The input is one integer, so it uses O(1) space under the same model. Counting it does not change the overall O(n) bound.

  • Base-case check: O(1) time and space.

Python’s default recursion limit is approximately 1,000, depending on the interpreter and call stack. Python has no tail-call optimization, so deep recursive input may raise RecursionError. An iterative version using an explicit stack avoids that recursion-depth limit.

Common Pitfalls

  • Missing base case: The function may recurse indefinitely or eventually raise RecursionError.

  • Base case returns the wrong value: Termination alone does not guarantee correctness.

  • Recursive case does not progress: Every call must reduce or transform the input toward the base case.

  • Ignoring multiple branches: Every possible path must reach a valid stopping condition.

  • Confusing base case with memoization: Memoization avoids repeated computation but does not replace a base case.

  • Excessive recursion depth: Use an explicit stack when the expected depth may exceed Python’s limit.

5

How does recursion depth affect algorithm complexity?

Recursion depth is the maximum number of simultaneously active recursive frames on the call stack. It directly determines the algorithm’s stack-space requirement; it does not determine running time by itself because runtime also depends on the total number of calls and the work performed by each call.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Depth Affects Complexity

Let D be the maximum recursion depth, T the total number of recursive calls, and W the work performed per call. A useful general bound is O(T × W) time, while recursive calls require O(D) auxiliary stack space.

Recursive pattern Best time Average time Worst time Auxiliary stack
One branch per call over n elements O(n) O(n) O(n) O(D)
Full binary branching to depth D O(2^D) O(2^D) O(2^D) O(D)
Memoized Fibonacci recurrence O(n) O(n) O(n) O(n)
Binary-tree traversal O(n) O(n) O(n) O(h)
Quicksort O(n log n) O(n log n) O(n²) O(log n) best/average, O(n) worst

A linear recursion makes n calls, each doing constant work, so both time and stack depth are O(n). A full binary recursion makes 2^(D+1) - 1 calls, giving O(2^D) time but only O(D) stack depth. Tree traversal visits every node once, so its time is O(n) while its stack depth depends on the tree height h, measured in edges.

These space bounds are auxiliary space and exclude the original input. If the input’s own O(n) storage is included, add it to the listed auxiliary space.

Call Stack Trace

For a recursive sum that decreases its argument by one, the calls remain active until the base case returns:

  • sum_to(3)

  • sum_to(2)

    • sum_to(1)

    • sum_to(0) returns 0 — base case

    • returns 1 — recursive case

  • returns 3 — recursive case

  • returns 6 — recursive case

Each recursive call moves toward the base case by decreasing the argument. Counting every frame, including the base-case frame, the depth for sum_to(n) is n + 1; counting only recursive edges, it is n.

Python Recursion Limit

CPython 3.12 typically starts with sys.getrecursionlimit() set to 1000, although the usable depth can be lower because the interpreter and native stack also consume space. Python has no tail-call optimization, so a tail-recursive-looking function still retains each active frame.

Normal excessive recursion generally raises RecursionError. Increasing the recursion limit can permit deeper calls, but setting it too high may exhaust the native stack and crash the interpreter. For reliably large depths, convert the algorithm to an explicit-stack implementation instead of continually raising the limit.

Memoization and Repeated Calls

Memoization, commonly implemented with functools.cache, prevents repeated evaluation of the same subproblem. For the standard Fibonacci recurrence, it reduces O(2^n) time to O(n) time and uses O(n) cache storage. The longest dependency chain is still O(n), so the standard recursive implementation retains O(n) stack depth.

Memoization primarily reduces repeated work, not stack usage. An iterative bottom-up formulation can remove recursion entirely when stack depth is a concern.

Common Pitfalls and Interview Tips

  • Depth versus total calls: Maximum depth is not the same as the total number of calls; a shallow but heavily branching recursion can still take exponential time.

  • Off-by-one errors: State whether depth counts stack frames, recursive calls, or tree levels.

  • Ignoring stack space: Recursion depth must be included in auxiliary-space analysis.

  • Repeated subproblems: Use memoization when recursive subproblems overlap.

  • Graph cycles: Use a visited set and account for empty graphs, isolated or disconnected components, and cycles.

  • Mutating input: Avoid modifying shared structures unless mutation is intentional.

  • Integer overflow: Python integers do not overflow, but equivalent algorithms in fixed-width languages may require checks.

  • Large depths: Prefer an explicit stack rather than relying on an arbitrarily high recursion limit.

6

How does the call stack work in recursion?

The call stack is the runtime’s LIFO stack of active function invocations. Recursion adds a new frame for each unfinished call; when a call returns, its frame is removed and execution resumes in the caller’s frame.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Call Stack Works

  • Stack frame: Represents one active invocation. Depending on the language and runtime, it stores the return location, arguments, local variables, and other execution state.

  • Push on call: When a function invokes another function, the caller’s frame remains active while a new frame is pushed for the callee.

  • Pop on return: When the callee returns, its frame is removed and its return value is made available to the caller.

  • LIFO order: The most recently activated call is the first to finish. Recursive calls therefore unwind from the deepest frame back through their callers.

  • Base case: The condition that stops further recursion. Without a reachable base case, calls continue until the runtime’s recursion limit or available stack is exhausted.

Example: Factorial

For factorial(3), the calls proceed as follows:

  1. factorial(3) is called and pushes its frame.

  2. factorial(3) calls factorial(2), which pushes another frame.

  3. factorial(2) calls factorial(1), which pushes another frame.

  4. factorial(1) reaches the base case and returns 1; its frame is popped.

  5. factorial(2) resumes, computes 2 × 1, and returns 2.

  6. factorial(3) resumes, computes 3 × 2, and returns 6.

The maximum recursion depth is three factorial frames, plus the frame of the original caller.

Complexity and Recursion Depth

For linear recursion such as factorial:

  • Time complexity: Best, average, and worst case are all O(n) because there are n calls and each performs constant work apart from its recursive call.

  • Auxiliary space complexity: O(n) because all n stack frames remain active until the base case returns. The recursion stack is included, while the input itself is not counted separately.

For a branching recursion, time is O©, where C is the total number of calls, and stack space is O(d), where d is the maximum recursion depth, assuming each frame uses constant space.

Python Limits and Explicit-Stack Iteration

Python 3.12 has a default recursion limit of 1,000, which sys.getrecursionlimit() reports unless configured otherwise. Exceeding it normally raises RecursionError. Python also has no tail-call optimization, so tail-recursive calls still consume stack space.

When depth may be large, replace recursive calls with an explicit stack such as a Python list. For factorial, push (value, entering) states onto the list; on entry, push a returning state followed by the state for value - 1, and on return multiply the result by value. This avoids Python’s recursion limit, although the explicit stack can still require O(n) space. Raising the recursion limit with sys.setrecursionlimit() is less safe because an excessively high limit may exhaust the native stack.

When recursive calls repeat the same inputs, memoization with functools.cache can avoid repeated computation.

Common Pitfalls

  • Off-by-one errors: Define whether the base case includes zero, one, or an empty input.

  • Unreachable base case: Ensure every recursive path moves toward and eventually reaches the base case.

  • Stack overflow: Python normally raises RecursionError; other languages may crash, and an unsafe Python limit can also exhaust the native stack.

  • Integer overflow: Factorials and similar results quickly exceed fixed-width integer ranges in languages such as Java or C++.

  • Mutating input: Avoid modifying shared collections unless mutation is intentional; pass the required state explicitly.

  • Repeated work: Add memoization when subproblems overlap.

  • Missing visited set: Recursive graph traversals require a visited set to prevent cycles from causing infinite recursion.

  • Interview follow-ups: Interviewers commonly ask for the call trace, time and stack-space complexity, an iterative conversion using an explicit stack, and how memoization or cycle detection would change the solution.

7

What safety risks occur when determining recursion depth?

Recursion depth is the maximum number of simultaneously active call frames on one call path. Determining it is risky because input shape can force deeper recursion than expected, helper frames can make actual usage exceed an estimate, and exceeding a runtime’s limit may crash the process instead of producing a recoverable exception.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Safety Risks

  • Unbounded recursion: A missing termination condition or failure to make progress can consume the call stack until the program fails.

  • Underestimating required depth: The depth of the input is not necessarily the runtime recursion depth. Helper functions, wrappers, generators, or multiple recursive calls can add frames.

  • Native stack exhaustion: Some runtimes do not detect excessive recursion safely and may terminate the entire process through a segmentation fault or stack overflow.

  • Memory exhaustion: Every active frame consumes stack memory, and memoization or large per-frame objects can substantially increase total memory use.

  • Runaway execution: Even when recursion eventually terminates, excessive branching or repeated states can cause excessive CPU time.

  • Incorrect depth accounting: Off-by-one errors can arise from counting the initial frame, counting edges versus nodes, or failing to remove entries when unwinding.

Interpreting Depth Safely

Input depth and call-stack depth should be treated as separate quantities. For example, a tree may have height h, but a particular recursive traversal may use roughly h + 1 frames. A different algorithm that processes both children may have different peak usage.

A safe recursive traversal should have:

  1. A clearly defined termination condition, such as reaching a leaf or an empty container.

  2. A recursive case that makes measurable progress toward that condition, such as descending into one child.

  3. A check against the allowed depth before making another recursive call.

  4. Cycle detection when the input is not guaranteed to be a tree.

A small call-stack trace is:

  • visit(root, 0)

  • visit(child, 1)

    • visit(leaf, 2) reaches the base case.

Each recursive step descends one level toward a finite leaf, so termination depends on the input being finite and acyclic.

Python 3.12 Considerations

In a normal CPython 3.12 process, sys.getrecursionlimit() initially returns 1000. Exceeding that configured limit normally raises RecursionError, but setting the limit excessively high can exhaust the native stack and crash the interpreter before Python raises that exception.

Python 3.12 has no tail-call optimization, so replacing a recursive call with return recursive_call(...) does not reduce stack usage. functools.cache can eliminate repeated computation, but it does not reduce recursion depth and adds O(k) space for k distinct cached states.

Safer Design Strategies

  • Use an explicit stack when recursion depth can be large. This moves state from the native call stack to the heap, although the heap can still run out of memory.

  • Bound the input or depth before processing when practical, such as limiting accepted JSON nesting or directory traversal depth.

  • Use memoization when subproblems repeat and O(k) cache space is acceptable.

  • Detect cycles when the input graph is malformed or not guaranteed to be acyclic. An active-path set detects cycles; a global visited set also prevents repeated processing in general graphs.

  • Avoid raising the recursion limit as the primary fix. Convert the algorithm to iteration or redesign it to use less stack per call.

Complexity and Edge Cases

For a tree with n nodes and height h, excluding the input tree itself:

Approach Best, Average, Worst Time Auxiliary Space Reason
Recursive traversal O(n) O(h), worst O(n) Includes O(h) active frames and any path-tracking state
Iterative traversal with an explicit stack O(n) O(n) worst; O(h) for a chain Pending and exit entries can grow with the number of nodes
  • Empty input: Usually returns depth 0.

  • One element: A single tree node has depth 0 when depth counts edges.

  • Duplicates and negative values: Do not affect depth.

  • Already sorted input: Not relevant to tree depth.

  • Cycles: A cycle violates the tree model and must be detected rather than traversed indefinitely.

  • Disconnected graphs: The result must define whether depth is measured per component or as the maximum over all components; a visited set is also required.

Common Pitfalls and Interview Tips

  • Do not assume maximum input depth equals maximum recursion depth.

  • Do not deliberately trigger RecursionError to discover a safe limit; the safe value depends on the platform, current stack use, and call shape.

  • Include or exclude the initial frame deliberately when reporting call depth.

  • Remove nodes from an active-path set during unwinding so shared nodes are not mistaken for cycles.

  • Interviewers commonly follow up with questions about converting recursion to an explicit stack, detecting cycles, handling disconnected components, and explaining the auxiliary-space cost.

8

What is the Depth-First Search algorithm and how does it work?

Depth-first search (DFS) is a graph traversal algorithm that explores as far as possible along one path before backtracking to explore remaining branches. It is commonly used for cycle detection, connected components, topological sorting, and searching paths or reachable nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

DFS maintains a visited set and follows this process:

  1. Mark the starting vertex as visited and record it.

  2. Select one unvisited adjacent vertex.

  3. Recursively explore that vertex before returning to the previous call.

  4. When no unvisited neighbors remain, backtrack to the caller.

  5. Continue until every reachable vertex has been visited.

The visited set prevents infinite recursion when the graph contains cycles or duplicate edges. Marking a vertex when it is discovered also prevents multiple parents from scheduling it repeatedly.

DFS is not necessarily unique because its traversal order depends on the order in which neighbors are considered.

Main Variants

  • Recursive DFS: Uses the call stack to represent the active path. It is concise, but deep graphs can exceed Python’s default recursion limit of about 1000.

  • Iterative DFS: Replaces recursion with an explicit stack. This avoids recursion-limit errors and is preferable for large or potentially deep graphs.

  • Preorder DFS: Records a vertex when it is first visited.

  • Postorder DFS: Records a vertex after all its descendants have been processed. Postorder is commonly used for topological sorting.

DFS works on trees as well as general graphs. On a tree, there is exactly one simple path between any two connected vertices, so a visited set is still useful for implementation consistency but is not required to prevent cycles.

Complexity

Let V be the number of vertices and E the number of edges in the reachable component (or the whole graph if connected).

Case Recursive DFS Iterative DFS Reason
Best O(V + E) O(V + E) A complete traversal processes every reachable vertex and adjacency entry
Average O(V + E) O(V + E) Each vertex and edge in the component is processed a constant number of times
Worst O(V + E) O(V + E) The entire reachable graph may be explored
Auxiliary space O(V) O(V) Includes visited and either the recursion stack or explicit stack

The input adjacency lists are not counted as auxiliary space. If the input representation is included, total storage is O(V + E). The recursive space bound includes a maximum call-stack depth of O(V); the iterative version includes an explicit stack of O(V).

For a disconnected graph, a traversal from one starting vertex visits only that vertex’s connected component. Other components require additional starting vertices.

Code Example

def dfs_recursive(
    graph: dict[str, list[str]], start: str
) -> list[str]:
    """Return recursive DFS visit order from start."""
    visited: set[str] = set()
    order: list[str] = []

    def visit(node: str) -> None:
        # Base case: an already visited node must not be processed again.
        if node in visited:
            return

        visited.add(node)
        order.append(node)

        unvisited_neighbors = [
            neighbor
            for neighbor in graph.get(node, [])
            if neighbor not in visited
        ]

        # Base case: no unvisited neighbors to explore.
        if not unvisited_neighbors:
            return

        # Recursive case: each call discovers one new vertex and moves
        # toward the base case by reducing the unvisited vertices.
        for neighbor in unvisited_neighbors:
            visit(neighbor)

    visit(start)
    return order


def dfs_iterative(
    graph: dict[str, list[str]], start: str
) -> list[str]:
    """Return iterative DFS visit order from start."""
    visited: set[str] = {start}
    stack: list[str] = [start]
    order: list[str] = []

    while stack:
        node = stack.pop()
        order.append(node)

        # Reverse the neighbors to preserve recursive-style traversal order.
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return order


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["E"],
    "E": [],
}

print(dfs_recursive(graph, "A"))  # ['A', 'B', 'D', 'E', 'C']
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'E', 'C']

Edge cases handled by these implementations include one-vertex graphs, duplicate edges, self-loops, cycles, missing adjacency entries, and disconnected components when separate roots are supplied. Labels can be strings or conceptually any hashable values; DFS does not require sorted or numeric input.

Call Stack and Trace

For the recursive traversal from A, the calls are:

visit(A)
└── visit(B)
    ├── visit(D)
    │   └── visit(E)
    └── visit(C)
        └── returns: D and E are already visited

Each recursive call discovers a new vertex, so the remaining unvisited set becomes smaller. A cycle such as C -> D -> C terminates because C is marked before DFS descends into D.

Python does not optimize tail recursion. For a chain containing more than roughly 1000 vertices, the recursive implementation may raise RecursionError; the iterative implementation avoids that limitation because it uses an explicit stack.

Interview Tips

  • Always use a visited set or equivalent marker when the graph may contain cycles.

  • Do not assume DFS has one fixed visit order; adjacency order determines the result.

  • Do not mutate the input graph unless modification is explicitly required.

  • Handle disconnected graphs by starting another traversal for each unvisited component.

  • Distinguish DFS from breadth-first search: DFS follows one path deeply, while BFS explores level by level.

  • Use functools.cache for recursive problems with repeated overlapping subproblems, such as Fibonacci. Ordinary graph DFS uses a visited set instead.

  • Common follow-up questions include cycle detection, connected components, topological sorting, path finding, and the choice between recursive and iterative traversal.

9

How do you implement recursive binary search in Python?

A recursive binary search finds a target in a sorted sequence by repeatedly examining its midpoint and searching only the half that could contain the target. Each recursive call reduces the search interval until it finds the value or the interval becomes empty.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm maintains an inclusive interval from low to high:

  • If low > high, the target is absent.

  • Compute mid = low + (high - low) // 2.

  • If values[mid] == target, return mid.

  • If the target is smaller than values[mid], recursively search [low, mid - 1].

  • Otherwise, recursively search [mid + 1, high].

The input must be sorted in ascending order. Negative numbers, duplicates, and an empty sequence are supported. With duplicates, the function returns one matching index; it does not guarantee the first occurrence.

Call Stack Trace

For recursive_binary_search([1, 3, 5, 7, 9], 7):

  1. search(low=0, high=4) examines mid=2, containing 5.

  2. Since 7 > 5, it calls search(low=3, high=4).

  3. That call examines mid=3, containing 7, and returns index 3.

The corresponding call stack is:

search(0, 4)
└── search(3, 4) → returns 3

Each call moves toward the base case by either moving low upward or high downward.

Complexity

Case Time Reason
Best O(1) The target is found at the first midpoint.
Average O(log n) Each comparison eliminates approximately half of the remaining interval.
Worst O(log n) The search continues until the interval becomes empty.
  • Auxiliary space: O(log n), including the recursion stack.

  • Input storage: The input sequence is not counted in the O(log n) auxiliary-space figure. If input storage is included, total space is O(n).

  • The recursive depth is approximately log2(n), so Python’s default recursion limit of about 1000 is not a practical concern for normal-sized in-memory lists. Python does not provide tail-call optimization, but an iterative implementation can avoid recursion overhead.

Memoization with functools.cache is unnecessary because the recursive branches search different intervals and do not repeat the same subproblem.

Code Example

from collections.abc import Sequence


def recursive_binary_search(values: Sequence[int], target: int) -> int:
    """Return an index of target in ascending sorted values, or -1 if absent."""

    def search(low: int, high: int) -> int:
        # Base case: the candidate interval is empty.
        if low > high:
            return -1

        mid = low + (high - low) // 2

        # Base case: the target is found at the midpoint.
        if values[mid] == target:
            return mid

        # Recursive case: search only the half that may contain the target.
        # Each call moves an interval boundary toward the empty-range base case.
        if target < values[mid]:
            return search(low, mid - 1)

        return search(mid + 1, high)

    return search(0, len(values) - 1)


print(recursive_binary_search([1, 3, 5, 7, 9], 7))  # 3
print(recursive_binary_search([1, 3, 5, 7, 9], 4))  # -1

Common Pitfalls

  • Unsorted input: Binary search can return an incorrect result. Sorting first costs O(n log n) time and may require additional space.

  • Off-by-one errors: Mixing inclusive and exclusive interval boundaries can skip an element or cause infinite recursion.

  • Duplicate values: The algorithm finds a matching element, not necessarily the first or last occurrence.

  • Empty or single-element input: An empty sequence immediately returns -1; a one-element sequence is checked directly.

  • Unexpected mutation: The function does not modify the input.

  • Interview follow-up: Discuss why the midpoint avoids overflow in other languages, how to implement a lower-bound search for duplicates, and how an iterative version would avoid the call stack.

10

How do you solve Tower of Hanoi recursively?

The recursive Tower of Hanoi solution moves the smallest n - 1 disks to the auxiliary peg, moves the largest disk to the target peg, and then moves the n - 1 disks from the auxiliary peg onto it. This produces the minimum possible number of moves: 2ⁿ − 1.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Strategy

For move(n, source, target, auxiliary):

  1. If n == 0, do nothing.

  2. Recursively move n - 1 disks from source to auxiliary, using target as the temporary peg.

  3. Move disk n from source to target.

  4. Recursively move n - 1 disks from auxiliary to target, using source as the temporary peg.

The recurrence for the number of moves is:

M(n) = 2M(n - 1) + 1, with M(0) = 0, giving M(n) = 2ⁿ - 1.

Call Stack Trace

For three disks, moving from peg 1 to peg 3 through peg 2:

move(3, 1, 3, 2)
  move(2, 1, 2, 3)
    move(1, 1, 3, 2)    -> move disk 1 from peg 1 to peg 3
    move disk 2 from peg 1 to peg 2
    move(1, 3, 2, 1)    -> move disk 1 from peg 3 to peg 2
  move disk 3 from peg 1 to peg 3
  move(2, 2, 3, 1)
    move(1, 2, 1, 3)    -> move disk 1 from peg 2 to peg 1
    move disk 2 from peg 2 to peg 3
    move(1, 1, 3, 2)    -> move disk 1 from peg 1 to peg 3

Each recursive call reduces the disk count by one, so every branch moves toward the base case.

Complexity

Measure Best Average Worst Reason
Time O(2ⁿ) O(2ⁿ) O(2ⁿ) The recurrence is T(n) = 2T(n - 1) + O(1).
Auxiliary space O(n) O(n) O(n) The recursion stack contains up to n + 1 frames.
Space including returned moves O(2ⁿ) O(2ⁿ) O(2ⁿ) The result contains exactly 2ⁿ - 1 move descriptions.

The input is one integer, so it occupies O(1) space and is not counted in the O(n) auxiliary-space calculation.

Code Example

def solve_tower_of_hanoi(num_disks: int) -> list[str]:
    """Return the minimum recursive move sequence for Tower of Hanoi."""
    if num_disks < 0:
        raise ValueError("num_disks must be non-negative")

    moves: list[str] = []

    def move_disks(
        count: int,
        source: int,
        target: int,
        auxiliary: int,
    ) -> None:
        # Base case: no disks remain, so there is nothing to move.
        if count == 0:
            return

        # Recursive case: move count - 1 disks, move the largest, then move
        # count - 1 disks again. Each call moves toward the base case.
        move_disks(count - 1, source, auxiliary, target)
        moves.append(
            f"Move disk {count} from peg {source} to peg {target}"
        )
        move_disks(count - 1, auxiliary, target, source)

    move_disks(num_disks, 1, 3, 2)
    return moves


print(solve_tower_of_hanoi(3))
# Expected output:
# [
#     'Move disk 1 from peg 1 to peg 3',
#     'Move disk 2 from peg 1 to peg 2',
#     'Move disk 1 from peg 3 to peg 2',
#     'Move disk 3 from peg 1 to peg 3',
#     'Move disk 1 from peg 2 to peg 1',
#     'Move disk 2 from peg 2 to peg 3',
#     'Move disk 1 from peg 1 to peg 3'
# ]

For large numbers of disks, replace recursion with an explicit stack:

def solve_tower_of_hanoi_iterative(num_disks: int) -> list[str]:
    """Return the minimum move sequence using an explicit stack."""
    if num_disks < 0:
        raise ValueError("num_disks must be non-negative")

    moves: list[str] = []
    # Stack frames: (count, source, target, auxiliary, phase)
    # phase 0 = before first recursive call, phase 1 = after first call (do move and start second call)
    stack: list[tuple[int, int, int, int, int]] = [
        (num_disks, 1, 3, 2, 0)
    ]

    while stack:
        count, source, target, auxiliary, phase = stack.pop()

        if count == 0:
            continue

        if phase == 0:
            # Simulate the first recursive call.
            stack.append((count, source, target, auxiliary, 1))
            stack.append((count - 1, source, auxiliary, target, 0))
        else:
            # phase == 1: perform the move and simulate the second recursive call.
            moves.append(
                f"Move disk {count} from peg {source} to peg {target}"
            )
            # Second recursive call starts at phase 0.
            stack.append((count - 1, auxiliary, target, source, 0))

    return moves


print(solve_tower_of_hanoi_iterative(3))
# Expected output: the same seven moves shown above.

Common Pitfalls

  • Base case: Use n == 0; using n == 1 can either add an unnecessary move or complicate the recursion.

  • Correct peg roles: The temporary peg changes between the two recursive calls.

  • Empty input: Zero disks returns an empty list.

  • One disk: One disk produces exactly one move.

  • Negative disks: The implementation raises ValueError.

  • Invalid models: Duplicate disk sizes, sorted inputs, disconnected graphs, and cycles do not apply to Tower of Hanoi.

  • Recursion depth: Python’s default recursion limit is about 1000, and Python has no tail-call optimization. Use the explicit-stack version for large n.

  • Memoization: functools.cache does not improve this solution because the recursive states do not repeat; each subproblem is solved once.

11

How do you recursively check whether a string is a palindrome?

A palindrome is a string that reads identically forward and backward. A recursive solution compares characters from both ends, moving inward until the characters match or the two pointers meet.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The recursive function receives two indexes:

  • left identifies the next character to compare from the beginning.

  • right identifies the next character to compare from the end.

  • The base case occurs when the indexes meet or cross. Every compared pair matched, so the string is a palindrome.

  • The recursive case compares text[left] and text[right]. If they differ, the string is not a palindrome; otherwise, the function calls itself with both indexes moved inward.

For "level", the call stack is:

compare(0, 4)
└── compare(1, 3)
    └── compare(2, 2) → True

A mismatch at any level immediately returns False.

Complexity

For a string of length n:

Approach Time Auxiliary space Reason
Recursive comparison O(n) O(n) Makes O(n) comparisons and stores O(n) recursive calls
Iterative explicit stack O(n) O(1) Compares each mirrored pair while retaining at most one pending index pair

The input string itself is not counted in auxiliary space. The recursive version has O(n) recursion depth and can exceed Python’s default recursion limit of about 1,000. Python does not perform tail-call optimization, so the iterative version is safer for long strings.

Memoization is unnecessary because these recursive calls do not repeat the same subproblem.

Edge Cases and Alternatives

  • Empty string: Treated as a palindrome by convention.

  • One-character string: Always a palindrome.

  • Duplicate characters: Handled naturally because every mirrored pair is checked.

  • Case or punctuation: This implementation compares characters exactly. To ignore case and non-alphanumeric characters, first use ''.join(char.casefold() for char in text if char.isalnum()); this normalization requires an additional O(n) string.

  • Large inputs: Use an explicit stack or a two-pointer loop to avoid Python’s recursion-depth limit.

Code Example

def is_palindrome(text: str) -> bool:
    """Return whether text is a palindrome using exact character comparison."""

    def compare(left: int, right: int) -> bool:
        # Base case: the pointers met or crossed, so all pairs matched.
        if left >= right:
            return True

        # Recursive case: mirrored characters must be equal.
        if text[left] != text[right]:
            return False

        # The recursive call moves toward the base case.
        return compare(left + 1, right - 1)

    return compare(0, len(text) - 1)


def is_palindrome_iterative(text: str) -> bool:
    """Return whether text is a palindrome without using recursion."""
    stack: list[tuple[int, int]] = [(0, len(text) - 1)]

    while stack:
        left, right = stack.pop()

        if left >= right:
            continue

        if text[left] != text[right]:
            return False

        stack.append((left + 1, right - 1))

    return True


print(is_palindrome("level"))       # True
print(is_palindrome("hello"))       # False
print(is_palindrome_iterative("racecar"))  # True

Interview Tips

  • Clarify whether comparisons are case-sensitive and whether spaces or punctuation are ignored.

  • Mention the O(n) recursion stack; many candidates incorrectly claim O(1) space for recursive solutions.

  • Explain that each recursive call reduces the remaining problem by two characters, guaranteeing progress toward the base case.

  • Avoid reversing the string unless an additional O(n) result string is acceptable.

  • A common follow-up asks for an iterative solution that avoids the default recursion limit.

12

How does recursive in-order tree traversal work?

In-order tree traversal visits every node in the order left subtree, current node, right subtree. Recursion performs the left and right traversals by calling the same function on smaller subtrees, while a base case stops processing empty subtrees.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each node, the recursive function follows this sequence:

  1. If the node is None, return immediately. This is the base case.

  2. Recursively traverse the node’s left subtree.

  3. Visit the current node and record its value.

  4. Recursively traverse the node’s right subtree.

Each recursive call moves down to a child, so the subtree becomes smaller until it reaches the None base case.

The order is called in-order because the current node is processed between its two subtrees. In a binary search tree (BST), this produces values in ascending order. For an arbitrary binary tree, it produces a consistent traversal order but not necessarily sorted values.

Call Stack Trace

For this tree:

2
   / \
  1   3

The recursive calls proceed as follows:

  • visit(2)

  • visit(1)

    • visit(None) — base case

    • Append 1

    • visit(None) — base case

  • Append 2

  • visit(3)

    • visit(None) — base case

    • Append 3

    • visit(None) — base case

The call stack grows while descending into the left subtree and shrinks as the function returns to process each node.

Complexity

Let n be the number of nodes and h the tree height measured in edges.

Case Time Auxiliary space Reason
Best O(n) O(h + 1) Every node is visited once, and the recursion stack follows the tree height
Average O(n) O(h + 1) The same work is required regardless of the node arrangement
Worst O(n) O(n + 1) A completely skewed tree has height n - 1

The +1 accounts for the base-case call on an empty subtree. The input tree itself is not counted as auxiliary space. The returned list uses O(n) additional space, so total additional memory, including output, is O(n).

Memoization is unnecessary for a standard tree traversal because each node is visited exactly once.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class TreeNode:
    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def inorder_values(root: TreeNode | None) -> list[int]:
    """Return node values in left-root-right order."""
    values: list[int] = []

    def visit(node: TreeNode | None) -> None:
        # Base case: an empty subtree contributes no values.
        if node is None:
            return

        # Recursive case: descend into the smaller left subtree.
        # Each call moves toward the base case by following a child.
        visit(node.left)

        values.append(node.value)

        # Recursive case: descend into the smaller right subtree.
        # Each call moves toward the base case by following a child.
        visit(node.right)

    visit(root)
    return values


def inorder_values_iterative(root: TreeNode | None) -> list[int]:
    """Return in-order values using an explicit stack."""
    values: list[int] = []
    stack: list[TreeNode] = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        values.append(current.value)
        current = current.right

    return values


tree = TreeNode(
    2,
    left=TreeNode(1),
    right=TreeNode(3),
)

print(inorder_values(tree))          # [1, 2, 3]
print(inorder_values_iterative(tree))  # [1, 2, 3]

Common Pitfalls

  • Wrong traversal order: Processing the root before the left subtree produces pre-order, not in-order.

  • Missing base case: Without the None return, recursion continues indefinitely.

  • Recursion depth: A skewed tree with more than roughly 1,000 levels can raise RecursionError. Python 3.12 has no tail-call optimization, so use the explicit-stack version for potentially deep trees.

  • Empty or single-node tree: An empty tree returns []; a single-node tree returns [node.value].

  • Duplicates and negative values: Both are traversed normally and retained in their in-order positions.

  • Unrelated graph cases: Disconnected graphs, cycles, and already-sorted input are not standard binary-tree cases. If shared nodes or cycles are possible, the structure is a graph and requires a visited set to prevent repeated traversal.

13

How do you calculate the N-th Fibonacci number with tail recursion?

A tail-recursive Fibonacci function carries the previous two Fibonacci values through its arguments, so the recursive call is the final operation. Python 3.12 does not optimize tail calls, so the implementation still uses O(n) recursion-stack space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Tail-Recursive Design

Use the standard definition:

  • F(0) = 0

  • F(1) = 1

  • F(n) = F(n - 1) + F(n - 2)

Instead of calculating both values independently, maintain:

  • current: the Fibonacci value for the current position.

  • following: the Fibonacci value for the next position.

  • remaining: the number of steps still required.

Each recursive call changes remaining to remaining - 1, moving it toward the base case of zero.

Code Example

def fibonacci(n: int) -> int:
    """Return F(n), where F(0) = 0 and F(1) = 1."""
    if n < 0:
        raise ValueError("n must be non-negative")

    def tail_fibonacci(remaining: int, current: int, following: int) -> int:
        # Base case: no positions remain, so return the current value.
        if remaining == 0:
            return current

        # Recursive case: remaining decreases toward the base case,
        # and the tail call is the final operation.
        return tail_fibonacci(
            remaining - 1,
            following,
            current + following,
        )

    return tail_fibonacci(n, 0, 1)


print(fibonacci(10))  # 55

If the recursion depth could exceed Python’s default limit of approximately 1,000 calls, use an explicit stack:

def fibonacci_with_stack(n: int) -> int:
    """Return F(n) without using Python's recursion limit."""
    if n < 0:
        raise ValueError("n must be non-negative")

    stack: list[tuple[int, int, int]] = [(n, 0, 1)]

    while stack:
        remaining, current, following = stack.pop()

        # Base case: the required position has been reached.
        if remaining == 0:
            return current

        # Replace the current state with its next recursive state.
        stack.append((remaining - 1, following, current + following))

    raise RuntimeError("Unreachable state")


print(fibonacci_with_stack(10))  # 55

Call Stack Trace

For fibonacci(3), the calls are:

tail_fibonacci(3, 0, 1)
└── tail_fibonacci(2, 1, 1)
    └── tail_fibonacci(1, 1, 2)
        └── tail_fibonacci(0, 2, 3)
            └── returns 3

Every call decreases remaining by one, eventually reaching the base case.

Complexity

Approach Time Auxiliary Space Reason When to Use
Naive recursion O(φⁿ) O(n) recursion stack It makes two recursive calls per level, and the maximum call depth is O(n) Demonstrate the exponential problem
Memoized recursion with functools.cache O(n) O(n) cache plus O(n) stack Each distinct subproblem is computed once, but recursion and caching both store O(n) entries Avoid repeated subproblems
Tail-recursive accumulator in Python O(n) O(n) recursion stack It performs one call per decrement, and Python retains every active frame because it has no tail-call optimization Demonstrate the tail-recursive pattern
Explicit-stack accumulator O(n) O(1) It performs one state transition per decrement, and the stack contains at most one tuple at a time Avoid Python’s recursion limit with optimal auxiliary space

For the tail-recursive implementation, best, average, and worst-case time are all O(n). The explicit-stack implementation also has O(n) best, average, and worst-case time. All auxiliary-space figures exclude the input itself. These bounds assume unit-cost integer arithmetic; Python integers grow in size as Fibonacci values become large.

Common Pitfalls

  • Indexing mismatch: This implementation returns F(0) = 0. If an interviewer defines the first Fibonacci number as 1, call fibonacci(n - 1) for positive n.

  • Recursion limit: Python’s default limit is about 1,000 calls. Use the explicit-stack version for large inputs instead of raising sys.getrecursionlimit().

  • Incorrect tail-call claim: Tail recursion is not constant-space in Python because Python does not perform tail-call optimization.

  • Unnecessary memoization: The accumulator version does not repeat identical subproblems, so functools.cache would not improve it.

  • Negative input: Reject negative n explicitly rather than recursing indefinitely.

  • Common follow-up: Interviewers may ask for an O(1)-space accumulator loop, a memoized recursive solution, or an explanation of why the tail call still occupies stack space in Python.

14

How do compilers optimize tail recursion, and what benefits does it provide?

Tail recursion is a recursive call in tail position, meaning the call is the final operation and its result is returned directly. Compilers can eliminate or reuse the current stack frame, effectively converting the recursion into a loop while preserving the program’s result.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Tail-Call Optimization Works

A call is in tail position when no work remains after it returns. For example:

return recursive_call(arguments)

A compiler supporting tail-call optimization may:

  1. Detect that the recursive call is in tail position.

  2. Reuse the current stack frame instead of allocating another one.

  3. Replace the call with a jump or continuation.

  4. Return the final result directly to the original caller.

Some runtimes or libraries use a trampoline: the recursive function returns a thunk or tail-call descriptor, and a driver loop invokes it. This also avoids an unbounded chain of pending stack frames.

The following is not tail recursion because addition occurs after the recursive call:

return 1 + recursive_call(n - 1)

Call Stack and Complexity

For the tail_sum operation over n values, which visits each value exactly once:

  • Time: The best, average, and worst cases are each O(n), because each value is processed once.

  • Space without optimization: O(n) auxiliary space because the recursion depth reaches n. The input is not counted.

  • Space with proper tail-call optimization: O(1) auxiliary space because only one stack frame is needed. The input is not counted.

For tail_sum([2, 3]), the unoptimized CPython call stack is:

tail_sum([2, 3], index=0, total=0)
  tail_sum([2, 3], index=1, total=2)
    tail_sum([2, 3], index=2, total=5)
      returns 5

With proper tail-call optimization, the same frame is reused conceptually:

(index=0, total=0) → (index=1, total=2) → (index=2, total=5) → 5

There is no growing chain of recursive frames.

Benefits

  • Can prevent stack overflow from the recursive chain: Deep tail recursion does not require one stack frame per call.

  • Reduces memory usage: Auxiliary stack space can remain constant.

  • Improves performance: Compilers may avoid repeated frame creation and teardown.

  • Supports functional-style algorithms: Tail-recursive list processing and tree traversals can remain recursive without exhausting the call stack.

  • Enables loop conversion: A compiler can transform tail recursion into an equivalent while loop.

Language and Compiler Support

Tail-call optimization depends on both language semantics and compiler implementation:

  • Some implementations of Scheme guarantee proper tail recursion.

  • C and C++ compilers may perform sibling-call optimization, but the language standards do not guarantee it.

  • Java does not guarantee general tail-call optimization.

  • CPython 3.12 does not optimize tail calls. Its default recursion limit is approximately 1,000, so sufficiently deep recursion raises RecursionError.

  • Other languages may provide explicit constructs or libraries for trampolines and loop conversion.

A compiler cannot optimize every call that appears last syntactically. It must preserve semantics involving destructors, exception handling, stack unwinding, and argument cleanup.

Code Example

This CPython 3.12 example shows tail recursion and its iterative equivalent. The recursive version is semantically correct but remains vulnerable to RecursionError for large inputs.

def tail_sum(values: list[int], index: int = 0, total: int = 0) -> int:
    """Return the sum using a recursive call in tail position."""
    if index == len(values):  # Base case
        return total

    # Recursive case: this tail call moves index toward len(values).
    return tail_sum(values, index + 1, total + values[index])


def tail_sum_iterative(values: list[int]) -> int:
    """Return the same sum using an explicit loop."""
    total = 0
    index = 0

    while index < len(values):
        total += values[index]
        index += 1

    return total


print(tail_sum([2, 3, 4]))       # 9
print(tail_sum_iterative([2, 3, 4]))  # 9

An optimizing compiler could effectively transform the first function into the second. CPython executes the first function with O(n) recursion-stack space, while the second uses O(1) auxiliary space; both take O(n) time.

Common Pitfalls

  • Misidentifying tail position: Work performed after the call prevents optimization.

  • Assuming every compiler supports it: Syntax alone does not guarantee stack-frame elimination.

  • Expecting CPython to optimize tail calls: Use an explicit loop or trampoline-style design instead.

  • Ignoring cleanup semantics: Some operations prevent a compiler from replacing the call safely.

  • Forgetting recursion limits: A tail-recursive function in CPython can still exceed sys.getrecursionlimit().

  • Off-by-one errors: Check the base condition before indexing the input.

  • Integer overflow: Python integers are arbitrary-precision, but an equivalent implementation in a fixed-width language may overflow.

  • Mutating input: These functions do not mutate the list; state that policy explicitly if a variant transforms it.

  • Visited sets: They are not needed for this linear sum, but cyclic graph traversals require them.

  • Edge cases: Empty input returns 0; one-element, duplicate, and negative inputs follow ordinary addition. Input order, including already sorted input, does not affect the result. Disconnected graphs and cycles are not applicable to this summation example.

  • Interview follow-ups: Interviewers commonly ask how to detect a tail call, why the stack remains constant after optimization, how recursion can be converted to iteration, and which languages guarantee proper tail recursion.

15

How do head recursion and tail recursion differ?

Head recursion uses the result of the recursive call in further computation, while tail recursion makes the recursive call the final operation and directly returns its result. In Python 3.12, neither form benefits from automatic tail-call optimization.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • Head recursion: The recursive call’s result is needed after it returns. Combining or transforming that result is therefore called post-recursive work.

  • Tail recursion: The recursive call is the last action, so the current stack frame has no additional work to perform after the call returns.

  • Stack behavior: Tail recursion is easier to convert to iteration because there are no pending post-recursive operations.

  • Performance in Python: Python does not optimize tail recursion. Both forms normally consume one stack frame per recursive call.

Approach Time Complexity Auxiliary Space When to Use
Head recursion Depends on the algorithm; typically O(n) calls plus required work O(d) recursion stack The recursive result must be transformed or combined
Tail recursion Depends on the algorithm; typically O(n) calls plus required work O(d) in Python The final result can be returned or passed directly onward
Tail recursion converted to iteration Usually the same as recursion Often O(1) for simple accumulator patterns Large inputs that could exceed Python’s recursion limit

Here, d is the maximum recursion depth, and auxiliary space includes the recursion stack but excludes the input itself.

Call Stack and Complexity

For head-recursive factorial with an input of 3, head_factorial(3) calls head_factorial(2). The multiplication by 3 cannot occur until that call returns. The same pattern continues through head_factorial(1) and the base case head_factorial(0), which returns 1; the pending multiplications then occur while the stack unwinds.

For tail-recursive factorial using an accumulator, the calls proceed from helper(3, 1) to helper(2, 3), helper(1, 6), and finally the base case helper(0, 6). Each recursive call directly returns the result of the next call, so there are no multiplication frames waiting during unwinding.

For factorial:

  • Best, average, and worst-case time: O(n), because each call performs constant work and makes one recursive call.

  • Recursive auxiliary space: O(n), because n + 1 calls can be active simultaneously.

  • Iterative auxiliary space: O(1) for an accumulator-based implementation that keeps only the current value and accumulator.

  • The input itself is not counted in auxiliary space.

Tail recursion does not automatically make an algorithm faster. It mainly removes pending work from the stack and provides a straightforward path to an iterative implementation.

Python Behavior

Python’s default recursion limit is approximately 1,000, obtainable through sys.getrecursionlimit(). Python also has no tail-call optimization, so a tail-recursive function still uses O(d) stack space.

When a recursive algorithm can exceed that limit, convert it to an iterative version. A simple tail-recursive accumulator can be replaced by a loop that keeps the current value and accumulator in variables. If multiple pending states must be preserved, use an explicit stack and push and pop those states one at a time.

Common Pitfalls and Interview Tips

  • Assuming Python optimizes tail calls: It does not; use an explicit stack or a loop for potentially deep recursion.

  • Confusing tail position with tail-call optimization: Tail position describes the program structure, not Python’s runtime behavior.

  • Ignoring pending operations: Head recursion needs additional work during unwinding; converting it to iteration generally requires storing those pending operations.

  • Forgetting base cases: Every recursive function needs a clearly identified base case and a recursive case that moves toward it.

  • Repeated subproblems: If recursion repeatedly evaluates the same inputs, functools.cache can reduce time, although it does not remove recursion-stack usage.

  • Edge cases: When adapting a recursive algorithm, explicitly handle empty input, one element, duplicates, negative numbers where applicable, already sorted input, disconnected graphs, and cycles as relevant to the problem.

  • Likely follow-up questions: Interviewers may ask for an iterative version, an O(d) call-stack analysis, or how memoization would affect a tree recursion.

16

How can factorial be calculated with a tail-recursive function in Python?

Use an accumulator so the recursive call is the final operation. The helper is tail-recursive conceptually, although Python 3.12 does not implement tail-call optimization, so its calls still occupy the normal recursion stack.

Read full answer

Applies toPython 3.12

Tail-Recursive Approach

A factorial can be represented with two values:

  • remaining: the number whose factorial is still being calculated.

  • accumulator: the product calculated so far.

The recurrence is:

factorial_tail(remaining, accumulator) = factorial_tail(remaining - 1, accumulator × remaining)

The base case is remaining == 0, at which point the accumulator contains the factorial. Each recursive call decreases remaining by one, so it always progresses toward the base case.

Call Stack Trace

For the helper calls made by factorial(5):

factorial_tail(5, 1)
  factorial_tail(4, 5)
    factorial_tail(3, 20)
      factorial_tail(2, 60)
        factorial_tail(1, 120)
          factorial_tail(0, 120)  # Base case: return 120

The helper is tail-recursive because factorial_tail(...) is returned directly without performing work after the recursive call returns.

Code Example

def factorial(number: int) -> int:
    """Calculate factorial using a tail-recursive helper."""
    if isinstance(number, bool) or not isinstance(number, int):
        raise TypeError("number must be an integer")
    if number < 0:
        raise ValueError("factorial is undefined for negative numbers")

    def factorial_tail(remaining: int, accumulator: int) -> int:
        # Base case: all factors have been multiplied.
        if remaining == 0:
            return accumulator

        # Recursive case: remaining decreases toward the base case.
        return factorial_tail(remaining - 1, accumulator * remaining)

    return factorial_tail(number, 1)


print(factorial(5))  # 120
print(factorial(0))  # 1

Complexity

Case Time Auxiliary space
Best O(n) O(n)
Average O(n) O(n)
Worst O(n) O(n)
  • Time: There are n + 1 helper calls: the base case and n recursive steps that each perform one multiplication.

  • Space: The recursion depth reaches n + 1 helper frames, so the stack uses O(n) space.

  • These bounds assume constant-time arithmetic. Python integers grow with the result, so very large factorials also incur additional big-integer computation cost.

  • The input and returned integer are not counted in the auxiliary-space figure.

Explicit-Stack Alternative

Because Python’s default recursion limit is approximately 1,000—it can be inspected with sys.getrecursionlimit()—and Python has no tail-call optimization, an explicit stack avoids RecursionError for large inputs:

def factorial_iterative(number: int) -> int:
    """Calculate factorial using an explicit stack."""
    if isinstance(number, bool) or not isinstance(number, int):
        raise TypeError("number must be an integer")
    if number < 0:
        raise ValueError("factorial is undefined for negative numbers")

    stack: list[tuple[int, int]] = [(number, 1)]

    while stack:
        remaining, accumulator = stack.pop()

        if remaining == 0:
            return accumulator

        stack.append((remaining - 1, accumulator * remaining))

    raise RuntimeError("factorial calculation did not complete")


print(factorial_iterative(5))  # 120

The explicit-stack version takes O(n) time and O(1) auxiliary space because it pops the current entry before pushing its successor, leaving at most one stack entry at a time.

Common Pitfalls

  • Python has no tail-call optimization: A tail-recursive helper still consumes stack frames and can raise RecursionError for sufficiently large inputs.

  • Negative input: Factorial is undefined for negative integers, so reject them with ValueError.

  • Zero and one: Both are valid, and 0! = 1! = 1.

  • Invalid types: The implementation rejects non-integers and booleans rather than relying only on type hints.

  • Memoization: The accumulator version has no repeated subproblems, so memoization is unnecessary. A conventional recursive product also has no overlapping subproblems within one call; functools.cache helps only when the same factorial inputs are requested repeatedly.

  • Integer limits: In languages with fixed-width integers, factorial quickly overflows. Python supports arbitrary-precision integers, but memory and computation costs still increase rapidly.

  • Interview follow-ups: Interviewers may ask for an iterative implementation, validation of invalid input, explanation of why the accumulator preserves the result, or analysis of the recursion stack.

17

Can tail recursion outperform non-tail recursion across languages?

Tail recursion can use less stack space in languages that provide tail-call optimization (TCO). Python 3.12 does not optimize tail calls, so tail-recursive and comparable non-tail-recursive functions both retain one call-stack frame per recursive call.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Tail Calls Work

A function is tail-recursive when the recursive call is its final operation. Nothing needs to be calculated after that call returns.

For example, ordinary factorial recursion performs a multiplication after the recursive call:

return n * factorial(n - 1)

A tail-recursive version passes the accumulated result into the next call:

return factorial(n - 1, accumulator * n)

The difference is significant only when the language or runtime implements TCO:

  • With TCO: the current frame is reused, so the recursion stack remains constant.

  • Without TCO: Python stores a new frame for every call, regardless of whether the call is in tail position.

  • Time complexity: tail recursion is usually not faster asymptotically; its main benefit is reduced stack usage.

Complexity

Assuming constant-time integer arithmetic:

Implementation Best time Average time Worst time Auxiliary space
Python non-tail recursion O(n) O(n) O(n) O(n) recursion stack
Python tail-style recursion O(n) O(n) O(n) O(n) recursion stack
Tail recursion with TCO O(n) O(n) O(n) O(1) stack
Iterative equivalent O(n) O(n) O(n) O(1) stack

The space figures include the recursion or explicit stack but exclude the input. The integer input itself occupies O(1) space. Python’s default recursion limit is about 1,000, and Python has no tail-call optimization.

Call Stack Behavior

For factorial(3), non-tail recursion produces:

factorial(3)
└── factorial(2)
    └── factorial(1)
        └── factorial(0) → 1
            ← 1
        ← 1 × 1
    ← 2 × 1
← 3 × 2

Each call moves one step closer to the base case at n = 0.

The tail-style version behaves similarly in Python:

factorial_tail(3)
└── accumulate(2, 3)
    └── accumulate(1, 6)
        └── accumulate(0, 6) → 6

In a TCO-enabled runtime, each accumulate frame would replace the previous frame rather than remain on the stack.

Code Example

def factorial(n: int) -> int:
    """Calculate factorial using non-tail recursion."""
    if n < 0:
        raise ValueError("n must be non-negative")

    if n == 0:
        # Base case: the recursive calls have reached zero.
        return 1

    # Recursive case: n decreases toward the base case.
    return n * factorial(n - 1)


def factorial_tail(n: int) -> int:
    """Calculate factorial using tail-recursive-style calls."""
    if n < 0:
        raise ValueError("n must be non-negative")

    def accumulate(remaining: int, accumulator: int) -> int:
        if remaining == 0:
            # Base case: return the accumulated factorial.
            return accumulator

        # Recursive case: remaining decreases toward the base case.
        return accumulate(remaining - 1, accumulator * remaining)

    return accumulate(n, 1)


def factorial_iterative(n: int) -> int:
    """Calculate factorial using an explicit stack without recursion."""
    if n < 0:
        raise ValueError("n must be non-negative")

    stack: list[tuple[int, int]] = [(n, 1)]

    while stack:
        remaining, accumulator = stack.pop()

        if remaining == 0:
            # Base case: the accumulated factorial is complete.
            return accumulator

        # Replace the pending state with the next state.
        stack.append((remaining - 1, accumulator * remaining))

    raise RuntimeError("Unreachable state")


print(factorial(5))           # Output: 120
print(factorial_tail(5))      # Output: 120
print(factorial_iterative(5))  # Output: 120

For this particular tail recurrence, the explicit stack contains at most one pending state, so it uses O(1) auxiliary space. A direct accumulator loop would be simpler and equally valid.

Common Pitfalls

  • Assuming Python performs TCO: Python 3.12 does not; every recursive call consumes a stack frame.

  • Ignoring the recursion limit: factorial with inputs around 1,000 or greater can raise RecursionError. Use an iterative implementation for large inputs.

  • Raising the limit indiscriminately: sys.setrecursionlimit() does not make recursion free and excessively high limits can cause a process crash.

  • Confusing tail position with TCO: syntactically placing a call last does not make a language optimize it.

  • Repeated subproblems: functools.cache can eliminate repeated computation, but it does not reduce recursion depth or provide TCO.

  • Edge cases: factorial defines 0! = 1, 1! = 1, and negative inputs are invalid.

18

Can every recursive function be rewritten without recursion?

Usually, yes: a terminating recursive computation can be simulated using an explicit stack instead of the language’s call stack. However, the iterative version may require extra state, may not be simpler, and does not necessarily use less memory.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Recursion works by creating a new stack frame for each call. When the function returns, that frame is removed and its result is passed back to the caller.

An iterative rewrite replaces those frames with data stored in a collection such as list or collections.deque:

  • Arguments and local state: Store everything needed to resume the call.

  • Return address: Store which operation should happen after the simulated call finishes.

  • Base case: Process it directly rather than pushing another frame.

  • Recursive case: Replace the recursive call with a stack push and continue the loop.

A simple loop with an accumulator is preferable when the recursion is tail recursive, because the pending calls do not need to be preserved separately.

Call Stack and Complexity

For factorial(4), the recursive call stack is:

  • factorial(4)

  • factorial(3)

    • factorial(2)

    • factorial(1)

      • factorial(0) — base case, returns 1

Each call moves toward the base case by reducing n by one.

For factorial, the best, average, and worst-case time complexity are all O(n):

  • Recursive version: O(n) time because it makes n recursive calls.

  • Explicit-stack version: O(n) time because each level is pushed and popped once.

  • Accumulator-loop version: O(n) time with O(1) auxiliary space.

Space complexity includes the recursion stack and excludes the input itself:

  • Recursive version: O(n) auxiliary space for the call stack.

  • Explicit-stack version: O(n) auxiliary space for pending stack frames.

  • Accumulator-loop version: O(1) auxiliary space.

For a general recursive algorithm, replace n with the maximum recursion depth h; the explicit stack usually requires O(h) additional space.

Choosing an Approach

Approach Time Auxiliary space When to use
Direct recursion O(n) for factorial O(n) The recursive structure is clear and depth is safe
Explicit-stack iteration O(n) for factorial O(n) General recursion must be simulated without recursion
Accumulator iteration O(n) for factorial O(1) Tail recursion or a simple linear process
Memoized recursion Depends on repeated subproblems O(number of cached states) plus the stack Recursive calls repeat and caching improves performance

When calls repeat, Python 3.12’s functools.cache can avoid recomputing identical subproblems. It does not remove recursion, but it can substantially reduce repeated work.

Common Pitfalls

  • Do not assume conversion improves complexity: replacing recursion with an explicit stack usually preserves O(h) stack space.

  • Python 3.12 has no tail-call optimization: a tail-recursive function still consumes stack frames.

  • Python’s default recursion limit is about 1000: deep recursive solutions may raise RecursionError; check it with sys.getrecursionlimit().

  • Preserve the base case: the iterative version must explicitly handle the condition that stops the original recursion.

  • Watch for infinite recursion: if the original function never reaches its base case, an equivalent iterative program will generally also fail to terminate.

  • Prefer simple iteration for linear recursion: an explicit stack is valuable for tree or graph traversals, but it is unnecessary for ordinary loops.

In interviews, the strongest answer is: any ordinary terminating recursive algorithm can be simulated without recursion by replacing call frames with an explicit stack, but the rewrite may be more complex and will not automatically reduce time or space complexity.

19

How do you convert a recursive function to iteration in Python?

Convert recursion to iteration by replacing the implicit call stack with an explicit stack of frames. Each frame stores the state needed to resume processing after a recursive call returns; since no specific recursive function was provided, factorial demonstrates the general technique.

Read full answer

Applies toPython 3.12

Conversion Pattern

To rewrite a recursive function:

  1. Identify the base case: This becomes the condition that finalizes a frame.

  2. Identify the recursive case: Determine what state must be preserved between calls.

  3. Represent each call as a frame: Store values such as the current input, accumulators, or completion status.

  4. Use a LIFO stack: Python’s list provides LIFO behavior through append() and pop().

  5. Push continuation work before child work: This ensures the child frame is processed first, matching recursive evaluation order.

For a function with several recursive branches, each frame may also need to record which branch or traversal state should be processed next.

Edge Cases

  • Zero: factorial(0) returns 1 because 0! = 1.

  • Negative input: Both functions raise ValueError because factorial is defined here only for non-negative integers.

  • Deep recursion: The recursive version can raise RecursionError near Python’s recursion limit, while the explicit-stack version avoids the Python call-depth limit but still uses O(n) stack entries.

Code Example

def factorial_recursive(number: int) -> int:
    """Return the factorial of a non-negative integer recursively."""
    if number < 0:
        raise ValueError("number must be non-negative")

    # Base case: 0! equals 1.
    if number == 0:
        return 1

    # Recursive case: number decreases toward the base case.
    return number * factorial_recursive(number - 1)


def factorial_iterative(number: int) -> int:
    """Return the factorial of a non-negative integer using a stack."""
    if number < 0:
        raise ValueError("number must be non-negative")

    # Each frame contains (value, continuation_ready).
    stack: list[tuple[int, bool]] = [(number, False)]
    result = 1

    while stack:
        value, continuation_ready = stack.pop()

        if not continuation_ready:
            # Base case: the recursive call has returned 1.
            if value == 0:
                result = 1
            else:
                # Recursive case represented as a pending continuation
                # followed by the child frame.
                stack.append((value, True))
                stack.append((value - 1, False))
        else:
            # Resume the parent frame after its child has completed.
            result *= value

    return result


print(factorial_recursive(4))   # 24
print(factorial_iterative(4))   # 24

The boolean in each stack frame distinguishes entering a call from resuming it after the child returns.

Call Stack Walkthrough

For factorial(4), the recursive call stack is:

factorial(4)
└── factorial(3)
    └── factorial(2)
        └── factorial(1)
            └── factorial(0) -> 1

The calls then unwind, multiplying the base result by 1, 2, 3, and 4.

The iterative version performs the equivalent work through these stack states:

[(4, False)]
[(4, True), (3, False)]
[(4, True), (3, True), (2, False)]
[(4, True), (3, True), (2, True), (1, False)]
[(4, True), (3, True), (2, True), (1, True), (0, False)]

It reaches the base case, then resumes the pending frames to produce 24.

Complexity

Under the usual constant-time arithmetic model:

Approach Best time Average time Worst time Auxiliary space
Recursive factorial O(n) O(n) O(n) O(n) for the recursion stack
Explicit-stack factorial O(n) O(n) O(n) O(n) for the explicit stack
Factorial-specific accumulator loop O(n) O(n) O(n) O(1)

All three approaches perform n multiplications and process n+1 factorial states. The recursive version retains one live call frame per pending call, the explicit-stack version retains one list entry per pending frame, and the accumulator loop keeps only the current value and result. The input is excluded from auxiliary-space calculations.

Common Pitfalls

  • Incorrect push order: Push the continuation before the child frame, or the parent may resume too early.

  • Missing base case: The iterative version must explicitly finalize the same state as the recursive version.

  • Using pop(0): Removing from the front of a list is O(n); use pop() for LIFO stack behavior.

  • Ignoring recursion limits: Python’s default recursion limit is about 1,000 (sys.getrecursionlimit()), and Python has no tail-call optimization.

  • Losing per-frame state: Shared mutable accumulators can be incorrect for branching recursion; store separate state in each frame.

  • Repeated subproblems: If recursive calls repeat the same inputs, use functools.cache; converting to iteration alone does not reduce the number of repeated computations.

  • Fixed-width overflow: In languages such as Java or C++, factorial can overflow integer limits even though Python integers grow automatically.

20

How do you implement QuickSort iteratively with an explicit stack?

An iterative QuickSort replaces the program’s recursive call stack with an explicit LIFO stack. Instead of recursively sorting two subranges after partitioning, the algorithm pushes those ranges onto the stack and processes them later.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Model

A recursive QuickSort has two cases:

  • Base case: When low >= high, the range contains at most one element and is already sorted.

  • Recursive case: Partition the range around a pivot, then recursively sort the ranges to the pivot’s left and right.

The iterative version stores the pending (low, high) ranges in stack. It pushes the right range first so the left range is processed first, matching the usual left-before-right recursive execution order.

Partitioning Strategy

The example uses Lomuto partitioning with the last element as the pivot:

  1. Place the pivot at high temporarily.

  2. Move every value less than or equal to the pivot into the left partition.

  3. Swap the pivot with the first value in the right partition.

  4. Return the pivot’s final index.

  5. Schedule the two resulting ranges for later processing.

Each scheduled range is strictly smaller than its parent range, so processing continues toward the base case.

Code Example

def quick_sort_iterative(values: list[int]) -> list[int]:
    """Sort values in place using QuickSort and an explicit stack."""
    stack: list[tuple[int, int]] = [(0, len(values) - 1)]

    while stack:
        low, high = stack.pop()

        # Recursive base case: zero or one element is already sorted.
        if low >= high:
            continue

        # Recursive case: partition this range around its pivot.
        pivot = values[high]
        store_index = low

        for index in range(low, high):
            if values[index] <= pivot:
                values[store_index], values[index] = (
                    values[index],
                    values[store_index],
                )
                store_index += 1

        values[store_index], values[high] = values[high], values[store_index]
        pivot_index = store_index

        # These ranges move toward the recursive base case.
        # Push right first so the left range is processed first.
        if pivot_index + 1 < high:
            stack.append((pivot_index + 1, high))

        if low < pivot_index - 1:
            stack.append((low, pivot_index - 1))

    return values


numbers = [5, 2, 8, 1, 3]
print(quick_sort_iterative(numbers))  # [1, 2, 3, 5, 8]

Complexity

Case Time Auxiliary space Reason
Best O(n log n) O(log n) Balanced partitions produce O(log n) levels, each processing O(n) elements.
Average O(n log n) O(log n) Random pivot placement usually produces reasonably balanced partitions.
Worst O(n²) O(n) Repeatedly unbalanced partitions create quadratically many comparisons and may accumulate many pending ranges.
  • Time includes comparisons, swaps, and stack operations.

  • Auxiliary space excludes the input list and includes the explicit stack that replaces the recursion stack.

  • If the input list’s O(n) storage is counted, total space is O(n) in every case.

  • Empty and single-element inputs take O(1) time.

Walkthrough

For [5, 2, 8, 1, 3], the pending range is (0, 4):

  1. The pivot is 3.

  2. Partitioning produces [2, 1, 3, 5, 8], with the pivot at index 2.

  3. The pending ranges become (3, 4) and (0, 1).

  4. Because the stack is LIFO, (0, 1) is processed first and becomes [1, 2].

  5. Processing (3, 4) leaves [5, 8].

  6. The final result is [1, 2, 3, 5, 8].

The equivalent recursive call structure begins with quick_sort(0, 4), followed by quick_sort(0, 1) and quick_sort(3, 4); one-element ranges terminate at the base case.

Common Pitfalls and Interview Tips

  • Mutation: This implementation sorts the original list in place. Copy the list first if the caller needs the original order.

  • Duplicate values: Lomuto partitioning with <= handles duplicates correctly, but an input containing many equal values can degrade to O(n²). A three-way partition is preferable for such data.

  • Adversarial input: Choosing the last element as the pivot allows a sorted or specially arranged input to trigger the worst case. Randomized pivot selection reduces predictable attacks.

  • Stack order: Push the right range before the left range to preserve left-first recursive processing.

  • Python recursion: Python has no tail-call optimization and normally limits recursion depth to about 1,000. An explicit stack avoids RecursionError on deeply unbalanced input.

  • Common follow-up: Explain why the algorithm is in-place, whether it is stable, and how its performance changes with duplicate-heavy or nearly sorted data.

21

How do you convert recursive DFS to an iterative stack implementation?

Depth-first search (DFS) can be made iterative by replacing the runtime call stack with an explicit stack of DFS frames. Each frame stores a vertex and an iterator over its remaining neighbors, preserving the traversal order of the shown recursive implementation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Recursive DFS Works

Recursive DFS uses three pieces of state:

  • The current vertex.

  • A visited set that prevents cycles and duplicate processing.

  • The program’s call stack, which remembers where each recursive call should resume.

For each vertex, the algorithm records it, then recursively visits its unvisited neighbors in order. When a recursive call finishes, control returns to the previous call through the call stack.

Converting the Call Stack

Each recursive call can be represented by an explicit stack frame containing:

  • The current vertex.

  • An iterator positioned at the next neighbor to examine.

The algorithm repeatedly examines the top frame:

  1. If it has another neighbor, visit that neighbor if necessary.

  2. If the neighbor is new, record it and push a new frame.

  3. If the frame has no neighbors remaining, pop it and resume its parent.

This frame-based approach exactly preserves the recursive DFS preorder shown below. A simpler stack-of-vertices implementation may produce a different order unless neighbors are pushed in reverse, and it can contain duplicate pending vertices.

Code Example

from collections.abc import Iterator

Graph = dict[str, list[str]]


def recursive_dfs(graph: Graph, start: str) -> list[str]:
    """Return DFS preorder using recursion."""
    if start not in graph:
        return []

    visited: set[str] = set()
    order: list[str] = []

    def visit(vertex: str) -> None:
        """Visit a vertex and explore its reachable subtree."""
        # Base case: an already visited vertex has no new subtree to explore.
        if vertex in visited:
            return

        visited.add(vertex)
        order.append(vertex)

        # Recursive case: each call marks one new vertex, so it advances
        # toward finite termination.
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visit(neighbor)

        # Other base case: a vertex with no unvisited neighbors makes no
        # recursive call and returns to its parent.

    visit(start)
    return order


def iterative_dfs(graph: Graph, start: str) -> list[str]:
    """Return DFS preorder using an explicit stack of DFS frames."""
    if start not in graph:
        return []

    visited: set[str] = {start}
    order: list[str] = [start]

    # Each frame contains the current vertex and its remaining neighbors.
    stack: list[tuple[str, Iterator[str]]] = [
        (start, iter(graph.get(start, [])))
    ]

    while stack:
        vertex, neighbors = stack[-1]
        neighbor = next(neighbors, None)

        if neighbor is None:
            # This frame is exhausted, so resume its parent frame.
            stack.pop()
        elif neighbor not in visited:
            visited.add(neighbor)
            order.append(neighbor)
            stack.append((neighbor, iter(graph.get(neighbor, []))))

    return order


graph: Graph = {
    "Alpha": ["Beta", "Gamma"],
    "Beta": ["Delta"],
    "Gamma": ["Delta", "Epsilon"],
    "Delta": [],
    "Epsilon": [],
}

print(recursive_dfs(graph, "Alpha"))
# ['Alpha', 'Beta', 'Delta', 'Gamma', 'Epsilon']

print(iterative_dfs(graph, "Alpha"))
# ['Alpha', 'Beta', 'Delta', 'Gamma', 'Epsilon']

Example Walkthrough

The recursive call stack and iterative frame stack progress through equivalent states:

Recursive call stack Iterative frame stack Recorded order
visit(Alpha) (Alpha) Alpha
visit(Alpha) → visit(Beta) (Alpha), (Beta) Alpha, Beta
visit(Alpha) → visit(Beta) → visit(Delta) (Alpha), (Beta), (Delta) Alpha, Beta, Delta
visit(Alpha) → visit(Gamma) (Alpha), (Gamma) Alpha, Beta, Delta, Gamma
visit(Alpha) → visit(Gamma) → visit(Epsilon) (Alpha), (Gamma), (Epsilon) Alpha, Beta, Delta, Gamma, Epsilon

Complexity

Let reachable_vertices be the number of vertices reachable from start, reachable_edges be the number of edges involving reachable vertices, and max_depth be the maximum number of simultaneously active DFS frames.

Implementation Best time Average time Worst time Best additional space Average additional space Worst additional space
Recursive DFS O(1) O(V + E) O(V + E) O(1) O(V) O(V)
Iterative DFS O(1) O(V + E) O(V + E) O(1) O(V) O(V)
  • Time: Each reachable vertex is recorded once, and each adjacency-list entry of a reachable vertex is examined once. An undirected edge may appear in two adjacency lists, which does not change the O(V + E) bound.

  • Space: Excluding the returned result, both versions use O(V) auxiliary space for the visited set; the recursion stack or explicit frame stack alone uses O(max_depth). The returned order uses O(V) output space.

  • Input counting: The table excludes the input graph. Including the entire graph, including disconnected components, total space is O(V + E).

Common Pitfalls

  • Empty or missing start: Return an empty list when the graph is empty or start is absent.

  • Single isolated vertex: Return a list containing only that vertex.

  • Cycles and duplicate edges: Mark vertices when discovered so they are never processed twice.

  • Disconnected graphs: A single-start DFS visits only the start vertex’s component; use an outer loop over unvisited vertices to traverse every component.

  • Traversal order: A basic LIFO stack can differ from recursive order. Reverse pushes or use stack frames to preserve recursive preorder.

  • Recursion depth: Python’s default recursion limit is about 1000 and can be inspected with sys.getrecursionlimit(). Python has no tail-call optimization, so the iterative version avoids RecursionError on deep graphs.

  • Repeated neighbor visits: Use a visited set. functools.cache is generally unnecessary because graph traversal depends on mutable exploration state.

  • Typical follow-up: Interviewers may ask how to visit disconnected components, preserve recursive neighbor order, return paths rather than preorder, or detect cycles.

22

How do you convert a binary tree into a doubly linked list?

Inorder traversal converts a binary tree into a doubly linked list by linking each visited node to the previously visited node and the next node. In this Python example, prev and next hold the list links, so the tree’s left and right child relationships remain intact; implementations that repurpose those two pointers instead lose the original tree structure.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The standard inorder traversal visits nodes in the order:

  1. Left subtree

  2. Current node

  3. Right subtree

During the traversal, maintain:

  • head: the first node in the resulting list

  • previous: the last node already added to the list

For each visited node:

  • Set node.prev = previous.

  • Set previous.next = node if a previous node exists.

  • Otherwise, set head = node.

  • Update previous to the current node.

After traversal, set the final node’s next pointer to None. For a binary search tree, the resulting list is sorted by value. For an arbitrary binary tree, it follows inorder traversal order rather than numeric order.

Complexity

Let n be the number of nodes and h the tree height measured in edges.

Approach Best time Average time Worst time Auxiliary space
Recursive inorder O(n) O(n) O(n) O(h) for the recursion stack
Iterative inorder O(n) O(n) O(n) O(h) for an explicit stack

Time is O(n) in every case because each node is visited once and linked in O(1) time. Auxiliary space is O(h) because either traversal stack contains at most O(h) nodes. The input tree and the list links stored on its nodes are not counted as auxiliary traversal space.

In the worst case, a skewed tree has h = n - 1, so the auxiliary space is O(n).

Call Stack and Edge Cases

For the tree:

4
   / \
  2   5
 / \
1   3

The recursive calls begin as follows:

visit(4)
└── visit(2)
    └── visit(1)
        └── visit(None)  # base case

Each recursive call moves toward a None child, which is the base case. The right subtree is visited only after the current node has been linked.

The algorithm handles:

  • Empty tree: returns None.

  • One-node tree: returns that node with prev and next set to None.

  • Duplicate or negative values: values are preserved; no sorting or comparison is performed.

  • Already sorted binary search tree: the inorder result is already sorted.

  • Skewed tree: correct, but recursive implementations may approach Python’s default recursion limit of about 1000.

  • Disconnected or cyclic input: invalid as a binary tree; the algorithm assumes valid child links.

Code Example

from __future__ import annotations


class Node:
    __slots__ = ("value", "left", "right", "prev", "next")

    def __init__(
        self,
        value: int,
        left: Node | None = None,
        right: Node | None = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right
        self.prev: Node | None = None
        self.next: Node | None = None


def tree_to_doubly_linked_list(root: Node | None) -> Node | None:
    """Flatten a binary tree into a doubly linked list using inorder traversal."""
    head: Node | None = None
    previous: Node | None = None

    def visit(node: Node | None) -> None:
        nonlocal head, previous

        if node is None:
            # Base case: an empty subtree contributes no node.
            return

        # Recursive case: process the left subtree first.
        # Each call moves toward a None child, which is the base case.
        visit(node.left)

        node.prev = previous
        if previous is None:
            head = node
        else:
            previous.next = node
        previous = node

        # Recursive case: process the right subtree after linking this node.
        visit(node.right)

    visit(root)

    if previous is not None:
        previous.next = None

    return head


def tree_to_doubly_linked_list_iterative(root: Node | None) -> Node | None:
    """Flatten a binary tree using an explicit stack to avoid recursion depth limits."""
    head: Node | None = None
    previous: Node | None = None
    stack: list[Node] = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        current.prev = previous

        if previous is None:
            head = current
        else:
            previous.next = current

        previous = current
        current = current.right

    if previous is not None:
        previous.next = None

    return head


root = Node(
    4,
    left=Node(2, left=Node(1), right=Node(3)),
    right=Node(5),
)

head = tree_to_doubly_linked_list(root)
# Expected output: 1 <-> 2 <-> 3 <-> 4 <-> 5

Common Pitfalls

  • If reusing left and right as list links, save and process child pointers before overwriting them; this implementation instead uses prev and next and leaves child pointers unchanged.

  • Always initialize the first node’s prev to None and the last node’s next to None.

  • Remember that the operation mutates the input nodes.

  • Use the iterative version for very deep trees; Python has no tail-call optimization.

  • A common follow-up asks why inorder traversal is used: it produces the required linked-list order while visiting every node exactly once.

23

How do you reverse a linked list recursively?

Recursive reversal changes each node’s next pointer so that the list points in the opposite direction. The recursive call reverses the remaining list, after which the current node is attached to the tail of that reversed list.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a list such as 1 -> 2 -> 3 -> None, the algorithm proceeds as follows:

  1. If the list is empty or contains one node, return it unchanged. This is the base case.

  2. Recursively reverse the list beginning at head.next.

  3. The recursive call returns the new head of the reversed suffix.

  4. Set the old second node’s next pointer to head.

  5. Set head.next to None, making head the new tail.

Each recursive call advances one node toward the base case.

Relevant edge cases include:

  • Empty list: Returns None.

  • One node: Returns that node unchanged.

  • Duplicates and negative numbers: Values remain unchanged; only links are reversed.

  • Already sorted input: Its values appear in reverse sorted order.

  • Cyclic list: Requires cycle detection before reversal.

  • Disconnected graphs: Not applicable to singly linked-list reversal.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: Node | None = None


def reverse_linked_list_recursive(head: Node | None) -> Node | None:
    """Reverse a singly linked list by changing each node's next pointer."""
    # Base case: an empty list or one-node list is already reversed.
    if head is None or head.next is None:
        return head

    # Recursive case: reverse the suffix after the current node.
    # Progress toward the base case: each call advances to head.next.
    reversed_head = reverse_linked_list_recursive(head.next)

    # Attach the current node to the tail of the reversed suffix.
    head.next.next = head
    head.next = None

    return reversed_head


def reverse_linked_list_iterative(head: Node | None) -> Node | None:
    """Reverse a singly linked list using constant auxiliary pointer state."""
    previous: Node | None = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    return previous


def reverse_linked_list_with_stack(head: Node | None) -> Node | None:
    """Reverse a singly linked list using an explicit stack."""
    stack: list[Node] = []
    current = head

    while current is not None:
        stack.append(current)
        current = current.next

    if not stack:
        return None

    new_head = stack.pop()
    new_head.next = None
    previous = new_head

    while stack:
        current = stack.pop()
        current.next = previous
        previous = current

    return new_head


def list_values(head: Node | None) -> list[int]:
    """Return the values stored in a linked list."""
    values: list[int] = []
    current = head

    while current is not None:
        values.append(current.value)
        current = current.next

    return values


head = Node(1, Node(2, Node(3)))
reversed_head = reverse_linked_list_recursive(head)
print(list_values(reversed_head))  # Expected output: [3, 2, 1]

The recursive version is concise, but sys.getrecursionlimit() defaults to 1,000 and Python has no tail-call optimization. The explicit-stack version literally replaces the call stack, while the pointer-based iterative version is preferable for long lists because it uses only O(1) auxiliary space.

Complexity

For an acyclic list of n nodes:

Implementation Best time Average time Worst time Auxiliary space Reason
Recursive O(n) O(n) O(n) O(n) One call per node, with up to n calls on the stack.
Pointer-based iterative O(n) O(n) O(n) O(1) One traversal using a constant number of pointers.
Explicit-stack iterative O(n) O(n) O(n) O(n) Each node is pushed and popped once from the stack.

Auxiliary space excludes the input list. Including the existing input nodes, total memory usage is O(n) for every implementation because no new list nodes are created.

Call Stack and Example Trace

For 1 -> 2 -> 3 -> None, the recursive calls are:

  • reverse(node 1)

  • reverse(node 2)

    • reverse(node 3) — one-node base case; returns node 3.

During unwinding:

  1. The node 2 call sets node 3.next = node 2 and node 2.next = None.

  2. The node 1 call sets node 2.next = node 1 and node 1.next = None.

The result is 3 -> 2 -> 1 -> None.

Common Pitfalls

  • Off-by-one boundary: Treat one node as a base case. Using only the empty-list base case leaves head.next as None during unwinding and causes an error.

  • Forgetting to detach the old link: Setting head.next = None prevents a cycle.

  • Mutating the input: The algorithm reverses the original nodes in place; retain the returned head.

  • Ignoring recursion depth: A long list can raise RecursionError; use an iterative implementation.

  • Cycle detection and visited state: Ordinary reversal assumes an acyclic list and needs no visited set. If cycles are possible, detect them before reversal; otherwise recursion reaches its limit and pointer-based iteration loops indefinitely.

  • Integer overflow: Python integers are arbitrary precision. In fixed-width languages, use a sufficiently wide type for any auxiliary length counter; pointer reversal itself performs no value arithmetic.

  • Unnecessary memoization: The calls process different suffixes rather than repeating identical subproblems, so functools.cache does not help.

  • Typical follow-up: Interviewers may ask for the iterative solution, reversal between two nodes, palindrome detection, or reversing the first k nodes.

24

How do you sort a stack using recursion in Python?

The standard approach uses recursive insertion: recursively remove elements from the original stack, then insert each removed element into its correct position in a sorted stack. The stack is represented as a Python list whose last element is the top.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Sorting a stack with recursion requires two recursive operations:

  • Sorting recursion: Remove the top element, recursively sort the remaining stack, and insert the removed element afterward.

  • Insertion recursion: Compare the value with the current top. If the current top is larger, temporarily remove it, recursively insert the value, and then restore the removed element.

The implementation below sorts the stack in ascending order from bottom to top. It mutates the input list.

Recursion Trace

For an input stack [3, 1, 2], where 2 is the top, the recursive calls are:

  1. sort_recursive([3, 1, 2])

  2. sort_recursive([3, 1])

    • sort_recursive([3])

    • sort_recursive([]) — base case

  3. During unwinding, the removed values are inserted back:

  4. Insert 3 into [] → [3]

  5. Insert 1 into [3] → [1, 3]

  6. Insert 2 into [1, 3] → [1, 2, 3]

The insertion recursion may temporarily remove larger values before restoring them in the correct order.

Code Example

def sort_stack_recursive(stack: list[int]) -> list[int]:
    """Sort a stack in ascending order from bottom to top, in place."""

    def insert_sorted(values: list[int], value: int) -> None:
        # Base case: the stack is empty, or the value belongs at the top.
        if not values or values[-1] <= value:
            values.append(value)
            return

        # Recursive case: remove one larger top, moving toward the base case.
        removed_top = values.pop()
        insert_sorted(values, value)
        values.append(removed_top)

    def sort_recursive(values: list[int]) -> None:
        # Base case: zero or one element is already sorted.
        if len(values) <= 1:
            return

        # Recursive case: remove one element, moving toward the base case.
        value = values.pop()
        sort_recursive(values)
        insert_sorted(values, value)

    sort_recursive(stack)
    return stack


def sort_stack_iterative(stack: list[int]) -> list[int]:
    """Sort a stack using explicit auxiliary stacks instead of recursion."""
    sorted_stack: list[int] = []
    displaced: list[int] = []

    while stack:
        value = stack.pop()

        while sorted_stack and sorted_stack[-1] > value:
            displaced.append(sorted_stack.pop())

        sorted_stack.append(value)

        while displaced:
            sorted_stack.append(displaced.pop())

    stack.extend(sorted_stack)
    return stack


if __name__ == "__main__":
    recursive_values = [3, 1, 2]
    print(sort_stack_recursive(recursive_values))  # [1, 2, 3]

    iterative_values = [3, 1, 2]
    print(sort_stack_iterative(iterative_values))  # [1, 2, 3]

Complexity

Let n be the number of elements. Both versions have the following time complexity:

Case Time Reason
Best O(n) The input is already sorted bottom-to-top, so each value is inserted without removing larger elements.
Average O(n²) Insertion may move or recurse through a substantial portion of the stack for each element.
Worst O(n²) Reverse-sorted input causes each insertion to move through nearly all larger elements.
  • Recursive auxiliary space: O(n) for the recursive call stack; the input stack is not counted in this figure.

  • Total space including the input stack: O(n).

  • Iterative auxiliary space: O(n) for sorted_stack and displaced; the input stack is not counted in this figure.

  • The iterative version avoids Python’s recursion-depth limit.

Common Pitfalls

  • Python recursion limit: Python’s default recursion limit is about 1000, and Python does not optimize tail calls. Large stacks can raise RecursionError; use the explicit-stack version instead.

  • Stack direction: The last list element is treated as the top. Reversing the convention changes where elements are removed and inserted.

  • Input mutation: Both functions modify the supplied list. Copy it first if the caller must retain the original order.

  • Empty input: An empty stack is handled by the base case and remains empty.

  • One element: A stack containing one element is already sorted and remains unchanged.

  • Duplicate values: The recursive insertion uses <=, so equal elements retain their relative input order.

  • Negative numbers: Comparisons work directly on the values, so negative numbers sort normally.

  • Already sorted input: This is the best case and takes O(n) time.

  • Off-by-one errors: The base case must include both zero and one element.

  • Interview follow-up: Interviewers may ask why the algorithm is O(n²), how an explicit stack replaces recursion, and how a general comparison sort could improve the time complexity to O(n log n) if ordinary list operations are available.

25

How do you find the lowest common ancestor in a BST?

A lowest common ancestor (LCA) in a binary search tree is the deepest node whose subtree contains both target nodes. The BST ordering property lets the search follow only one branch at each level until the targets diverge or one target is reached.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

At the current node:

  • If both target values are smaller, continue into the left subtree.

  • If both are larger, continue into the right subtree.

  • Otherwise, the targets are on different sides, or one is the current node, so the current node is their LCA.

This assumes that both targets exist and that keys are unique. A node is considered an ancestor of itself.

Call Stack Trace

For this BST, with targets 2 and 4:

6
       / \
      2   8
     / \
    1   4
lowest_common_ancestor(6, 2, 4)
  Both values are below 6
  lowest_common_ancestor(2, 2, 4)
    The first target is the current node
    return 2

Each recursive call descends to a child subtree, reducing the remaining tree height by one and moving toward a base case.

Complexity

Let n be the number of nodes and h the tree height measured in edges.

Implementation Time Auxiliary space
Recursive Best O(1); average O(h); worst O(n) Best O(1); average O(h); worst O(n) for the recursion stack
Iterative Best O(1); average O(h); worst O(n) O(1) in all cases because the stack holds at most one pending node

For a balanced BST, h = O(log n). For a randomly generated BST, O(log n) is an expected bound. A completely skewed tree has h = O(n). The input tree itself is not counted.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class BSTNode:
    value: int
    left: BSTNode | None = None
    right: BSTNode | None = None


def lowest_common_ancestor(
    root: BSTNode | None,
    first: BSTNode,
    second: BSTNode,
) -> BSTNode | None:
    """Return the LCA of two existing nodes in a BST with unique keys."""
    # Base case: an empty subtree cannot contain a common ancestor.
    if root is None:
        return None

    # Base case: a target node is its own ancestor.
    if first is root or second is root:
        return root

    # Recursive case: both targets are smaller, so descend to the left.
    if first.value < root.value and second.value < root.value:
        return lowest_common_ancestor(root.left, first, second)

    # Recursive case: both targets are larger, so descend to the right.
    if first.value > root.value and second.value > root.value:
        return lowest_common_ancestor(root.right, first, second)

    # The targets diverge here, so the current node is their lowest ancestor.
    return root


def lowest_common_ancestor_iterative(
    root: BSTNode | None,
    first: BSTNode,
    second: BSTNode,
) -> BSTNode | None:
    """Return the LCA using an explicit stack instead of recursion."""
    stack: list[BSTNode] = [root] if root is not None else []

    while stack:
        current = stack.pop()

        if first is current or second is current:
            return current

        if first.value < current.value and second.value < current.value:
            if current.left is None:
                return None
            stack.append(current.left)
        elif first.value > current.value and second.value > current.value:
            if current.right is None:
                return None
            stack.append(current.right)
        else:
            return current

    return None


root = BSTNode(6)
root.left = BSTNode(2)
root.right = BSTNode(8)
root.left.left = BSTNode(1)
root.left.right = BSTNode(4)

ancestor = lowest_common_ancestor(root, root.left, root.left.right)
print(ancestor.value if ancestor is not None else None)  # 2

ancestor = lowest_common_ancestor_iterative(
    root, root.left, root.left.right
)
print(ancestor.value if ancestor is not None else None)  # 2

Edge Cases

  • Empty tree: Returns None.

  • One node: Returns the node when it is a target.

  • Same target twice: Returns that target.

  • Negative values: Work normally because ordering determines the branch.

  • Duplicate keys: Unsupported; duplicates can make value-based navigation ambiguous.

  • Missing targets: Not supported; the targets must exist, or the result may be misleading.

  • Already sorted input: Produces a valid but potentially skewed BST, making recursive depth O(n).

  • Disconnected graphs or cycles: Not valid BST inputs; the implementation assumes an acyclic tree.

Common Pitfalls

  • Count tree height in edges consistently to avoid off-by-one errors.

  • Python integers do not overflow; in fixed-width languages, use a type large enough for every key.

  • These functions do not mutate the input tree.

  • A visited set is unnecessary for a valid BST because ordering selects one branch; general-tree searches need one to prevent cycles.

  • Python’s default recursion limit is approximately 1,000, and Python has no tail-call optimization. Use the iterative version for potentially deep trees.

  • Common follow-ups include general binary trees, parent pointers, duplicate keys, and determining whether the LCA is one of the targets.

26

How do you recursively flatten a multilevel doubly linked list?

A tail-returning recursion can flatten the list by promoting each node’s child chain into its next chain. The approach preserves depth-first preorder: the current node, its flattened child list, then its flattened next list.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Assume each node has value, next, prev, and child pointers. The prev pointer is included because the question specifies a doubly linked list; omit it for the common next/child variant.

For every node, the recursive helper:

  1. Saves the original next and child pointers.

  2. Recursively flattens the next sublist and then the child sublist.

  3. Connects the flattened child list before the flattened next list.

  4. Removes the child pointer.

  5. Returns the tail of the flattened sequence so the caller can append another sequence in constant time.

The helper visits the next branch first, but step 3 links the child branch first, so the resulting sequence still follows depth-first preorder.

Call Stack Trace

For a list shaped like:

1 -> 2 -> 3
|
4 -> 5
|
6

The actual recursive calls are:

flatten(1)
├── flatten(2)
│   ├── flatten(3)
│   │   ├── flatten(None)  # base case: next
│   │   └── flatten(None)  # base case: child
│   └── flatten(None)      # base case: child
├── flatten(4)
│   ├── flatten(5)
│   │   ├── flatten(None)  # base case: next
│   │   └── flatten(None)  # base case: child
│   └── flatten(6)
│       ├── flatten(None)  # base case: next
│       └── flatten(None)  # base case: child

After linking the returned tails, the result is:

1 -> 4 -> 6 -> 5 -> 2 -> 3

Complexity

Let n be the number of nodes and h the longest path through next and child pointers.

Implementation Best, Average and Worst Time Auxiliary Space Input Counted?
Recursive, cycle-safe O(n) O(n) for the seen set, plus O(h) recursion stack No
Iterative with explicit stack O(n) O(n) for the stack and seen set No

For acyclic input, each node is processed once, so all three time cases are O(n). The list is modified in place; no new list nodes are allocated.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    prev: Node | None = None
    next: Node | None = None
    child: Node | None = None


def flatten_recursive(head: Node | None) -> Node | None:
    """Flatten a multilevel doubly linked list in depth-first preorder."""
    seen: set[int] = set()

    def visit(node: Node | None) -> Node | None:
        # Base case: an empty sublist has no nodes to flatten.
        if node is None:
            return None

        if id(node) in seen:
            raise ValueError("Cycle or shared node detected")

        seen.add(id(node))
        original_next = node.next
        original_child = node.child

        # Recursive case: process both smaller sublists.
        # Each call follows one pointer and eventually reaches the None base case.
        next_tail = visit(original_next)
        child_tail = visit(original_child)

        node.child = None

        if original_child is not None:
            node.next = original_child
            original_child.prev = node

            if child_tail is not None:
                child_tail.next = next_tail

            if original_next is not None and child_tail is not None:
                original_next.prev = child_tail

            return next_tail if next_tail is not None else child_tail

        node.next = next_tail

        if original_next is not None:
            original_next.prev = node

        return next_tail if next_tail is not None else node

    result = visit(head)

    if result is not None:
        result.prev = None

    return result


def flatten_iterative(head: Node | None) -> Node | None:
    """Flatten using an explicit stack to avoid Python's recursion limit."""
    if head is None:
        return None

    stack: list[Node] = [head]
    seen: set[int] = set()
    result_head: Node | None = None
    result_tail: Node | None = None

    while stack:
        node = stack.pop()

        if id(node) in seen:
            raise ValueError("Cycle or shared node detected")

        seen.add(id(node))
        next_node = node.next
        child_node = node.child

        node.prev = None
        node.next = None
        node.child = None

        if result_tail is None:
            result_head = node
        else:
            result_tail.next = node
            node.prev = result_tail

        result_tail = node

        # Push next first so child is processed first from the stack.
        if next_node is not None:
            stack.append(next_node)
        if child_node is not None:
            stack.append(child_node)

    return result_head


def to_values(head: Node | None) -> list[int]:
    values: list[int] = []
    current = head

    while current is not None:
        values.append(current.value)
        current = current.next

    return values


node_6 = Node(6)
node_5 = Node(5)
node_4 = Node(4, next=node_5, child=node_6)
node_5.prev = node_4
node_6.prev = node_4

node_3 = Node(3)
node_2 = Node(2, next=node_3)
node_3.prev = node_2

node_1 = Node(1, next=node_2, child=node_4)
node_2.prev = node_1
node_4.prev = node_1

flattened = flatten_recursive(node_1)
print(to_values(flattened))
# Expected output: [1, 4, 6, 5, 2, 3]

Common Pitfalls

  • Recursion depth: Python’s default recursion limit is about 1000, and Python has no tail-call optimization. Use flatten_iterative when the multilevel structure can be deeper.

  • Mutating pointers too early: Save next and child before changing either pointer.

  • Incorrect prev links: When inserting the child list, update both the child head’s prev and the next list head’s prev.

  • Empty or single-node lists: An empty list returns None; a single node remains unchanged.

  • Duplicates and negative values: They are preserved because flattening only changes pointers.

  • Already flat lists: Their order remains unchanged.

  • Cycles or shared nodes: The implementation raises ValueError; otherwise recursion would not reach its base case.

  • Disconnected roots: A single head covers one connected list. Flatten each independent root separately.

27

How do you recursively serialize and deserialize a binary tree?

Use preorder serialization with a marker for every null child. Serialization visits the current node, then its left subtree, then its right subtree; deserialization consumes those markers in the same order to reconstruct the tree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Node values alone do not identify the tree’s shape, so the format must encode missing children with a null marker such as #:

  • A node is written as its integer value.

  • A null subtree is written as #.

  • The format is value,left-subtree,right-subtree.

For example:

1
   / \
  2   3

serializes to 1,2,#,#,3,#,#. Deserialization reads the root, then recursively parses its left and right subtrees.

  • An empty tree serializes as #; a one-node tree serializes as value,#,#.

  • Duplicate and negative values are supported.

  • Sorted input and disconnected graphs do not apply to a binary tree.

  • Cycles and shared node references are invalid; the serializers detect repeated nodes and raise ValueError.

Complexity

For a tree containing n nodes and height h, measured in edges:

  • Time: O(n) in the best, average, and worst cases. Every node and null marker is processed once.

  • Space: O(n) total in all cases, counting serialized text, token buffers, and the O(n) visited-node set. The recursive stack or iterative traversal stack is O(h).

  • For a balanced tree, h is O(log n); for a completely skewed tree, it is O(n).

Call Stack and Recursion Depth

For the example above, serialization follows this pattern:

visit(1)
  visit(2)
    visit(None) -> "#"
    visit(None) -> "#"
  visit(3)
    visit(None) -> "#"
    visit(None) -> "#"

Each recursive call descends into a child subtree and eventually reaches the null base case. Python’s default recursion limit is approximately 1,000, and Python has no tail-call optimization, so deeply skewed trees should use an explicit stack.

Code Example

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        value: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def serialize(root: TreeNode | None) -> str:
    """Serialize a binary tree using preorder traversal and null markers."""
    output: list[str] = []
    visited_ids: set[int] = set()

    def visit(node: TreeNode | None) -> None:
        # Base case: a null subtree is encoded with one marker.
        if node is None:
            output.append("#")
            return

        node_id = id(node)
        if node_id in visited_ids:
            raise ValueError("Input must not contain cycles or shared nodes.")
        visited_ids.add(node_id)

        output.append(str(node.value))

        # Recursive case: descend into the left subtree, then the right.
        # Each call moves one level closer to the base case.
        visit(node.left)
        visit(node.right)

    visit(root)
    return ",".join(output)


def deserialize(data: str) -> TreeNode | None:
    """Deserialize a valid preorder serialization into a binary tree."""
    if not data:
        return None

    tokens = data.split(",")
    index = 0

    def build() -> TreeNode | None:
        nonlocal index

        marker = tokens[index]
        index += 1

        # Base case: consume a null marker and return no node.
        if marker == "#":
            return None

        # Recursive case: create the node, then parse both subtrees.
        # Each valid call advances to a child subtree and eventually reaches "#".
        node = TreeNode(int(marker))
        node.left = build()
        node.right = build()
        return node

    return build()


def serialize_iterative(root: TreeNode | None) -> str:
    """Serialize a binary tree without recursion."""
    output: list[str] = []
    visited_ids: set[int] = set()
    stack: list[TreeNode | None] = [root]

    while stack:
        node = stack.pop()

        if node is None:
            output.append("#")
            continue

        node_id = id(node)
        if node_id in visited_ids:
            raise ValueError("Input must not contain cycles or shared nodes.")
        visited_ids.add(node_id)

        output.append(str(node.value))
        stack.append(node.right)
        stack.append(node.left)

    return ",".join(output)


def deserialize_iterative(data: str) -> TreeNode | None:
    """Deserialize a valid preorder serialization without recursion."""
    if not data:
        return None

    tokens = data.split(",")
    if tokens[0] == "#":
        return None

    index = 0
    root = TreeNode(int(tokens[index]))
    index += 1

    # Each frame records the parent and which child must be read next.
    stack: list[tuple[TreeNode, str]] = [(root, "left")]

    while stack:
        parent, side = stack.pop()
        marker = tokens[index]
        index += 1

        if marker == "#":
            if side == "left":
                stack.append((parent, "right"))
            continue

        child = TreeNode(int(marker))
        if side == "left":
            parent.left = child
            stack.append((parent, "right"))
        else:
            parent.right = child

        stack.append((child, "left"))

    return root


root = TreeNode(1, TreeNode(2), TreeNode(3))
encoded = serialize(root)

print(encoded)                                           # 1,2,#,#,3,#,#
print(serialize(deserialize(encoded)))                   # 1,2,#,#,3,#,#
print(serialize_iterative(root))                          # 1,2,#,#,3,#,#
print(serialize_iterative(deserialize_iterative(encoded)))  # 1,2,#,#,3,#,#

Common Pitfalls

  • Missing null markers: Different tree shapes become indistinguishable.

  • String concatenation: Repeated result += token can take O(n²); collect tokens and join once.

  • Recursion overflow: A skewed tree exceeding roughly 1,000 levels can exceed Python’s default limit.

  • Invalid input: The deserializers assume valid serialized data; untrusted input needs explicit validation.

  • Follow-up questions: Interviewers commonly ask about alternative formats, tree height, preserving node identity, and replacing recursion with an explicit stack.

28

What is the recursive algorithm for finding the Nth Fibonacci number?

The Nth Fibonacci value can be computed using the Fibonacci recurrence, F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1. A direct recursive implementation is simple but repeats calculations, so memoization is normally recommended.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Each recursive call calculates two smaller Fibonacci values and adds them:

  • Base case: Return n when n is 0 or 1.

  • Recursive case: Return fibonacci(n - 1) + fibonacci(n - 2).

  • Both recursive calls use a smaller n, so they move toward the base case.

  • Negative indices are invalid and should raise an exception.

This definition uses zero-based indexing. If a sequence is described as 1, 1, 2, 3, 5, ..., its Nth term corresponds to F(N - 1) under this convention.

Code Example

from functools import cache


def fibonacci(n: int) -> int:
    """Return the nth Fibonacci number recursively, where F(0) = 0."""
    if n < 0:
        raise ValueError("n must be non-negative")

    # Base case: F(0) = 0 and F(1) = 1.
    if n <= 1:
        return n

    # Recursive case: both calls move toward the base case.
    return fibonacci(n - 1) + fibonacci(n - 2)


@cache
def fibonacci_memoized(n: int) -> int:
    """Return the nth Fibonacci number using memoized recursion."""
    if n < 0:
        raise ValueError("n must be non-negative")

    # Base case: F(0) = 0 and F(1) = 1.
    if n <= 1:
        return n

    # Recursive case: both calls move toward the base case.
    return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)


def fibonacci_iterative(n: int) -> int:
    """Calculate Fibonacci iteratively with O(1) space."""
    if n < 0:
        raise ValueError("n must be non-negative")

    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fibonacci(5))              # 5
print(fibonacci_memoized(50))    # 12586269025
print(fibonacci_iterative(50))   # 12586269025

Call Stack and Trace

For the direct implementation, fibonacci(5) creates the following recursive tree:

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1) = 1
│   │   │   └── fibonacci(0) = 0
│   │   └── fibonacci(1) = 1
│   └── fibonacci(2)
│       ├── fibonacci(1) = 1
│       └── fibonacci(0) = 0
└── fibonacci(3)
    ├── fibonacci(2)
    │   ├── fibonacci(1) = 1
    │   └── fibonacci(0) = 0
    └── fibonacci(1) = 1

The base-case calls return first. Their values are then added while the call stack unwinds, producing 5.

The direct implementation recalculates values such as fibonacci(2) many times. @cache (from functools) stores previously computed results so each Fibonacci value is calculated only once.

Complexity

The complexities below use the standard unit-cost arithmetic model. For n = 0 or n = 1, all implementations take O(1) time and space.

Approach Best time Average time Worst time Auxiliary space, including recursion stack
Direct recursion O(φ^n) O(φ^n) O(φ^n) O(n) for the stack
Memoized recursion O(n) O(n) O(n) O(n) for the cache and stack
Iterative (bottom-up) O(n) O(n) O(n) O(1)
  • φ is the golden ratio, approximately 1.618.

  • Direct recursion takes exponential time because the recursive tree contains exponentially many calls.

  • Memoized recursion calculates each of the n + 1 distinct states once.

  • The iterative version computes values in a loop, using constant space.

  • The input value itself is not counted in auxiliary space.

Common Pitfalls

  • Incorrect indexing: Clearly state whether F(0) = 0 or the sequence starts at index 1.

  • Repeated work: Use functools.cache unless exponential time is intentionally being demonstrated.

  • Recursion depth: Python’s default recursion limit is about 1000, and Python has no tail-call optimization. Memoized recursion can still exceed the limit for large n; use an iterative version instead of repeatedly raising the limit.

  • Negative input: Validate that n is non-negative.

  • Integer overflow in other languages: Use a sufficiently wide integer type when calculating large Fibonacci numbers.

  • Typical follow-up: Interviewers may ask for the iterative dynamic-programming solution, which also takes O(n) time but can use O(1) stored state when values are computed in order.

29

How can recursion calculate the sum of digits in Python?

A recursive digit-sum function repeatedly removes the last digit using modulo and adds that digit to the result obtained from the remaining number. The base case stops the recursion when the number becomes zero.

Read full answer

Applies toPython 3.12

How It Works

For a non-negative integer:

  1. number % 10 extracts the last digit.

  2. number // 10 removes the last digit.

  3. Add the extracted digit to the recursive result.

  4. When number == 0, return 0.

Using abs(number) makes the function work for negative integers as well. For example, -123 is treated as 123.

Code Example

def sum_digits(number: int) -> int:
    """Return the sum of the decimal digits of an integer."""
    number = abs(number)

    # Base case: zero contributes zero to the digit sum.
    if number == 0:
        return 0

    # Recursive case: add the last digit to the sum of the remaining digits.
    # Each call moves toward the base case because number // 10 is smaller.
    return number % 10 + sum_digits(number // 10)


# Example:
print(sum_digits(12345))  # Output: 15

Call Stack Trace

For sum_digits(123):

sum_digits(123)
├── 123 % 10 = 3
└── sum_digits(12)
    ├── 12 % 10 = 2
    └── sum_digits(1)
        ├── 1 % 10 = 1
        └── sum_digits(0)
            └── returns 0

The calls then return in reverse order:

sum_digits(1)  -> 1
sum_digits(12) -> 2 + 1 = 3
sum_digits(123) -> 3 + 3 = 6

Complexity

Let d be the number of decimal digits in the absolute value of the input.

  • Time: O(d) arithmetic operations in the best, average and worst cases under the usual unit-cost integer model. Each call performs one modulo, one division and one addition.

  • Arbitrary-precision detail: Python 3.12 integers have unbounded precision. When the cost is measured by digits or machine words, the modulo and division operations process progressively shorter integers, resulting in O(d²) total digit/word work in all cases.

  • Auxiliary space: O(d) stack frames under the unit-cost model, excluding the original input. If actual Python big-integer storage is counted, the simultaneously retained quotients require O(d²) bits in all cases because their lengths decrease one digit at a time.

Memoization is unnecessary because this function makes only one recursive call per level; repeated subproblems do not occur.

Edge Cases and Alternatives

  • Empty input: Python integers do not have an empty representation, so this case is not applicable.

  • Zero: sum_digits(0) returns 0.

  • One element: sum_digits(7) returns 7.

  • Negative numbers: The function calculates the digit sum of the absolute value.

  • Duplicates: Duplicate digits are included normally; for example, 112 returns 4.

  • Already sorted input: Digit order does not affect the result.

  • Very large numbers: Python 3.12’s default recursion limit is approximately 1000. An integer with around 1,000 decimal digits can exceed it and raise RecursionError. The following equivalent implementation uses an explicit stack instead of recursive calls:

def sum_digits_iterative(number: int) -> int:
    """Return the sum of decimal digits using an explicit stack."""
    # Each frame contains the remaining number and accumulated digit sum.
    stack: list[tuple[int, int]] = [(abs(number), 0)]
    total = 0

    while stack:
        remaining, accumulated = stack.pop()

        # Base case: all digits have been processed.
        if remaining == 0:
            total += accumulated
            continue

        # Represent the recursive call with another explicit stack frame.
        digit = remaining % 10
        stack.append((remaining // 10, accumulated + digit))

    return total


# Example:
print(sum_digits_iterative(12345))  # Output: 15

Common Pitfalls

  • Forgetting to use abs(number) causes negative inputs to produce negative results because Python’s modulo operator preserves the sign of the dividend.

  • Omitting the zero base case leads to unbounded recursion until Python raises RecursionError.

  • Assuming recursion depth is unlimited is unsafe in Python 3.12; Python does not implement tail-call optimization.

  • Interviewers may ask for an iterative version, how negative numbers are handled, or how to calculate the digit sum without converting the number to a string.

30

How do I implement recursive Merge Sort in Python?

Merge sort is a divide-and-conquer algorithm that recursively splits a list into smaller lists, sorts each half, and merges the sorted halves. Its implementation is naturally stable and guarantees O(n log n) time complexity.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Base case: A list with zero or one element is already sorted.

  2. Divide: Split the list into two approximately equal halves.

  3. Recurse: Sort each half independently until both reach the base case.

  4. Merge: Combine the sorted halves by repeatedly selecting the smaller front element.

For [3, 1, 2], the recursion proceeds as follows:

  • merge_sort([3, 1, 2])

  • Splits into [3] and [1, 2]

    • [1, 2] splits into [1] and [2]

    • Merging [1] and [2] produces [1, 2]

  • Merging [3] and [1, 2] produces [1, 2, 3]

The recursion depth is O(log n) because each call works with half as many elements. Python’s default recursion limit is about 1000, so Merge Sort’s logarithmic depth is normally not a concern. Python does not have tail-call optimization, but it is not needed here.

Complexity

Case Time Reason
Best O(n log n) Every level performs merging even if the input is already sorted.
Average O(n log n) There are O(log n) levels, with O(n) work per level.
Worst O(n log n) Each merge scans the combined elements once per level.
  • Auxiliary space: O(n) for slices, sorted halves, and merged lists.

  • Recursion stack: O(log n) and included in the auxiliary-space calculation.

  • Input accounting: The original input is excluded from the standard auxiliary-space measure. Including it still gives O(n) total space.

  • Stability: The implementation remains stable by choosing the left half when equal elements are encountered.

Code Example

def _merge(left: list[int], right: list[int]) -> list[int]:
    """Merge two sorted lists into one sorted list."""
    merged: list[int] = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        # Prefer the left list on equality to preserve stability.
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


def _merge_sort_recursive(values: list[int]) -> list[int]:
    """Sort a list recursively without modifying the original list."""
    # Base case: zero or one element is already sorted.
    if len(values) <= 1:
        return values.copy()

    midpoint = len(values) // 2
    left_values = values[:midpoint]
    right_values = values[midpoint:]

    # Recursive case: each call receives a smaller list and moves
    # toward the zero-or-one-element base case.
    left_sorted = _merge_sort_recursive(left_values)
    right_sorted = _merge_sort_recursive(right_values)

    return _merge(left_sorted, right_sorted)


def merge_sort(values: list[int]) -> list[int]:
    """Return a new list containing the values in ascending order."""
    return _merge_sort_recursive(values)


result = merge_sort([5, -2, 4, 4, 0, -1])
# Expected output: [-2, -1, 0, 4, 4, 5]

Edge Cases

  • Empty input: Returns [] through the base case.

  • One element: Returns a copy of that element.

  • Duplicates: Preserves the relative order of equal values.

  • Negative numbers: Are handled by ordinary numeric comparisons.

  • Already sorted input: Produces the same ordering in O(n log n) time.

  • Input mutation: The original list remains unchanged; returned lists contain the same references to immutable values.

Memoization with functools.cache does not improve this implementation because the recursive calls operate on disjoint sublists rather than repeating the same inputs.

Common Pitfalls

  • Incorrect partition boundaries: values[:midpoint] and values[midpoint:] include every element exactly once.

  • Unstable merging: Choosing the right half when values are equal can reverse the order of equivalent records; using <= preserves stability.

  • Mutating input unintentionally: The example returns a new list and leaves the caller’s list unchanged.

  • Overflow in other languages: Index-based implementations should calculate midpoints as left + (right - left) // 2 to avoid addition overflow in fixed-width integer languages.

  • Visited set: A visited set is not applicable because Merge Sort processes separate list segments rather than graph nodes.

  • Common follow-up questions: Interviewers often ask why the algorithm is stable, how it compares with quicksort, how bottom-up Merge Sort avoids recursion, or how it can be optimized for linked lists.

31

How can you recursively print every distinct permutation of a string in Python?

Backtracking builds a permutation one character at a time, marks each input position as used, and recurses with the next position. When all positions are filled, it prints the completed permutation; duplicate characters are skipped at the same recursion depth so each distinct result appears exactly once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm maintains:

  • characters: the sorted input characters.

  • path: the permutation currently being constructed.

  • used: a Boolean list indicating which input positions are already selected.

At each recursive call:

  1. If position == len(characters), the permutation is complete, so print path.

  2. Otherwise, try each character whose position is not already used.

  3. Append that character to path, mark its position as used, and recurse.

  4. After returning, remove the character and clear its used flag.

Every recursive call receives position + 1, so it moves toward the base case. Sorting makes the output deterministic and lexicographically ordered.

Call Tree and Example

For "ab":

backtrack(position=0)
└── backtrack(position=1)
    ├── backtrack(position=2)  # Prints "ab", then returns
    └── backtrack(position=2)  # Prints "ba", then returns
  1. At position 0, select "a".

  2. At position 1, select "b".

  3. At position 2, print "ab" and return.

  4. Backtrack to position 0, replace "a" with "b", and then select "a".

  5. At position 2, print "ba".

For "aab", duplicate skipping prevents equivalent choices at the same recursion depth. It still allows both "a" positions to be selected at different depths, producing "aab".

Code Example

def print_permutations(text: str) -> None:
    """Print every distinct permutation of text in lexicographic order."""
    characters = sorted(text)
    path: list[str] = []
    used: list[bool] = [False] * len(characters)

    def backtrack(position: int) -> None:
        # Base case: every position has been selected.
        if position == len(characters):
            print("".join(path))
            return

        # Recursive case: selecting a character moves toward the base case.
        for index, character in enumerate(characters):
            if used[index]:
                continue

            # Skip duplicate choices at the same recursion depth.
            if index > 0 and character == characters[index - 1] and not used[index - 1]:
                continue

            path.append(character)
            used[index] = True

            backtrack(position + 1)

            # Restore the state before exploring another branch.
            path.pop()
            used[index] = False

    backtrack(0)


print_permutations("aab")
# Expected output:
# aab
# aba
# baa

For long strings, an explicit stack avoids Python’s recursion-depth limit:

def print_permutations_iterative(text: str) -> None:
    """Print every distinct permutation of text without recursion."""
    characters = sorted(text)
    path: list[str] = []
    used: list[bool] = [False] * len(characters)

    # Frame: (position, next candidate index, selected character index).
    stack: list[tuple[int, int, int]] = [(0, 0, -1)]

    while stack:
        position, next_index, selected_index = stack[-1]

        if position == len(characters):
            print("".join(path))
            stack.pop()
            if selected_index != -1:
                path.pop()
                used[selected_index] = False
            continue

        if next_index == len(characters):
            stack.pop()
            if selected_index != -1:
                path.pop()
                used[selected_index] = False
            continue

        stack[-1] = (position, next_index + 1, selected_index)
        index = next_index

        if used[index]:
            continue
        if index > 0 and characters[index] == characters[index - 1] and not used[index - 1]:
            continue

        path.append(characters[index])
        used[index] = True
        stack.append((position + 1, 0, index))


print_permutations_iterative("aab")
# Expected output:
# aab
# aba
# baa

Complexity

Let n be the string length and P the number of distinct permutations.

  • Best, average, and worst-case time: O(n × P) for nonempty strings. There are P results, and constructing and printing each takes O(n) time. For distinct characters, P = n!.

  • Empty-string time: O(1), because the function prints one empty permutation.

  • Auxiliary space: O(n), including the recursion stack or explicit stack, path, and used. The input string is not counted.

  • Output cost: Printing all permutations requires at least Ω(n × P) time for nonempty strings.

Interview Tips

  • Edge cases: Empty input prints one blank permutation; one character prints once; duplicates produce only distinct arrangements; sorted input needs no special handling.

  • Recursion depth: The depth is O(n). Python’s default limit is approximately 1,000, so prefer an explicit stack for long inputs; raising it with sys.setrecursionlimit() can still exhaust the native stack.

  • Off-by-one errors: The base case is position == len(characters), not len(characters) - 1.

  • Integer overflow: Python integers do not overflow; fixed-width languages can overflow when calculating permutation counts.

  • Input mutation: sorted(text) creates a sorted copy and does not mutate the original string.

  • Used state: Use per-position state for the current path; a single global visited set would incorrectly prevent valid reuse at different depths.

  • Memoization: functools.cache is normally unnecessary here because these recursive branches do not repeat the same overlapping subproblem.

  • Follow-up: Interviewers commonly ask how to avoid duplicates, return a list instead of printing, generate results lazily, or replace recursion with an explicit stack.

32

How can recursion generate all valid balanced parentheses?

Balanced parentheses are strings in which every prefix contains at least as many opening parentheses as closing ones, and the total counts are equal. A recursive backtracking algorithm builds such strings by adding ( when openings remain and ) only when it cannot make the prefix invalid.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For n pairs of parentheses, maintain three values:

  • opening: Number of opening parentheses already used.

  • closing: Number of closing parentheses already used.

  • path: The current partial string.

The recursive function makes two possible decisions:

  1. Add ( if opening < n.

  2. Add ) if closing < opening.

The second condition prevents a prefix such as )( or ()) from being generated. When both counts reach n, the current path is a complete balanced string and is added to the results.

Every branch produces a unique result, so there are no duplicates. The number of possible results is the Catalan number:

[ C_n = frac{1}{n+1}binom{2n}{n} ]

Call Stack and Example

For n = 2, the recursion explores:

""
└─ "("
   ├─ "(("
   │  └─ "(()"
   │     └─ "(())"
   └─ "()"
      └─ "()("
         └─ "()()"

Each recursive call adds one character and moves closer to the base case where both counters equal n. The mutable path is popped after each branch, allowing the same storage to be reused.

Python has no tail-call optimization. The helper can reach 2n + 1 levels, and Python’s default recursion limit is about 1,000, so very large values of n may require an explicit-stack implementation.

Complexity

The number of results is (C_n), and each result contains 2n characters.

  • Time: Best, average, and worst case are all O(n · Cₙ). Each complete result must be copied into the output, so producing all results dominates the running time.

  • Auxiliary space: O(n), excluding the output. This includes the O(n) recursion stack and the O(n) shared path.

  • Output space: O(n · Cₙ) if the returned list is included.

  • The input is a single integer and occupies O(1) space, so it is not counted separately.

Memoization with functools.cache is not useful here: each branch contributes a distinct output, and the Catalan-sized result set dominates the work.

Code Example

def generate_balanced_parentheses(pairs: int) -> list[str]:
    """Return all balanced parenthesis strings containing the given pairs."""
    if pairs < 0:
        raise ValueError("pairs must be non-negative")

    results: list[str] = []
    path: list[str] = []

    def backtrack(opening: int, closing: int) -> None:
        # Base case: all pairs are used, so the current path is balanced.
        if opening == pairs and closing == pairs:
            results.append("".join(path))
            return

        # Recursive case: add "(" and move toward the base case.
        if opening < pairs:
            path.append("(")
            backtrack(opening + 1, closing)
            path.pop()

        # Recursive case: add ")" and move toward the base case.
        if closing < opening:
            path.append(")")
            backtrack(opening, closing + 1)
            path.pop()

    backtrack(0, 0)
    return results


print(generate_balanced_parentheses(2))
# Expected output: ['(())', '()()']

An explicit-stack version avoids Python’s recursion limit:

def generate_balanced_parentheses_iterative(pairs: int) -> list[str]:
    """Return all balanced parentheses using an explicit DFS stack."""
    if pairs < 0:
        raise ValueError("pairs must be non-negative")

    results: list[str] = []
    stack: list[tuple[str, int, int]] = [("", 0, 0)]

    while stack:
        current, opening, closing = stack.pop()

        if opening == pairs and closing == pairs:
            results.append(current)
            continue

        # Push the closing branch first so the opening branch is explored first.
        if closing < opening:
            stack.append((current + ")", opening, closing + 1))

        if opening < pairs:
            stack.append((current + "(", opening + 1, closing))

    return results


print(generate_balanced_parentheses_iterative(2))
# Expected output: ['(())', '()()']

The straightforward iterative version copies prefixes onto the stack, requiring O(n²) auxiliary space in the worst case. It still stores O(n · Cₙ) space for the returned results.

Common Pitfalls

  • Allowing invalid closing parentheses: Never add ) when closing == opening.

  • Off-by-one errors: pairs means pairs, so the final string contains 2 * pairs characters.

  • Incorrect base case: A result is complete only when both opening and closing counts equal pairs.

  • Ignoring recursion depth: Use an explicit stack or carefully adjust sys.setrecursionlimit() for unusually deep recursion.

  • Edge cases: pairs == 0 returns [""], pairs == 1 returns ["()"], and negative values raise ValueError.

  • Duplicate outputs: Each recursive decision sequence is unique, so no deduplication is necessary.

Typical follow-up questions ask why the answer count is Catalan, how to validate an existing parenthesis string, and how to adapt the algorithm to produce only unique combinations with additional symbols.

33

How can recursion solve the Skyline Problem?

The divide-and-conquer recursion solution computes skyline profiles for smaller groups of buildings, then merges those profiles by taking the maximum height over every overlapping interval. Each recursive call operates on a strictly smaller subset until it reaches a simple base case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach and Representation

This implementation uses the standard building representation (left, right, height), where each interval is half-open: [left, right).

The recursive process is:

  1. Sort buildings by their left coordinate.

  2. Divide them into two approximately equal groups.

  3. Recursively compute each group’s skyline profile.

  4. Merge the two profiles by examining their interval boundaries.

  5. Return the coordinates where the visible height changes.

A profile contains segments (start, end, height). Zero-height segments preserve gaps between buildings and ensure that overlapping buildings are handled correctly.

How the Recursive Merge Works

During merging, the next boundary is the earliest start or end strictly after the current position among the two profiles. At each resulting interval, the visible height is:

max(left_height, right_height)

For example, with buildings [(1,5,10), (2,6,15), (7,9,12)], the visible intervals are:

Interval Maximum height
[1,2) 10
[2,6) 15
[6,7) 0
[7,9) 12

The resulting critical points are [(1,10), (2,15), (6,0), (7,12), (9,0)].

The call structure for three buildings is:

  • profile([A, B, C])

  • profile([A]) reaches the base case.

  • profile([B, C])

    • profile([B]) reaches the base case.

    • profile([C]) reaches the base case.

    • Merge their profiles.

  • Merge the two resulting profiles.

Memoization is unnecessary because recursive calls operate on disjoint subsets rather than repeating identical subproblems.

Complexity

For n buildings:

Case Time Reason
Best O(n log n) Recursive list slicing and profile merging require O(n) work per level.
Average O(n log n) Sorting and merging take O(n log n) overall.
Worst O(n log n) Each merge is O(n), and the recursion has O(log n) levels.

Space: O(n) auxiliary, including temporary slices, merged profiles, and the recursion stack. The recursion stack itself is O(log n). The input list is not counted separately; the returned skyline can also contain O(n) points.

Code Example

from typing import TypeAlias

Building: TypeAlias = tuple[int, int, int]
Segment: TypeAlias = tuple[int, int, int]
Profile: TypeAlias = list[Segment]
Point: TypeAlias = tuple[int, int]


def _merge_profiles(left: Profile, right: Profile) -> Profile:
    """Merge two skyline profiles by taking their maximum height."""
    if not left:
        return right.copy()
    if not right:
        return left.copy()

    domain_start = min(left[0][0], right[0][0])
    domain_end = max(left[-1][1], right[-1][1])
    position = domain_start
    left_index = 0
    right_index = 0
    merged: Profile = []

    while position < domain_end:
        while left_index < len(left) and left[left_index][1] <= position:
            left_index += 1
        while right_index < len(right) and right[right_index][1] <= position:
            right_index += 1

        left_height = 0
        if (
            left_index < len(left)
            and left[left_index][0] <= position < left[left_index][1]
        ):
            left_height = left[left_index][2]

        right_height = 0
        if (
            right_index < len(right)
            and right[right_index][0] <= position < right[right_index][1]
        ):
            right_height = right[right_index][2]

        # Consider only boundaries strictly after the current position.
        boundaries = [domain_end]
        if left_index < len(left):
            start, end, _ = left[left_index]
            if start > position:
                boundaries.append(start)
            if end > position:
                boundaries.append(end)
        if right_index < len(right):
            start, end, _ = right[right_index]
            if start > position:
                boundaries.append(start)
            if end > position:
                boundaries.append(end)

        next_position = min(boundaries)
        visible_height = max(left_height, right_height)

        if merged and merged[-1][2] == visible_height:
            merged[-1] = (merged[-1][0], next_position, visible_height)
        else:
            merged.append((position, next_position, visible_height))

        position = next_position

    return merged


def _build_profile(buildings: list[Building]) -> Profile:
    """Recursively compute the visible height profile."""
    # Base case: an empty subset has no profile.
    if not buildings:
        return []

    # Base case: one building defines a single segment.
    if len(buildings) == 1:
        left, right, height = buildings[0]
        return [(left, right, height)]

    # Recursive case: split into two strictly smaller subsets.
    # Each recursive call therefore moves toward the base case.
    midpoint = len(buildings) // 2
    left_profile = _build_profile(buildings[:midpoint])
    right_profile = _build_profile(buildings[midpoint:])
    return _merge_profiles(left_profile, right_profile)


def solve_skyline(buildings: list[Building]) -> list[Point]:
    """Return the critical points of the skyline."""
    for left, right, height in buildings:
        if right <= left:
            raise ValueError("Each building must have right > left")
        if height < 0:
            raise ValueError("Building heights cannot be negative")

    if not buildings:
        return []

    # Sort a copy so the caller's input is not mutated.
    ordered = sorted(buildings, key=lambda item: (item[0], item[1], item[2]))
    profile = _build_profile(ordered)

    points: list[Point] = []
    previous_height = 0

    for start, end, height in profile:
        if height != previous_height:
            points.append((start, height))
            previous_height = height

    # Include the final descent to ground level when necessary.
    if previous_height != 0:
        points.append((profile[-1][1], 0))

    return points


# Expected: [(1, 10), (2, 15), (6, 0), (7, 12), (9, 0)]
print(solve_skyline([
    (1, 5, 10),
    (2, 6, 15),
    (7, 9, 12),
]))

Common Pitfalls

  • Off-by-one errors: Treat intervals as [left, right) so buildings sharing an endpoint do not incorrectly overlap.

  • Missing zero-height gaps: A skyline must fall to zero between disconnected buildings.

  • Mutating the input: Sorting a copy avoids surprising callers.

  • Edge cases: Empty input returns []; one positive-height building returns its start and end points; a zero-height building produces no visible points; duplicate and overlapping buildings are supported; negative heights are rejected.

  • Recursion depth: The depth is O(log n), so Python’s approximately 1000-call limit is not a practical concern, although Python has no tail-call optimization.

  • Large numeric values: In Java or C++, use sufficiently wide integer types for coordinates and heights to avoid overflow.

34

How do you implement recursive backtracking for Sudoku?

Recursive backtracking solves Sudoku by placing a valid digit in an empty cell, recursively solving the remaining board, and undoing that placement if the smaller board cannot be completed. A 9×9 puzzle requires at most 81 recursive placements, so its call stack is safely below Python’s default recursion limit of about 1,000.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

  1. Copy the puzzle so the caller’s input is not mutated.

  2. Find the first empty cell, represented by 0.

  3. Try each digit from 1 through 9.

  4. Accept a digit only if it does not conflict with its row, column, or 3×3 box.

  5. Recursively solve the board with that digit placed.

  6. If recursion fails, remove the digit and try the next candidate.

Backtracking is preferable to generating every possible filled board because invalid choices are rejected before deeper recursive calls.

Call Stack Trace

For a puzzle whose only empty cell requires 9:

solve()
└── Place 9 at (8, 8)
    └── solve()
        └── find_empty() returns None
            └── Base case: return True

If a deeper call fails, the stack unwinds. Each failed level resets its cell to 0 before returning False to the preceding level.

Complexity

Let m be the number of empty cells.

Approach Time Space When to use
Unconstrained enumeration O(81 × 9^81) O(81) Theoretical baseline only
Constraint-guided backtracking O(81 × 9^m) worst case O(81 + m) Practical Sudoku solver
  • Best time: O(81m) when the first candidate works at every level.

  • Average time: Instance-dependent and generally exponential in m; puzzle structure determines how much backtracking occurs.

  • Worst time: O(81 × 9^m), commonly written as O(9^m) for a fixed 9×9 board.

  • Auxiliary space: O(m + 81), including both the recursion stack and copied working board. The caller’s input is excluded from this count.

Generalized Sudoku has no known guaranteed polynomial-time solution. The minimum remaining values heuristic can improve practical performance by choosing the empty cell with the fewest legal candidates.

Code Example

def solve_sudoku(grid: list[list[int]]) -> list[list[int]] | None:
    """Solve a 9x9 Sudoku using 0 for blanks; return None if unsolvable."""
    size = 9

    if len(grid) != size or any(len(row) != size for row in grid):
        raise ValueError("The grid must contain exactly 9 rows and 9 columns.")

    puzzle = [row.copy() for row in grid]

    if any(type(value) is not int for row in puzzle for value in row):
        raise TypeError("Every cell must contain an integer.")
    if any(value < 0 or value > 9 for row in puzzle for value in row):
        raise ValueError("Cell values must be between 0 and 9.")

    def has_duplicate(values: list[int]) -> bool:
        seen: set[int] = set()
        for value in values:
            if value == 0:
                continue
            if value in seen:
                return True
            seen.add(value)
        return False

    for index in range(size):
        if has_duplicate(puzzle[index]):
            raise ValueError("The initial grid contains a duplicate row value.")
        if has_duplicate([puzzle[row][index] for row in range(size)]):
            raise ValueError("The initial grid contains a duplicate column value.")

        box_row = (index // 3) * 3
        box_col = (index % 3) * 3
        box_values = [
            puzzle[box_row + row_offset][box_col + column_offset]
            for row_offset in range(3)
            for column_offset in range(3)
        ]
        if has_duplicate(box_values):
            raise ValueError("The initial grid contains a duplicate box value.")

    def find_empty() -> tuple[int, int] | None:
        for row in range(size):
            for column in range(size):
                if puzzle[row][column] == 0:
                    return row, column
        return None

    def is_valid(row: int, column: int, candidate: int) -> bool:
        for index in range(size):
            if puzzle[row][index] == candidate:
                return False
            if puzzle[index][column] == candidate:
                return False

        box_row = (row // 3) * 3
        box_col = (column % 3) * 3
        for row_offset in range(3):
            for column_offset in range(3):
                if puzzle[box_row + row_offset][box_col + column_offset] == candidate:
                    return False
        return True

    def solve() -> bool:
        empty = find_empty()

        # Base case: no empty cells remain, so the board is solved.
        if empty is None:
            return True

        row, column = empty

        for candidate in range(1, size + 1):
            if not is_valid(row, column, candidate):
                continue

            puzzle[row][column] = candidate

            # Recursive case: each call fills one more cell and moves
            # toward the base case by reducing the number of blanks.
            if solve():
                return True

            puzzle[row][column] = 0

        return False

    return puzzle if solve() else None


puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]

print(solve_sudoku(puzzle))
# Expected output:
# [[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8],
#  [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3],
#  [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6],
#  [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5],
#  [3, 4, 5, 2, 8, 6, 1, 7, 9]]

Edge Cases and Best Practices

  • Empty grid: Contains many valid solutions; the function returns the first one found.

  • One empty cell: Recurses once and returns the completed board if the missing digit is valid.

  • Duplicates or invalid values: The function raises an error rather than attempting to repair an invalid initial grid.

  • Unsolvable puzzle: A structurally valid but unsatisfiable puzzle returns None.

  • Input preservation: Copying the grid prevents accidental mutation of the caller’s data.

  • Large generalized boards: Replace recursive calls with an explicit stack containing the current cell, candidate, and next candidate index. Python has no tail-call optimization.

Common Pitfalls

  • Forgetting to undo a placement: Without resetting the cell to 0, later branches explore invalid states.

  • Using an incorrect base case: Success is reached only when no empty cells remain, not merely when one row is complete.

  • Checking only rows and columns: Every candidate must also be checked against its 3×3 box.

  • Overlooking exponential backtracking: The minimum remaining values heuristic is a common follow-up optimization.

  • Ignoring recursion depth: It is safe for 9×9 Sudoku, but larger puzzles may require an explicit stack.

35

Find the K-th order statistic recursively in an unsorted list

Quickselect is a recursive selection algorithm that finds the K-th smallest element without fully sorting the list. Here, K is 1-based, and randomized pivoting with three-way partitioning handles duplicate values efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Strategy

The algorithm partitions the active range around a pivot:

  • Values smaller than the pivot form the less partition.

  • Values equal to the pivot form the equal partition.

  • Values larger than the pivot form the greater partition.

Only the partition containing the requested rank is searched recursively. If the rank lies in the equal partition, the answer is returned immediately because all values there are identical. Otherwise, the selected range is strictly smaller and moves toward the singleton base case.

Complexity and Alternatives

Approach Time Extra space When to use
Repeated minimum extraction Best/average/worst O(nK) O(1) Very small K or a simple implementation
Full sorting with Python list.sort Best O(n); average/worst O(n log n) O(n) temporary storage Multiple order statistics are needed
Randomized Quickselect Best/expected O(n); worst O(n²) Best O(1); expected O(log n); worst O(n) One order statistic is required

Repeated extraction performs K linear scans. Python’s Timsort recognizes sorted or reversed runs, giving its linear best case, while general sorting takes O(n log n) comparisons and temporary storage. Quickselect scans only the active partition; random pivoting gives expected linear total work and logarithmic recursion depth, but an unlucky pivot sequence can cause quadratic time and linear stack depth.

These space figures exclude the input list. Including the input, total storage is O(n).

Code Example

from random import Random


def kth_order_statistic(values: list[int], k: int) -> int:
    """Return the k-th smallest value, modifying values in place."""
    if not values:
        raise ValueError("values must not be empty")
    if not 1 <= k <= len(values):
        raise IndexError("k must be between 1 and len(values)")

    rng = Random()

    def select(left: int, right: int, rank: int) -> int:
        # Base case: one candidate remains, so it is the requested value.
        if left == right:
            return values[left]

        # Recursive case: partition the range and select only the
        # partition containing rank. Every call uses a smaller range
        # and therefore moves toward the base case.
        pivot = values[rng.randint(left, right)]
        less = current = left
        greater = right

        while current <= greater:
            if values[current] < pivot:
                values[less], values[current] = values[current], values[less]
                less += 1
                current += 1
            elif values[current] > pivot:
                values[greater], values[current] = values[current], values[greater]
                greater -= 1
            else:
                current += 1

        less_count = less - left
        equal_count = greater - less + 1

        if rank < less_count:
            return select(left, less - 1, rank)

        if rank < less_count + equal_count:
            return values[less]

        return select(
            greater + 1,
            right,
            rank - less_count - equal_count,
        )

    return select(0, len(values) - 1, k - 1)


values = [8, 3, 7, 1, 5, 2]
print(kth_order_statistic(values, 3))  # Expected output: 3

Call Stack and Trace

One possible sequence of randomized pivots is 7, 2, and 3 (the partitions are shown as the code leaves them):

select(0, 5, 2), pivot=7
├─ less=[2, 3, 1, 5], equal=[7], greater=[8]
└─ select(0, 3, 2), pivot=2
   ├─ less=[1], equal=[2], greater=[5, 3]
   └─ select(2, 3, 0), pivot=3
      ├─ less=[], equal=[3], greater=[5]
      └─ rank 0 is in the equal partition -> return 3

For an iterative version, use a LIFO stack containing (left, right, rank) tasks. Pop each task, return immediately for a singleton range, partition it, and push only the less or greater range containing the adjusted rank. This avoids Python’s approximately 1000-call recursion limit; Python has no tail-call optimization.

Common Pitfalls

  • Off-by-one errors: K is 1-based, while the internal rank is zero-based. The equal count is inclusive, and the greater range starts at greater + 1.

  • Mutating input: The code partitions the list in place. Copy it first if the original order must be preserved.

  • Duplicate values: Three-way partitioning prevents equal values from causing unnecessary recursion.

  • Invalid input: Empty lists and out-of-range K raise explicit exceptions.

  • Edge cases: One-element lists, negative values, duplicates, and already sorted inputs are handled correctly.

  • Recursion depth: Worst-case depth is O(n); use the explicit-stack version for very large inputs.

  • Memoization: It is unnecessary because recursive subproblems do not repeat.

  • Other languages: Use sufficiently wide integer types for indices and ranks, especially in fixed-width languages.

  • Common follow-up: Interviewers may ask about deterministic worst-case selection, avoiding input mutation, retrieving several order statistics, or implementing the iterative variant.

36

How do you recursively detect a cycle in an undirected graph?

Cycle detection in an undirected graph can be performed with a recursive depth-first search (DFS). During traversal, encountering a visited neighbor that is not the current node’s parent indicates a cycle.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each unvisited vertex, start a DFS and maintain a visited set:

  • Visit a vertex and mark it as visited.

  • For every adjacent vertex:

  • Ignore the parent, because the edge back to the parent is the same undirected edge used to arrive there.

  • If the neighbor is already visited, a cycle exists.

  • Otherwise, recursively visit the neighbor.

  • Run the outer search for every component so disconnected graphs are handled.

For example, in the triangle A-B-C-A, DFS may follow A → B → C. When C examines A, A is already visited and is not C’s parent, so a cycle is detected.

Memoization is not needed here because each vertex is processed only once through the visited set.

Call Stack Example

One possible recursion trace for a triangle is:

has_cycle(graph)
└── dfs(A, _NO_PARENT)
    └── dfs(B, A)
        └── dfs(C, B)
            └── C examines A
                └── A is visited and is not C's parent
                    └── return True

Each recursive call moves one edge deeper into the graph until it either finds a visited non-parent vertex or exhausts the connected component.

Code Example

The implementation below assumes a simple undirected graph: each edge is represented in both adjacency lists, and repeated entries in an adjacency list are treated as one edge.

from collections.abc import Hashable, Mapping, Sequence
from typing import Final, TypeVar

Vertex = TypeVar("Vertex", bound=Hashable)
_NO_PARENT: Final[object] = object()


def has_cycle(graph: Mapping[Vertex, Sequence[Vertex]]) -> bool:
    """Return whether a simple undirected graph contains a cycle."""
    visited: set[Vertex] = set()

    def dfs(node: Vertex, parent: object) -> bool:
        visited.add(node)

        for neighbor in set(graph.get(node, ())):
            if neighbor == parent:
                continue

            # Cycle condition: a visited non-parent neighbor proves a cycle.
            if neighbor in visited:
                return True

            # Recursive case: visiting an unvisited neighbor reduces the
            # unvisited vertices by one until the base case is reached.
            if dfs(neighbor, node):
                return True

        # Base case: all neighbors were exhausted without finding a cycle.
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, _NO_PARENT):
                return True

    return False


def has_cycle_iterative(graph: Mapping[Vertex, Sequence[Vertex]]) -> bool:
    """Return whether a simple undirected graph contains a cycle iteratively."""
    visited: set[Vertex] = set()

    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        stack: list[tuple[Vertex, object]] = [(start, _NO_PARENT)]

        while stack:
            node, parent = stack.pop()

            for neighbor in set(graph.get(node, ())):
                if neighbor == parent:
                    continue

                if neighbor in visited:
                    return True

                visited.add(neighbor)
                stack.append((neighbor, node))

    return False


triangle = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B"],
}

print(has_cycle(triangle))  # True
print(has_cycle_iterative(triangle))  # True

Complexity

Let V be the number of vertices and E the number of edges.

  • Time:

  • Best: O(1) when the first examined edge immediately proves a cycle, or for an empty graph or single isolated vertex.

  • Average: O(V + E), because each vertex and adjacency entry is processed once.

  • Worst: O(V + E), when the entire graph must be explored.

  • Auxiliary space: O(V), including the visited set and the recursion or explicit stack. The input graph, which occupies O(V + E) space, is not counted.

  • The recursive version can reach depth O(V). Python’s default recursion limit is about 1000, so the iterative version with an explicit stack is safer for very deep graphs.

Common Pitfalls

  • Skipping every visited neighbor prevents cycle detection. Only the parent should be ignored in a simple graph.

  • Forgetting to search every connected component can miss a cycle elsewhere in the graph.

  • Assuming the adjacency list is one-way produces incorrect results; undirected edges should appear in both endpoint lists.

  • Duplicate adjacency entries do not create a cycle in a simple graph. The implementation removes those duplicates with set.

  • Parallel edges require edge identifiers rather than only vertex names if a two-edge multigraph cycle must be detected.

  • Self-loops are correctly detected as cycles because the vertex is visited and is not its own parent.

  • Arbitrary hashable labels, including None, zero, and negative values, are supported because vertex identity, rather than numeric magnitude, determines adjacency.

37

How can I recursively generate all full binary trees with N nodes?

A full binary tree is one in which every node has either zero or two children. Recursively choose the left subtree’s size, derive the right subtree’s size, and combine every possible pair of subtrees; valid trees can exist only when N is odd.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Idea

For a tree containing size nodes:

  • The base case is size == 1, which produces a leaf.

  • The root consumes one node, leaving size - 1 nodes for its two children.

  • Both subtree sizes must be odd because each subtree is itself a full binary tree.

  • For every valid split, recursively generate all left and right subtrees and combine every pair.

The code treats the left and right children as distinct, so it enumerates ordered structural shapes. Node values are canonical preorder identifiers used to display the generated trees.

Complexity

For N = 2m + 1, the number of ordered full binary tree shapes is the Catalan number

[ C_m = frac{1}{m+1}binom{2m}{m}. ]

Case Time Space
Odd N > 0 O(N × C_m) O(N × C_m)
Even or non-positive N O(1) O(1)
  • Time reason: There are C_m results, each representing an N-node tree.

  • Space reason: The output contains O(N × C_m) node positions, and the recursion stack can reach O(N) depth. The input itself is O(1) and is not counted.

  • Best, average, and worst cases are the same because enumeration is deterministic and must produce every result.

Example Walkthrough

For N = 5, the possible root splits are 1 + 3 and 3 + 1:

build(5)
├── split 1 + 3
│   ├── build(1) → leaf
│   └── build(3)
│       ├── build(1) → leaf
│       └── build(1) → leaf
└── split 3 + 1
    ├── build(3)
    │   ├── build(1) → leaf
    │   └── build(1) → leaf
    └── build(1) → leaf

Each three-node subtree must split as 1 + 1, producing two ordered shapes overall.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(frozen=True)
class TreeNode:
    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def all_full_binary_trees(node_count: int) -> list[TreeNode]:
    """Return all ordered full binary tree shapes with node_count nodes."""

    def build(size: int, next_value: int) -> list[TreeNode]:
        if size == 1:
            # Base case: a single node is a leaf.
            return [TreeNode(value=next_value)]

        if size <= 0 or size % 2 == 0:
            # Base case: full binary trees cannot have even or non-positive size.
            return []

        trees: list[TreeNode] = []

        for left_size in range(1, size, 2):
            right_size = size - 1 - left_size

            # Recursive case: both child sizes are smaller than size,
            # so every recursive call moves toward the size-1 base case.
            left_trees = build(left_size, next_value + 1)
            right_trees = build(right_size, next_value + 1 + left_size)

            for left in left_trees:
                for right in right_trees:
                    trees.append(
                        TreeNode(value=next_value, left=left, right=right)
                    )

        return trees

    return build(node_count, 1)


# Example call:
# print(all_full_binary_trees(3))
# [TreeNode(value=1, left=TreeNode(value=2, left=None, right=None),
#            right=TreeNode(value=3, left=None, right=None))]

Common Pitfalls

  • Incorrect split formula: The right subtree contains size - 1 - left_size nodes because the root consumes one node.

  • Only odd sizes: An even number of nodes cannot form a full binary tree.

  • Mirror duplicates: The code counts left/right mirror images as different ordered trees. Removing them requires an additional symmetry check.

  • Label interpretation: The values are canonical identifiers, not every possible permutation of user-supplied labels.

  • Repeated calls: Subtree sizes recur, so functools.cache can cache shape-only results by size. Copy cached results before allowing mutation.

  • Recursion depth: Python has no tail-call optimization, and sys.getrecursionlimit() is about 1000. For large inputs, use an explicit stack whose frames store the remaining split, child results, and processing phase.

  • Irrelevant cases: Empty, negative, one-element, duplicate, sorted, disconnected, and cycle inputs are either handled above or do not apply to this structure-generation problem.

  • Common follow-up: Interviewers often ask for the Catalan-number count, unordered-tree deduplication, labeled-tree generation, or an iterative stack-based implementation.

38

How does recursive divide and conquer work, with examples?

Divide and conquer is a recursive problem-solving strategy that splits a problem into smaller subproblems, solves them recursively, and combines their results. Recursion provides the mechanism for repeatedly applying the same solution until each subproblem reaches a simple base case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A divide-and-conquer algorithm generally follows three steps:

  1. Divide: Split the input into smaller, usually independent subproblems.

  2. Conquer: Recursively solve each subproblem, stopping at a base case.

  3. Combine: Combine the subproblem results into the final answer.

Recursion and divide and conquer are related but not identical. Recursion means a function calls itself; divide and conquer describes how those calls are used to solve a problem. Some recursive algorithms, such as naive recursive Fibonacci generation, are not divide and conquer because they repeatedly calculate the same overlapping subproblems.

Recurrence and Complexity

Merge sort demonstrates the typical divide-and-conquer recurrence:

  • Divide: Split n elements into two groups of approximately n / 2.

  • Conquer: Sort both groups, giving T(n) = 2T(n / 2) + O(n).

  • Combine: Merge the sorted groups in O(n) time.

The result is O(n log n) time. The recursion depth is O(log n) because each level halves the input size.

Common Examples

Algorithm Best time Average time Worst time Space, including recursion stack
Merge sort O(n log n) O(n log n) O(n log n) O(n) auxiliary storage plus O(log n) stack (algorithm); Python slicing version uses O(n log n) auxiliary
Binary search O(1) O(log n) O(log n) O(log n) stack for recursive implementations
Quicksort O(n log n) O(n log n) O(n²) O(log n) average or O(n) worst-case stack
Tower of Hanoi O(2ⁿ) O(2ⁿ) O(2ⁿ) O(n) stack

These space complexities exclude the input storage itself but include temporary storage and recursive calls. The merge sort implementation below uses list slicing, which creates new lists at each level, resulting in O(n log n) auxiliary space; an optimized version with a single temporary array can achieve O(n) auxiliary space. Binary search uses only O(log n) calls when it follows one branch per level.

Code Example

The following merge sort implementation recursively divides the list, sorts each half, and combines them.

def sort_values(values: list[int]) -> list[int]:
    """Sort integers in place with merge sort and return the list."""

    def merge_sort(items: list[int]) -> list[int]:
        # Base case: lists with fewer than two elements are already sorted.
        if len(items) < 2:
            return items

        # Recursive case: divide into two smaller lists and sort each one.
        # Progress: each recursive call receives fewer elements and reaches the base case.
        middle = len(items) // 2
        left = merge_sort(items[:middle])
        right = merge_sort(items[middle:])

        # Combine: merge the two sorted lists.
        merged: list[int] = []
        left_index = 0
        right_index = 0

        while left_index < len(left) and right_index < len(right):
            if left[left_index] <= right[right_index]:
                merged.append(left[left_index])
                left_index += 1
            else:
                merged.append(right[right_index])
                right_index += 1

        merged.extend(left[left_index:])
        merged.extend(right[right_index:])
        return merged

    sorted_values = merge_sort(values)
    values[:] = sorted_values
    return values


values = [3, -1, 3, 0, -1]
result = sort_values(values)
print(result)  # Output: [-1, -1, 0, 3, 3]

Call Stack Trace

For merge_sort([3, 1, 2]), the recursive calls are:

merge_sort([3, 1, 2])
├── merge_sort([3])
│   └── Base case
├── merge_sort([1, 2])
│   ├── merge_sort([1])
│   │   └── Base case
│   └── merge_sort([2])
│       └── Base case
└── Merge [1, 2] and [3] → [1, 2, 3]

Each recursive call moves toward the base case by reducing the number of elements. Once both halves are sorted, the combine step produces the final sorted list.

Edge Cases and Common Pitfalls

  • Empty input: The base case returns an empty list.

  • One element: No division or merging is required.

  • Duplicates: Merge sort preserves duplicates; it does not remove them.

  • Negative numbers: Numeric ordering works normally.

  • Already sorted input: Merge sort still takes O(n log n) time.

  • Mutating input: This implementation sorts the original list in place. Use a copy if the caller requires the original order.

  • Recursion depth: Python’s default recursion limit is approximately 1000, and Python has no tail-call optimization. Merge sort has only O(log n) depth, but algorithms with potentially large depth should use functools.cache when subproblems repeat or an explicit stack for iterative processing.

  • Repeated subproblems: If divide and conquer generates identical states, memoization with functools.cache can prevent repeated computation, at the cost of additional O(k) storage for k cached results.

  • Slicing overhead: The code uses list slicing (items[:middle], items[middle:]) which creates new lists at each recursive call. This makes the auxiliary space O(n log n) instead of the algorithmic O(n). For large inputs, consider an implementation that passes indices and uses a single temporary array.

39

How can recursion solve the Longest Common Subsequence problem?

The Longest Common Subsequence (LCS) is the longest sequence of characters appearing in two strings in the same relative order, without requiring the characters to be contiguous. A recursive solution compares characters, follows the optimal matching branch, and memoizes repeated subproblems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recurrence and Idea

Let L(i, j) be the LCS length for left[i:] and right[j:]:

  • If either string is exhausted, L(i, j) = 0.

  • If left[i] == right[j], match them: L(i, j) = 1 + L(i + 1, j + 1).

  • Otherwise, skip one character from either string: L(i, j) = max(L(i + 1, j), L(i, j + 1)).

Memoization prevents repeated evaluation of the same (i, j) state. functools.cache is a drop-in alternative when only the LCS length is required; the implementation below uses an explicit cache because reconstruction also needs the stored lengths.

Call Stack Trace

For left = "abc" and right = "ace", the recursive calls begin as follows:

solve(0, 0)  # a == a -> 2
└── solve(1, 1)  # b != c -> 1
    ├── solve(2, 1)  # c == c -> 1
    │   └── solve(3, 2) -> 0
    └── solve(1, 2)  # b != e -> 0
        ├── solve(2, 2) -> 0
        └── solve(1, 3) -> 0

Every recursive call advances at least one index toward the base case. The computed length is 2, and reconstruction returns "ac".

Complexity

Let m = len(left) and n = len(right).

Approach Best time Average time Worst time Space When to use
Naive recursion O(min(m, n)) Exponential; O(2^(m+n)) is a safe upper bound O(2^(m+n)) O(m + n) call stack Learning only
Memoized recursion O(min(m, n)) O(mn) O(mn) O(mn) cache plus O(min(m, n)) stack Recursive solution

The space figures are auxiliary and exclude the input strings; the returned subsequence adds O(min(m, n)). Each memoized state performs constant work, and there are at most (m + 1)(n + 1) states.

Code Example

def longest_common_subsequence(left: str, right: str) -> str:
    """Return one longest common subsequence of two strings."""
    memo: dict[tuple[int, int], int] = {}

    def solve(left_index: int, right_index: int) -> int:
        key = (left_index, right_index)
        if key in memo:
            return memo[key]

        # Base case: one string is exhausted.
        if left_index == len(left) or right_index == len(right):
            result = 0
        else:
            # Recursive case: every call advances toward the base case.
            if left[left_index] == right[right_index]:
                result = 1 + solve(left_index + 1, right_index + 1)
            else:
                result = max(
                    solve(left_index + 1, right_index),
                    solve(left_index, right_index + 1),
                )

        memo[key] = result
        return result

    solve(0, 0)

    result: list[str] = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] == right[right_index]:
            result.append(left[left_index])
            left_index += 1
            right_index += 1
        elif memo[(left_index + 1, right_index)] >= memo[
            (left_index, right_index + 1)
        ]:
            left_index += 1
        else:
            right_index += 1

    return "".join(result)


print(longest_common_subsequence("abc", "ace"))  # ac

Explicit Stack Alternative

Python’s default recursion limit is about 1000, available through sys.getrecursionlimit(), and Python does not optimize tail calls. For very long strings, simulate the recursive calls with an explicit stack:

def longest_common_subsequence_iterative(left: str, right: str) -> str:
    """Return one LCS using an explicit stack instead of recursion."""
    lengths: dict[tuple[int, int], int] = {}
    stack: list[tuple[int, int, bool]] = [(0, 0, False)]

    while stack:
        left_index, right_index, expanded = stack.pop()
        key = (left_index, right_index)

        if key in lengths:
            continue

        if left_index == len(left) or right_index == len(right):
            lengths[key] = 0
        elif expanded:
            if left[left_index] == right[right_index]:
                lengths[key] = 1 + lengths[(left_index + 1, right_index + 1)]
            else:
                lengths[key] = max(
                    lengths[(left_index + 1, right_index)],
                    lengths[(left_index, right_index + 1)],
                )
        else:
            stack.append((left_index, right_index, True))
            if left[left_index] == right[right_index]:
                stack.append((left_index + 1, right_index + 1, False))
            else:
                stack.append((left_index + 1, right_index, False))
                stack.append((left_index, right_index + 1, False))

    result: list[str] = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] == right[right_index]:
            result.append(left[left_index])
            left_index += 1
            right_index += 1
        elif lengths[(left_index + 1, right_index)] >= lengths[
            (left_index, right_index + 1)
        ]:
            left_index += 1
        else:
            right_index += 1

    return "".join(result)


print(longest_common_subsequence_iterative("abc", "ace"))  # ac

Common Pitfalls

  • Subsequence versus substring: skipped characters are allowed, but order must remain unchanged.

  • Missing base case: always return 0 when either index reaches its string’s length.

  • Repeated subproblems: memoize overlapping (i, j) states.

  • Off-by-one errors: matching advances both indices; skipping advances only one.

  • Input mutation: neither implementation modifies its arguments.

  • Edge cases: empty strings return ""; one-character strings and duplicates work naturally. Negative numbers and graph topology are not applicable to string LCS, and sorting inputs is incorrect because order affects the result.

40

How does recursion support greedy algorithm design?

Recursion can implement a greedy algorithm by repeatedly making the locally optimal choice and solving the smaller remaining problem. Recursion is only an implementation mechanism, however; it does not make an algorithm greedy or guarantee correctness—the chosen step must satisfy the greedy-choice property.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Role of Recursion

A recursive greedy solution generally follows this structure:

  1. Identify the best available choice.

  2. Apply that choice.

  3. Recursively solve the remaining subproblem.

  4. Stop at a base case.

This works when making the greedy choice preserves an optimal solution for the remaining problem. For example, with standard U.S. coin denominations, taking the largest usable coin is safe; an exchange argument can prove that the resulting number of coins is minimal.

Unlike recursive backtracking, a greedy recursion commits to one choice rather than exploring alternatives. Recursion is especially natural when a problem consists of repeated decisions on smaller instances. Many greedy algorithms, such as activity selection and some graph algorithms, are often clearer and avoid recursion-depth limits when implemented iteratively.

Recursive Call Structure

For coin change, the logical recurrence is:

G(amount) = [coin] + G(amount - coin)

The base case is G(0) = []. Each recursive call selects the largest usable denomination and decreases the remaining amount.

The public greedy_change function calls the nested build function, producing this trace:

  • build(30)

  • build(5) — selected 25 before recursing

    • build(0) — selected 5 before recursing; base case

Every recursive call moves toward the base case because the selected coin is positive.

Code Example

US_DENOMINATIONS: tuple[int, ...] = (25, 10, 5, 1)


def greedy_change(amount: int) -> list[int]:
    """Return greedy change using standard U.S. denominations."""
    if amount < 0:
        raise ValueError("amount must be non-negative")

    result: list[int] = []

    def build(remaining: int) -> None:
        # Base case: no money remains to change.
        if remaining == 0:
            return

        for coin in US_DENOMINATIONS:
            if coin <= remaining:
                # Recursive case: remaining becomes smaller each call.
                result.append(coin)
                build(remaining - coin)
                return

        raise ValueError("No valid denomination found")

    build(amount)
    return result


def greedy_change_iterative(amount: int) -> list[int]:
    """Return greedy change using an explicit stack."""
    if amount < 0:
        raise ValueError("amount must be non-negative")

    result: list[int] = []
    stack: list[int] = [amount]

    while stack:
        remaining = stack.pop()

        # Base case for the remaining subproblem.
        if remaining == 0:
            continue

        for coin in US_DENOMINATIONS:
            if coin <= remaining:
                result.append(coin)
                stack.append(remaining - coin)
                break
        else:
            raise ValueError("No valid denomination found")

    return result


print(greedy_change(30))           # [25, 5]
print(greedy_change_iterative(30))  # [25, 5]

Complexity

Let d be the number of coins selected and k the number of denominations.

  • Time: O(k × d) because each recursive call examines up to k denominations and appends one result element. With four fixed U.S. denominations, this is O(d).

  • Best case: O(1) for an amount of zero.

  • Average case: deterministic, so there is no separate average-case behavior.

  • Worst case: O(amount) because d can be Θ(amount), such as for amounts of the form 25m - 1.

  • Auxiliary space: the recursive version uses O(d) for the call stack. The iterative version uses O(1) auxiliary stack space because only one remaining amount is pending at a time.

  • Result space: both versions return an O(d) list. Total space is therefore O(d). The input itself is not counted.

Python’s default recursion limit is approximately 1000, and Python does not optimize tail calls. For large amounts, use the iterative version.

Common Pitfalls

  • Assuming recursion implies greediness: The algorithm must still prove that each greedy choice preserves global optimality.

  • Ignoring stack depth: Deep recursive chains can raise RecursionError; use an explicit stack when the depth may be large.

  • Applying greedy change to arbitrary denominations: Greedy is not optimal for every coin system, even when a valid combination exists.

  • Unnecessary memoization: This greedy chain does not repeat subproblems. If states do repeat, functools.cache may help, but that often indicates a dynamic-programming or backtracking problem rather than a pure greedy algorithm.

  • Mutating shared input: Keep greedy decisions in a result structure rather than modifying an original collection when callers may reuse it.

  • Edge cases: Amount 0 returns [], amount 1 returns [1], repeated denominations are allowed in the result, and negative amounts raise ValueError.

41

How does recursion implement backtracking in algorithm design?

Backtracking uses recursion to explore a sequence of choices, then undoes each choice before exploring the next alternative. Recursion supplies the call stack, while backtracking supplies the state restoration that makes exhaustive search with pruning possible.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Recursion Implements Backtracking

Each recursive call represents one partial solution and maintains the current state, such as a path, selected elements, or assigned positions.

  • Base case: The current state is complete, so record it as a solution.

  • Recursive case: Select an unused candidate, modify the state, and call recursively.

  • Undo step: Restore the state after the recursive call returns, allowing the next candidate to be explored.

  • Pruning: Skip a branch when it cannot produce a valid solution. A branch may also be evaluated by recursion without an explicit undo if its state is immutable.

The defining distinction from ordinary recursion is the undo step. Without it, sibling branches inherit state from previously explored branches.

Small Call-Stack Trace

For the values [1, 2]:

backtrack([])
├── choose 1 → backtrack([1])
│   └── choose 2 → backtrack([1, 2]) → record [1, 2]
│       undo 2, then undo 1
└── choose 2 → backtrack([2])
    └── choose 1 → backtrack([2, 1]) → record [2, 1]
        undo 1, then undo 2

The call stack returns after each branch, while path.pop() and counter restoration reset the shared state.

Approach Comparison

Approach Time Auxiliary Space When to Use
Brute-force permutation checking O(n · n!) O(n) Very small inputs with no useful pruning
Recursive backtracking O(n · n!) worst case O(n) General search problems, especially with constraint pruning

Backtracking is not asymptotically faster in the unconstrained worst case when every complete output must be materialized, but it reuses shared prefixes and can eliminate invalid branches early.

Complexity

Let n be the input size, d the number of distinct values, S the number of explored search states, and P the number of distinct outputs.

  • Recursive best case: O(n) when all values are identical, producing one permutation.

  • Recursive average case: O(dS + nP); each state examines at most d candidates, list append and end removal are amortized O(1), and each output copy costs O(n). There is no universal average without an input distribution.

  • Recursive worst case: O(n · n!) when all values are distinct, including materializing the outputs.

  • Recursive auxiliary space: O(n), including the recursion stack, current path, and frequency table; the input and returned results are excluded.

  • Explicit-stack best case: O(n²) when all values are identical because the implementation copies the growing path at every level.

  • Explicit-stack average case: O(nS + nP); there is no universal average without specifying an input distribution.

  • Explicit-stack worst case: O(n · n!) when all values are distinct, including materializing the outputs.

  • Explicit-stack auxiliary space: O(n³) in the worst case, excluding the input and returned results, because queued states retain copied paths and Counter maps.

  • Output space: O(nP) for either implementation, up to O(n · n!).

Code Example

from collections import Counter


def generate_unique_permutations(values: list[int]) -> list[list[int]]:
    """Return all distinct permutations of values."""
    remaining = Counter(values)
    result: list[list[int]] = []
    path: list[int] = []

    def backtrack() -> None:
        # Base case: a complete permutation has been constructed.
        if len(path) == len(values):
            result.append(path.copy())
            return

        # Recursive case: choose one value and move toward the base case.
        for value in remaining:
            if remaining[value] == 0:
                continue

            remaining[value] -= 1
            path.append(value)

            backtrack()

            # Undo the choice so another alternative can be explored.
            path.pop()
            remaining[value] += 1

    backtrack()
    return result


print(generate_unique_permutations([1, 1, 2]))
# Expected: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

An explicit stack can replace recursion when the depth may approach Python’s roughly 1000-call limit:

from collections import Counter


def generate_unique_permutations_iterative(
    values: list[int],
) -> list[list[int]]:
    """Return distinct permutations using an explicit depth-first stack."""
    stack: list[tuple[tuple[int, ...], Counter[int]]] = [
        ((), Counter(values))
    ]
    result: list[list[int]] = []

    while stack:
        path, remaining = stack.pop()

        if len(path) == len(values):
            result.append(list(path))
            continue

        for value in reversed(list(remaining)):
            if remaining[value] == 0:
                continue

            next_remaining = remaining.copy()
            next_remaining[value] -= 1
            stack.append((path + (value,), next_remaining))

    return result


print(generate_unique_permutations_iterative([1, 1, 2]))
# Expected: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Common Pitfalls

  • Forgetting to undo state causes later branches to use incorrect choices.

  • Incorrect base case may omit valid solutions or record incomplete ones.

  • Unsafe pruning can remove valid solutions; prune only when a branch is provably invalid.

  • Python recursion limit: sys.getrecursionlimit() is about 1000 by default, and Python has no tail-call optimization. Use an explicit stack for deeper traversals.

  • Edge cases: Empty input returns [[]]; one element returns [[value]]; duplicates produce distinct permutations; negative values work unchanged; already sorted input is valid and changes only traversal order.

  • Interview follow-up: Interviewers commonly ask how to add constraint checks, prune branches, and convert the recursive traversal into an explicit-stack implementation.

42

How does recursion enable dynamic programming with Fibonacci?

Dynamic programming uses recursion to solve a problem by defining results in terms of smaller subproblems and caching answers that have already been computed. Fibonacci is a classic example because each result depends recursively on the previous two results.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recurrence and State

For the zero-indexed Fibonacci sequence, let F(n) represent the Fibonacci number at position n:

  • Base cases: F(0) = 0 and F(1) = 1

  • Recursive case: F(n) = F(n - 1) + F(n - 2)

Each recursive call receives a smaller value, so it moves toward one of the base cases. However, plain recursion repeats calculations—for example, F(2) is computed while evaluating both F(3) and F(4).

Memoization with functools.cache ensures that each Fibonacci state is calculated only once.

Call Stack and Evaluation

For fibonacci(4), the recursive calls appear as follows:

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1) → 1
│   │   └── fib(0) → 0
│   │   result: 1
│   └── fib(1) → 1
│   result: 2
└── fib(2) → 1 (already cached)
    result: 3

The cache prevents fib(2) from being recalculated. This overlapping-subproblem structure is what turns an exponential recursive solution into a dynamic-programming solution.

Complexity

Assuming constant-cost integer arithmetic:

Approach Best time Average time Worst time Auxiliary space
Plain recursion O(φⁿ) O(φⁿ) O(φⁿ) O(n) recursion stack
Memoized recursion O(n) O(n) O(n) O(n) cache and O(n) recursion stack
Explicit-stack DP O(n) O(n) O(n) O(n) cache and O(n) stack
  • Memoized recursion time: Each state from 0 through n is computed once.

  • Auxiliary space: Includes the cache and call stack; the input itself is not counted.

  • The three cases have the same complexity because Fibonacci’s computation path is deterministic.

Python’s recursion limit is typically 1,000, accessible through sys.getrecursionlimit(), and Python does not optimize tail recursion. For very large n, an explicit stack avoids RecursionError.

Code Example

from functools import cache


def fibonacci(n: int) -> int:
    """Return the zero-indexed nth Fibonacci number using memoized recursion."""
    if n < 0:
        raise ValueError("n must be non-negative")

    @cache
    def fib(value: int) -> int:
        # Base case: recursion stops here.
        if value <= 1:
            return value

        # Recursive case: each call uses a smaller value and moves toward the base case.
        return fib(value - 1) + fib(value - 2)

    return fib(n)


def fibonacci_with_stack(n: int) -> int:
    """Return the nth Fibonacci number without using Python's call stack."""
    if n < 0:
        raise ValueError("n must be non-negative")

    memo: dict[int, int] = {0: 0, 1: 1}
    stack: list[tuple[str, int]] = [("visit", n)]

    while stack:
        action, value = stack.pop()

        if action == "combine":
            memo[value] = memo[value - 1] + memo[value - 2]
            continue

        if value in memo:
            continue

        if value <= 1:
            # Base case.
            memo[value] = value
            continue

        # Simulate the recursive calls, then combine their cached results.
        stack.append(("combine", value))
        stack.append(("visit", value - 1))
        stack.append(("visit", value - 2))

    return memo[n]


print(fibonacci(10))          # 55
print(fibonacci_with_stack(10))  # 55

Common Pitfalls

  • Repeated work: Plain recursion recalculates overlapping states; add memoization when subproblems repeat.

  • Incorrect base cases: Use F(0) = 0 and F(1) = 1 for the zero-indexed sequence.

  • Recursion depth: Memoization does not remove Python’s recursion-depth limit; use the explicit-stack version for large inputs.

  • Invalid input: Negative indices are rejected rather than silently producing an incorrect result.

  • Off-by-one errors: Clarify whether the problem expects F(0), F(1), or a one-indexed definition.

  • Stack implementation order: The explicit stack uses LIFO order, so the dependencies are pushed in reverse call order.

43

What is memoization, and how does it improve recursive algorithms?

Memoization is a caching technique that stores a function’s result for a particular set of inputs and reuses it when the same inputs recur. In recursive algorithms, it eliminates repeated computation by ensuring that each distinct subproblem is solved only once, trading additional cache space for lower running time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A memoized recursive solution normally follows these steps:

  1. Form a cache key representing the current inputs.

  2. Check whether the cache already contains a result for that key.

  3. If it does, return the cached result immediately.

  4. Otherwise, calculate the result through the recursive calls.

  5. Store the completed result in the cache before returning it.

Memoization is effective when:

  • The same subproblem is encountered repeatedly.

  • The subproblem always produces the same result for the same inputs.

  • The inputs can be represented by a stable, hashable cache key.

  • The cost of cache lookup and storage is less than the work avoided.

The cache prevents the body of a function from being recalculated for a previously seen state, although every subsequent occurrence still performs a cache lookup. Python 3.12 provides the functools.cache decorator for this purpose; it maintains an unbounded, process-local cache.

Recursive Call Tree

For Fibonacci numbers, the recurrence is F(n) = F(n - 1) + F(n - 2), with base cases F(0) = 0 and F(1) = 1. A memoized call tree for fibonacci(5) is:

  • fibonacci(5) — cache miss

  • fibonacci(4) — cache miss

    • fibonacci(3) — cache miss

    • fibonacci(2) — cache miss

      • fibonacci(1) — base case; returns 1 and is cached

      • fibonacci(0) — base case; returns 0 and is cached

    • fibonacci(1) — cache hit; returns 1

    • fibonacci(2) — cache hit; returns 1

  • fibonacci(3) — cache hit; returns 2

  • fibonacci(5) — returns 5

Each base-case result becomes available only after its call completes. The call stack holds active frames, while the cache retains completed results. Consequently, the memoized tree computes only the distinct states from fibonacci(0) through fibonacci(5), rather than recomputing them throughout the full recursive tree.

Complexity

Let S be the number of distinct states, L the total number of function invocations including cache hits, and D the maximum recursion depth.

Approach Time Auxiliary space Reason
Plain recursive Fibonacci Best, average and worst: O(φ^n) for n ≥ 2 O(n) recursion stack The call tree contains exponentially many calls; the stack depth is linear in n.
Memoized recursive Fibonacci Best and average: O(n); pathological worst: O(n²) O(n) cache plus O(n) recursion stack There are O(n) distinct states and lookups. Under pathological hash collisions, a lookup can cost O(n).
General memoization Best and average: O(S + L); pathological worst: O(S(S + L)) O(S + D) Each state is computed once, while cache lookup is expected to take O(1); collisions can make it O(S).

These are auxiliary-space figures and do not count the input itself. Under the usual expected constant-time dictionary-operation model, memoized Fibonacci runs in O(n) time.

Practical Guidance

  • Use deterministic functions: If a result depends on mutable external state, include that state in the cache key or avoid memoization.

  • Use stable keys: Mutable objects can change after being cached or may be unhashable.

  • Account for cache size: Memoization stores results for the lifetime of the cache and can consume substantial memory.

  • Handle deep recursion: Python has no tail-call optimization, and its default recursion limit is approximately 1000. For large depths, an explicit stack can hold pending states and completed results, or the recursion limit can be raised carefully.

  • Compare alternatives: When all dependencies are simple, bottom-up dynamic programming can offer similar time complexity without recursion-stack overhead.

Common Pitfalls

  • Assuming two different inputs always represent different subproblems, or that identical inputs always produce the same result.

  • Forgetting that cache hits still cost time and that cache storage increases space usage.

  • Claiming memoization makes every recursive algorithm linear; it does so only when the number of distinct states is small relative to the original call tree.

  • Using recursion without identifying the base case and explaining why every recursive call moves toward it.

  • Treating memoization as cycle detection; it does not automatically detect recursive cycles.

Interview Tips

Explain the cache key, the first lookup, the recursive computation, and where the completed result is stored. Then compare the plain and memoized call trees, state time and space complexity, and identify what belongs in the recursion stack versus the cache. Mention functools.cache for Python and explain how an explicit stack can replace deep recursion.

44

How does stack overflow affect recursion, and how can it be avoided?

Stack overflow occurs when recursive calls require more stack space than the runtime permits. Each active call occupies a stack frame, so unbounded or excessively deep recursion can raise RecursionError in Python or crash a process that uses the native call stack directly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Call Stack Works

When a function calls itself, the runtime creates a new stack frame containing information such as parameters, local variables, and the return address. The original frame remains active until the recursive call returns.

For factorial_recursive(4), the calls proceed as follows:

  1. factorial_recursive(4) calls factorial_recursive(3).

  2. factorial_recursive(3) calls factorial_recursive(2).

  3. factorial_recursive(2) calls factorial_recursive(1).

  4. factorial_recursive(1) calls factorial_recursive(0).

  5. The base case returns 1.

  6. Each recursive case multiplies its argument by the returned value, producing 24.

The base case is number == 0. The recursive case calls factorial_recursive(number - 1), so every call moves toward the base case.

Effects of Stack Overflow

  • Python: The interpreter normally raises RecursionError when its recursion limit is reached. In Python 3.12, sys.getrecursionlimit() defaults to about 1000.

  • Native-stack languages: Exceeding the native stack may terminate the process rather than produce a catchable exception.

  • Unbounded recursion: Increasing the limit does not repair a missing or unreachable base case; it only delays the failure.

  • Memory use: Recursion depth consumes memory proportional to the number of active frames.

  • Tail calls: Python has no tail-call optimization, so placing a recursive call in tail position does not remove stack frames.

  • Raising the limit: sys.setrecursionlimit() allows deeper Python recursion but does not enlarge the native stack, so an excessive limit can still crash the interpreter.

Avoiding Stack Overflow

  1. Use an explicit stack: Replace runtime call frames with a list-based stack.

  2. Put the initial state on the stack.

  3. Pop one state and process it.

  4. Push its unvisited successor states in the required order.

  5. Continue until the stack is empty.

  6. For graphs, mark vertices as visited when pushing them to prevent cycles from being processed repeatedly and to avoid duplicate stack entries.

  7. For disconnected graphs, start another traversal from each unvisited component.

This removes the dependency on Python’s recursion limit, although the explicit stack still needs memory: O(d) for a maximum depth of d when each step leaves one pending state (as in linear recursion), and up to O(V) for a graph traversal that pushes every unvisited successor.

  1. Guarantee a reachable base case: Every recursive path must make measurable progress toward it.

  2. Reduce recursion depth: Divide-and-conquer can change linear recursion into logarithmic recursion when its recurrence supports that transformation.

  3. Increase the limit carefully: sys.setrecursionlimit() is appropriate only for a known-safe depth that fits within the native stack.

  4. Memoize repeated work: functools.cache avoids recomputing overlapping subproblems, but it does not reduce the number of active recursive frames.

  5. Prefer iteration for large inputs: Iterative algorithms are generally easier to profile and do not depend on the runtime’s call-stack limit.

Complexity

For factorial, assuming constant-cost arithmetic:

Approach Time Auxiliary Space Reason
Recursive O(n) O(n), including the recursion stack There are n calls and multiplications, and one frame remains active per call
Iterative O(n) O(1) auxiliary variables There are n iterations, and only a fixed number of variables are maintained

The best, average, and worst cases have the same bounds for factorial. The input is not counted in auxiliary space, nor is the returned output; in Python, however, the returned arbitrary-precision integer and the cost of multiplication can grow with the result size.

Common Pitfalls

  • Missing base case: Infinite recursion eventually exhausts the stack.

  • Unreachable base case: The recursive argument must move toward termination.

  • Excessive limit increase: A larger limit can conceal a design problem and cause a native-stack crash.

  • Memoization confused with stack safety: Caching repeated calls does not shorten active recursion.

  • Missing visited state: An explicit-stack graph traversal can loop forever or revisit nodes without one.

  • Interview follow-up: Explain the base case, recursive case, maximum depth, stack-space cost, and an iterative alternative.

45

How does space complexity differ between iterative and recursive solutions?

Space complexity measures the total memory an algorithm uses relative to the input size, and it behaves differently for iterative and recursive solutions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Understanding Space Complexity

  • Auxiliary space: extra memory allocated beyond the input (variables, data structures, call stack).

  • Input space: memory holding the input; usually omitted from the analysis.

  • Recursion stack: each function call reserves space for return address, parameters, and local variables.

  • Big-O notation expresses how this memory grows as the input size n increases.

Space in Iterative Solutions

  • A simple loop that updates a few scalars uses O(1) extra space.

  • If the loop builds a new container (e.g., a list, a dictionary), the space grows with the number of elements stored, often O(n).

  • Iterative code never incurs call‑stack overhead, so it can process very large inputs without hitting a recursion limit.

Space in Recursive Solutions

  • Every recursive call adds a stack frame; for a recursion depth d the extra space is O(d).

  • Depth d can be n (linear recursion), log n (balanced divide‑and‑conquer), or the height of a tree.

  • Local variables and return values also consume memory.

  • Python’s default recursion limit is ~1000; exceeding it raises RecursionError.

  • Memoization (caching results) reduces time but adds O(n) space for the cache.

Comparing Iterative and Recursive Approaches

Approach Typical Extra Space When to Choose
Iterative (loop) O(1) to O(n) Simple transformations, large inputs, memory‑constrained environments
Recursive (direct) O(depth) Tree/graph traversal, backtracking, when code clarity is paramount
Explicit stack O(depth) Naturally recursive algorithms that need to avoid call‑stack limits
  • Recursive solutions are often shorter and mirror the problem’s structure, but they use more memory and can overflow.

  • Iterative solutions are usually faster (no call overhead) and use less memory, though they can be harder to write for inherently recursive problems.

Converting Recursion to Iteration

  • Simulate the call stack with an explicit list (push/pop).

  • This removes the risk of RecursionError but still uses O(depth) heap memory.

  • Example: depth‑first search can be written iteratively with a stack that holds (node, state) pairs.

Interview Tips

  • Clarify whether the recursion stack is included in the space analysis.

  • Remember that Python does not perform tail‑call optimization.

  • For deep recursion, either switch to an iterative version or raise the limit with sys.setrecursionlimit.

  • Be prepared to rewrite a recursive function iteratively if the interviewer asks.

  • Common follow‑up: “How can you reduce the space complexity?” (tail recursion, explicit stack, or a different algorithm).

46

What is Tail Call Optimization and which languages support it?

Tail Call Optimization (TCO) is a compiler or interpreter optimization that reuses a function’s stack frame when a recursive call occurs in tail position, preventing the call stack from growing. It is especially valuable in functional languages and for algorithms that would otherwise recurse thousands of levels deep.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A tail call is the final operation performed by a function: the function returns the recursive call’s result directly, as in return recursive_call(...). Because no work remains after the call returns, an implementation can reuse the current frame instead of retaining another one.

For example, in countdown(3), the call to countdown(2) is in tail position if its result is returned directly. By contrast, return countdown(n - 1) + 1 is not tail-recursive because the addition must execute after the recursive call returns, so the current frame must remain active.

TCO preserves the logical recursion while making the physical stack depth constant for the recursive chain. An implementation may reuse a frame, compile the pattern into a loop, or provide language-level support for proper tail calls.

Language Support

Language TCO support Notes
Scheme and Racket Proper tail calls are guaranteed Their execution models support tail-call optimization.
OCaml Supported Tail calls are optimized in both native and bytecode execution.
Erlang and Elixir Supported BEAM optimizes tail calls, so a tail-recursive chain does not grow the process stack.
Scala Supported for eligible tail calls The compiler handles eligible self tail calls; @tailrec verifies that optimization is possible.
Kotlin Supported for eligible self tail calls The tailrec modifier produces an error when the compiler cannot optimize the function.
Python 3.12 Not supported Python has no tail-call optimization, and its default recursion limit is about 1000.
Java 21 Not guaranteed Java has no general language-level TCO guarantee; use iteration for deep recursion.
C# Not guaranteed C# does not guarantee general tail-call elimination, so portable code must not depend on it.
JavaScript ES2023 Not guaranteed ES2023 specifies no TCO guarantee, so portable code must not depend on it.
Go Not guaranteed Go has no general TCO guarantee; use loops or an explicit stack for deep recursion.
Rust No stable general TCO Use iterative code or an explicit stack for potentially deep recursion.
C and C++ No language guarantee Some compilers optimize specific sibling calls, but portable code must not depend on TCO.

A language can provide an optimization without guaranteeing it for every program. Compiler flags, optimization levels, function visibility, and the specific call shape can affect whether an opportunistic optimization is applied.

Call Stack and Complexity

Consider a countdown that decreases n to zero. Without TCO, the logical calls and physical stack depth progress as follows:

Logical call Active stack depth
countdown(3) 1
countdown(2) 2
countdown(1) 3
countdown(0) 4

Each frame remains active until the base case returns, so the maximum depth is proportional to n. With TCO, the logical call sequence is unchanged, but the same physical frame is reused and the maximum stack depth remains constant.

For n > 0:

  • Time: O(n) in the best, average, and worst cases because each recursive step performs constant work and reduces the value by one. The base case takes O(1) time.

  • Auxiliary space without TCO: O(n) in the best, average, and worst cases because the recursion stack contains up to n + 1 frames.

  • Auxiliary space with TCO: O(1) in all cases because only a constant number of frames and local values are retained.

The input itself is not counted in these auxiliary-space figures. TCO changes stack usage, not the number of logical calls or the required computation.

Best Practices and Common Pitfalls

  • Prefer iteration for deep recursion: For linear tail recursion, use a loop that updates the state directly. For branching recursion, use an explicit stack containing pending work.

  • Do not assume every tail call is optimized: Check the language and compiler guarantees, and ensure the call is genuinely in tail position.

  • Watch for hidden non-tail work: Arithmetic after a call, cleanup performed afterward, or a finally handler may require the current frame to remain active.

  • TCO does not memoize: If calls repeatedly solve the same subproblem, use functools.cache or another memoization strategy.

  • Avoid raising Python’s recursion limit casually: sys.setrecursionlimit() can cause a native stack overflow before Python reports a recursion error.

  • Common interview follow-up: Identify whether a recursive function is tail-recursive, whether the language guarantees TCO, and how the solution behaves when recursion depth could be large.

47

Convert recursion to iterative with explicit stack

Explicit-stack iteration replaces recursive call frames with a manually managed stack, so deep inputs are not constrained by Python’s recursion limit. Each stack item stores the state a recursive frame would hold: arguments, local values, pending work, and sometimes a return stage.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Recursive call: Python stores each active call’s arguments, locals, and return position in a call frame. The default recursion limit is 1000 (sys.getrecursionlimit()).

  • Explicit frame: A stack item stores the current node or subproblem, accumulated results, and any information needed after its children finish.

  • Traversal order: For pre-order DFS, push the right child before the left child because a stack is last-in, first-out.

  • Post-processing: Use a stage flag when a node must be revisited after its children, such as in post-order traversal.

  • Repeated calls: Memoization with functools.cache can prevent repeated subproblem computation, but it does not remove the recursion-depth limitation.

Complexity - Time: O(n) in the best, average, and worst cases because each node is visited once. - Auxiliary space: O(h), where h is the binary tree’s height measured in edges. The output list is O(n) but is excluded from auxiliary space; the input tree is also excluded. - Space cases: O(log n) for a balanced tree, O(n) for a skewed tree, and shape-dependent on average.

Relevant edge cases include an empty tree returning [], a one-node tree returning its value, and duplicate or negative values being preserved. Sorted input does not apply to tree traversal. For graphs, cycles require a visited set and disconnected components require an outer search loop.

Comparison and Trace

Approach Time Auxiliary space When to use
Recursive DFS O(n) O(h) call stack When depth is within the recursion limit
Iterative DFS O(n) O(h) explicit stack Deep or unbalanced trees
BFS with a queue O(n) O(w) queue Level-order traversal

For pre-order traversal of a tree whose root is 1 with children 2 and 3:

  1. Push 1: stack [1].

  2. Pop 1, output 1, then push 3 and 2: stack [3, 2].

  3. Pop 2, output 2: stack [3].

  4. Pop 3, output 3: stack [].

The recursive call stack is:

  • visit(1)

  • visit(2)

    • visit(None) — base case

    • visit(None) — base case

  • visit(3)

    • visit(None) — base case

    • visit(None) — base case

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class TreeNode:
    """Binary tree node."""

    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def preorder_recursive(root: TreeNode | None) -> list[int]:
    """Return pre-order values using recursion."""
    result: list[int] = []

    def visit(node: TreeNode | None) -> None:
        """Visit a node and its descendants."""
        # Base case: no node remains.
        if node is None:
            return

        result.append(node.value)

        # Recursive case: each call descends one child toward the base case.
        visit(node.left)
        visit(node.right)

    visit(root)
    return result


def preorder_iterative(root: TreeNode | None) -> list[int]:
    """Return pre-order values using an explicit stack."""
    if root is None:
        return []

    result: list[int] = []
    stack: list[TreeNode] = [root]

    while stack:
        node = stack.pop()
        result.append(node.value)

        # Push right first so the left child is processed first.
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    return result


def postorder_iterative(root: TreeNode | None) -> list[int]:
    """Return left-right-root values using stack frames with stage flags."""
    if root is None:
        return []

    result: list[int] = []
    stack: list[tuple[TreeNode, int]] = [(root, 0)]

    while stack:
        node, stage = stack.pop()

        if stage == 0:
            # Revisit this node after both children have been processed.
            stack.append((node, 1))
            if node.right is not None:
                stack.append((node.right, 0))
            if node.left is not None:
                stack.append((node.left, 0))
        else:
            result.append(node.value)

    return result


if __name__ == "__main__":
    #       1
    #      / \
    #     2   3
    #    / \
    #   4   5
    tree = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )

    print(preorder_recursive(tree))    # [1, 2, 4, 5, 3]
    print(preorder_iterative(tree))    # [1, 2, 4, 5, 3]
    print(postorder_iterative(tree))   # [4, 5, 2, 3, 1]

    deep_tree = TreeNode(0)
    current = deep_tree
    for index in range(1, 2000):
        current.right = TreeNode(index)
        current = current.right

    print(len(preorder_iterative(deep_tree)))  # 2000

Common Pitfalls

  • Wrong push order: Push right before left for left-first DFS.

  • Missing None checks: Accessing a child or popped node that is None raises an exception.

  • Shared mutable paths: An iterative backtracking algorithm must explicitly restore or copy path state.

  • Incorrect stage handling: Schedule post-processing before pushing children, but append the node only after the children finish.

  • Unbounded memory: Explicit stacks avoid recursion limits but can still exhaust available memory.

  • Tail recursion: Python does not optimize tail calls, so use a loop or explicit stack for tail-recursive algorithms.

Interview Tips

  • For iterative in-order traversal, use a current pointer and stack: descend left, pop and visit, then move right.

  • For graph traversal, add a visited set and discuss disconnected components.

  • Explain what each stack item represents and how the iterative state corresponds to a recursive frame.

  • Mention that list.append() and list.pop() are O(1) amortized, so stack operations do not dominate traversal time.

48

How should recursive absolute value handle negative integers?

Use a zero base case and ensure the negative recursive branch moves toward zero. For an integer value, the negative case can recurse on -value - 1, which reduces its magnitude by one before eventually reaching the base case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Definition

The recursive absolute value function can be defined as:

  • absolute_value(0) = 0

  • For a positive value: absolute_value(value) = 1 + absolute_value(value - 1)

  • For a negative value: absolute_value(value) = 1 + absolute_value(-value - 1)

The negative branch is important: -value - 1 converts a negative integer into a smaller positive magnitude. For example, -3 becomes 2, then 1, then 0.

Code Example

def recursive_absolute_value(value: int) -> int:
    """Return the absolute value of an integer using recursion."""
    # Base case: zero is the stopping point.
    if value == 0:
        return 0

    # Recursive case: positive values move toward the base case.
    if value > 0:
        return 1 + recursive_absolute_value(value - 1)

    # Recursive case: negative values move toward zero and then the base case.
    return 1 + recursive_absolute_value(-value - 1)


print(recursive_absolute_value(-3))  # 3
print(recursive_absolute_value(0))   # 0
print(recursive_absolute_value(4))   # 4

Call Stack and Complexity

For -3, the calls are:

recursive_absolute_value(-3)
└── recursive_absolute_value(2)
    └── recursive_absolute_value(1)
        └── recursive_absolute_value(0)  # base case

The function then returns through the stack, adding 1 at each level.

  • Time complexity:

  • Best case: O(1) when value == 0.

  • Average case: O(|value|) for nonzero inputs; the function makes one call per unit of magnitude.

  • Worst case: O(|value|).

  • Space complexity: O(|value|) because the recursion stack contains |value| + 1 frames in the worst case.

  • The input itself is not counted as additional space; the recursion stack is counted.

Iterative Alternative

Python’s default recursion limit is approximately 1000, and Python does not optimize tail recursion. Large absolute values can therefore cause RecursionError. An explicit stack avoids that limitation:

def iterative_absolute_value(value: int) -> int:
    """Return the absolute value using an explicit stack."""
    stack: list[int] = [value]
    result = 0

    while stack:
        current = stack.pop()

        # Base case: zero contributes nothing.
        if current == 0:
            continue

        result += 1

        if current > 0:
            stack.append(current - 1)
        else:
            stack.append(-current - 1)

    return result


print(iterative_absolute_value(-3))  # 3

The iterative version still takes O(|value|) time, but it uses O(1) auxiliary space because only one pending value is stored at a time. The input is not counted.

Common Pitfalls

  • Infinite recursion: Do not use recursive_absolute_value(value + 1) for negative values; the argument moves away from zero and never reaches the base case.

  • Wrong negative transformation: -value changes the sign but does not reduce the magnitude in a count-down recursion.

  • Stack depth: Recursive solutions with large values may exceed Python’s recursion limit. Prefer the iterative version or another non-recursive formula.

  • Input scope: The function accepts one integer. Empty collections, duplicates, sorting, disconnected graphs, and cycles do not apply; the relevant edge cases are zero, positive values, negative values, and very large magnitudes.

49

How do you recursively generate all combinations of n parenthesis pairs?

Recursive backtracking generates every unique, well-formed sequence of n matching parenthesis pairs. The algorithm adds ( while openings remain and adds ) only when there is an unmatched opening, so every prefix remains valid.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Idea

Track two counts:

  • open_count: number of opening parentheses used.

  • close_count: number of closing parentheses used.

At each call:

  1. Add ( if open_count < n.

  2. Add ) if close_count < open_count.

  3. When both counts equal n, save the completed sequence.

The second condition prevents invalid prefixes such as )(. The number of distinct results is the Catalan number:

[ C_n = frac{1}{n+1}binom{2n}{n} ]

Call Stack Trace

For n = 2, the recursive calls follow this structure:

generate(0, 0)
└── add "(" → generate(1, 0), path = "("
    ├── add "(" → generate(2, 0), path = "(("
    │   └── add ")" → generate(2, 1), path = "(()"
    │       └── add ")" → generate(2, 2), result = "(())"
    └── add ")" → generate(1, 1), path = "()"
        └── add "(" → generate(2, 1), path = "()("
            └── add ")" → generate(2, 2), result = "()()"

Each recursive call adds one character and moves closer to the base case.

Complexity

Approach Time Auxiliary space When to use
Generate and validate all 2^(2n) strings O(n · 2^(2n)) O(n) Baseline comparison
Recursive backtracking O(n · C_n) O(n) Efficiently generating valid results
  • Best, average and worst-case time: O(n · C_n). Each of the C_n results contains 2n characters, and the shared-prefix traversal visits O(n · C_n) states.

  • Auxiliary space: O(n), including the recursion stack and current path. This excludes the input and returned results.

  • Returned-output space: O(n · C_n).

  • Input space: O(1) under the usual model because n is a single integer.

Memoization with functools.cache is unnecessary: identical count pairs can occur under different prefixes and therefore require different results.

Code Example

def generate_parentheses(n: int) -> list[str]:
    """Return all well-formed combinations of n parenthesis pairs."""
    if n < 0:
        raise ValueError("n must be non-negative")

    results: list[str] = []
    path: list[str] = []

    def backtrack(open_count: int, close_count: int) -> None:
        # Base case: both counts have reached n.
        if open_count == n and close_count == n:
            results.append("".join(path))
            return

        # Recursive case: add an opening parenthesis.
        # This call moves toward the base case by increasing open_count.
        if open_count < n:
            path.append("(")
            backtrack(open_count + 1, close_count)
            path.pop()

        # Recursive case: add a closing parenthesis.
        # This call moves toward the base case by increasing close_count.
        if close_count < open_count:
            path.append(")")
            backtrack(open_count, close_count + 1)
            path.pop()

    backtrack(0, 0)
    return results


print(generate_parentheses(3))
# Expected output: ['((()))', '(()())', '(())()', '()(())', '()()()']

For large n, the recursive depth can approach Python’s default recursion limit of about 1000. An explicit-stack version avoids that limit:

def generate_parentheses_iterative(n: int) -> list[str]:
    """Return all well-formed combinations using an explicit stack."""
    if n < 0:
        raise ValueError("n must be non-negative")

    results: list[str] = []
    path: list[str] = []

    # Each frame contains (open_count, close_count, next_choice).
    stack: list[tuple[int, int, int]] = [(0, 0, 0)]

    while stack:
        open_count, close_count, choice = stack[-1]

        if open_count == n and close_count == n:
            results.append("".join(path))
            stack.pop()
            if stack:
                path.pop()
            continue

        if choice == 0:
            stack[-1] = (open_count, close_count, 1)
            if open_count < n:
                path.append("(")
                stack.append((open_count + 1, close_count, 0))
            continue

        if choice == 1:
            stack[-1] = (open_count, close_count, 2)
            if close_count < open_count:
                path.append(")")
                stack.append((open_count, close_count + 1, 0))
            continue

        stack.pop()
        if stack:
            path.pop()

    return results


print(generate_parentheses_iterative(3))
# Expected output: ['((()))', '(()())', '(())()', '()(())', '()()()']

Edge Cases

  • n = 0 returns [""], representing the empty combination.

  • n = 1 returns ["()"].

  • Negative n raises ValueError.

  • Each valid sequence appears exactly once; duplicate results are not generated.

  • The caller’s input is not mutated.

Common Pitfalls

  • Adding ) without checking close_count < open_count creates invalid sequences.

  • Checking the base case only when open_count == n can miss valid shorter paths.

  • Forgetting to remove the current character after recursion causes incorrect concatenations.

  • Python has no tail-call optimization, so deep recursion requires an explicit stack.

  • Interviewers often follow up by asking for the Catalan-number formula, output count, iterative conversion, or a version that generates only combinations containing a given prefix.

50

How can recursive functions be visually debugged?

A call trace is usually the fastest way to debug recursion: log each invocation’s inputs, indentation level, and return value. For branching recursion, draw a recursion tree instead, because it reveals repeated states, unnecessary branches, and paths that never reach a base case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Visual Debugging Strategies

  • Trace entry and exit: Print before the recursive call and after it returns. Entry logs show the active path; exit logs show how results propagate back through the stack.

  • Use indentation as depth: Increase indentation for each recursive call. This represents the current call-stack depth.

  • Draw a recursion tree: For problems such as permutations or naive Fibonacci, show every branch and annotate each node with its arguments and result.

  • Use a debugger: In Python 3.12, insert breakpoint() or use pdb. The where command displays the stack, while up and down navigate callers.

  • Track progress toward termination: Identify a measurable value that must move toward the base case, such as a list index increasing, a tree height decreasing, or a remaining budget shrinking.

  • Test a tiny input: A trace of two or three levels is usually enough to expose incorrect base cases, wrong argument updates, or incorrect unwind logic.

Technique Best for Main limitation
Indented call trace Linear recursion and stack behavior Large traces become noisy
Recursion tree Branching recursion Exponential output is possible
Interactive debugger Inspecting local state and stack frames Slower for very deep recursion
Progress assertions Verifying termination and invariants Does not explain the entire path

Following the Call Stack

For factorial(3), the active calls are:

factorial(3)
└── factorial(2)
    └── factorial(1)
        └── factorial(0)

The base case returns 1. The stack then unwinds: factorial(1) returns 1, factorial(2) returns 2, and factorial(3) returns 6.

A recursive tree is different from a call-stack trace: the tree shows every branch, while the stack shows only the path currently being explored.

Complexity

For the factorial example:

  • Time: Best, average, and worst case are all O(n) because each call makes one recursive call.

  • Auxiliary space: O(n) because the recursion stack contains up to n + 1 frames. The input itself is not counted separately; counting it still gives O(n) total storage.

  • Trace output: Printing an indented trace can generate O(n²) total characters because each line contains increasing indentation.

Python’s default recursion limit is approximately 1,000, and Python does not provide tail-call optimization. Deep recursion should therefore use an explicit stack or a raised recursion limit when appropriate.

Code Example

def factorial(n: int, depth: int = 0) -> int:
    """Print each recursive call and return value for debugging."""
    if n < 0:
        raise ValueError("n must be non-negative")

    print(f"{'  ' * depth}Call factorial(n={n})")

    if n == 0:
        # Base case: the recursion stops here.
        result = 1
    else:
        # Recursive case: n decreases by one, moving toward the base case.
        result = n * factorial(n - 1, depth + 1)

    print(f"{'  ' * depth}Return factorial(n={n}) = {result}")
    return result


# Example call:
factorial(3)

# Expected output:
# Call factorial(n=3)
#   Call factorial(n=2)
#     Call factorial(n=1)
#       Call factorial(n=0)
#       Return factorial(n=0) = 1
#     Return factorial(n=1) = 1
#   Return factorial(n=2) = 2
# Return factorial(n=3) = 6

Common Pitfalls

  • Incorrect base case: Verify that valid terminal inputs return the correct value. Here, n=0 returns 1, n=1 terminates correctly, and negative values are rejected.

  • No progress: Every recursive call must change state toward termination. Assertions can verify that a depth counter, index, or remaining budget decreases.

  • Repeated subproblems: Naive Fibonacci repeats calculations. Apply @functools.cache; memoization changes its time from O(2ⁿ) to O(n) and uses O(n) space for cached results.

  • Confusing stack and tree: Branching recursion may create many calls even though the maximum stack depth remains small.

  • Unbounded recursion: For empty trees or collections, define an explicit neutral result. For disconnected graphs, start traversals from every relevant root; for cycles, maintain a visited set.

  • Excessive output: Production code should use logging with configurable levels rather than unconditional prints. Interviewers may ask how you would replace the recursive implementation with an explicit-stack iterative version.

51

How can recursion determine whether an undirected graph is connected?

A recursive depth-first search (DFS) determines graph connectivity by starting at any vertex and visiting every reachable neighbor. The undirected graph is connected exactly when the DFS visits all vertices.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Select an arbitrary starting vertex.

  2. Mark it as visited.

  3. Recursively visit each unvisited neighbor.

  4. After the traversal finishes, compare the number of visited vertices with the total number of vertices.

  5. Return True if they are equal; otherwise return False.

A visited set is essential because graphs may contain cycles. It prevents the recursion from exploring the same vertex repeatedly and creating infinite recursion.

Code Example

from collections.abc import Iterable, Mapping


def _to_undirected_adjacency(
    graph: Mapping[int, Iterable[int]],
) -> dict[int, set[int]]:
    """Convert an adjacency list into an undirected adjacency mapping."""
    adjacency: dict[int, set[int]] = {
        vertex: set(neighbors)
        for vertex, neighbors in graph.items()
    }

    # Add every edge in both directions.
    for vertex, neighbors in list(adjacency.items()):
        for neighbor in neighbors:
            adjacency.setdefault(neighbor, set()).add(vertex)

    return adjacency


def is_graph_connected(graph: Mapping[int, Iterable[int]]) -> bool:
    """Return whether an undirected adjacency-list graph is connected."""
    adjacency = _to_undirected_adjacency(graph)

    # Convention: the empty graph is connected vacuously.
    if not adjacency:
        return True

    visited: set[int] = set()

    def visit(vertex: int) -> None:
        # Base case: an already visited vertex requires no further exploration.
        if vertex in visited:
            return

        visited.add(vertex)

        # Recursive case: each call moves to a new, unvisited vertex.
        # Since the graph is finite, every recursive path reaches the base case.
        for neighbor in adjacency[vertex]:
            if neighbor not in visited:
                visit(neighbor)

    start_vertex = next(iter(adjacency))
    visit(start_vertex)

    return len(visited) == len(adjacency)


def is_graph_connected_iterative(
    graph: Mapping[int, Iterable[int]],
) -> bool:
    """Return connectivity using an explicit stack instead of recursion."""
    adjacency = _to_undirected_adjacency(graph)

    if not adjacency:
        return True

    visited: set[int] = set()
    stack = [next(iter(adjacency))]

    while stack:
        vertex = stack.pop()

        if vertex in visited:
            continue

        visited.add(vertex)

        for neighbor in adjacency[vertex]:
            if neighbor not in visited:
                stack.append(neighbor)

    return len(visited) == len(adjacency)


connected_graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
}

disconnected_graph = {
    0: [1],
    1: [0],
    2: [],
    3: [],
}

print(is_graph_connected(connected_graph))       # True
print(is_graph_connected(disconnected_graph))    # False
print(is_graph_connected_iterative(connected_graph))  # True

Example Walkthrough

For the path 0 → 1 → 2, the recursive calls proceed as follows:

Step Call visited after the call
1 visit(0) {0}
2 visit(1) {0, 1}
3 visit(2) {0, 1, 2}
4 visit(2) returns because it has no unvisited neighbors {0, 1, 2}

The final comparison is 3 == 3, so the graph is connected.

For the disconnected example, the traversal visits only 0 and 1. Since the graph contains four vertices, the result is False.

Complexity

Let V be the number of vertices and E the number of undirected edges.

  • Time: O(V + E) in the best, average, and worst cases for this implementation. Each vertex is visited at most once, and each adjacency-list entry is examined at most once.

  • Auxiliary space: O(V), including the visited set and the recursive call stack. The recursion depth can reach O(V).

  • Input storage: The adjacency list itself uses O(V + E) space. If input storage is included, total space is O(V + E); otherwise auxiliary space is O(V).

Python’s default recursion limit is approximately 1000, and Python does not provide tail-call optimization. For graphs with a potentially large depth, use the iterative version with an explicit stack.

Common Pitfalls

  • Forgetting visited: Cycles cause infinite recursion.

  • Using the wrong starting vertex: The algorithm assumes an undirected graph. In a directed graph, the question must instead specify reachability from a source or strong connectivity.

  • Ignoring isolated vertices: A vertex with an empty adjacency list is still a vertex and must be included in the total count.

  • Confusing duplicate edges with multiple vertices: Duplicate edges do not affect connectivity; the code uses sets to remove them.

  • Negative vertex labels: Labels can be any hashable application-defined values; negative integers are valid.

  • Using functools.cache instead of visited: Memoization is unnecessary for this DFS. Repeated visits represent cycles or already explored paths, so a visited set is the appropriate mechanism.

  • Interview follow-up: Ask whether the graph is directed, how isolated vertices are represented, what the empty-graph convention should be, and whether recursion depth could exceed Python’s default limit.

52

How do you recursively implement a regular expression matcher?

Memoized recursion solves this by checking whether a suffix of the pattern can match a suffix of the text. The implementation supports literal characters, . for any single character, and postfix * for zero or more occurrences of the preceding character.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The recursive function receives two indices:

  • pattern_index: the next pattern character to process.

  • text_index: the next text character to process.

There are two main cases:

  • Base case: When the pattern is exhausted, the match succeeds only if the text is also exhausted.

  • Recursive case: When the next pattern element is a literal or ., it consumes one text character if it matches.

  • Recursive case with *: The preceding character can appear zero times or at least one time:

  • Skip the entire character* group, or

  • Consume one matching character and remain at the same pattern position.

The @cache decorator prevents repeated subproblems from being recomputed.

Recursive Trace

For text = "aa" and pattern = "a*", the important calls are:

match(0, 0)
├── match(2, 0)  # skip `a*`; pattern is exhausted, but text remains -> False
└── match(0, 1)  # the first `a` was consumed before this call
    ├── match(2, 1)  # skip `a*`; text remains -> False
    └── match(0, 2)  # the second `a` was consumed before this call
        └── match(2, 2)  # skip `a*`; both are exhausted -> True

Every recursive call moves toward a base case by advancing the pattern index, the text index, or both.

Complexity

Let m be the pattern length, n be the text length, and S = (m + 1)(n + 1).

  • Best case: O(m + n + 1) when only a single non-branching path is explored.

  • Average/expected time: O(S), equivalent to O(mn) for nonempty inputs, assuming average O(1) memo-table lookups.

  • Strict worst-case time: O(S²) if pathological hash-table collisions are considered; under the conventional constant-time memo-lookup model, the usual answer is O(mn).

  • Auxiliary space: O(S) for memoization, plus O(m + n + 1) for the recursion stack.

  • Input space: The input strings are not counted separately.

Large Inputs

The recursion depth can approach O(m + n). Python’s default recursion limit is about 1000, and Python does not provide tail-call optimization. For long inputs, use an explicit stack or an iterative bottom-up dynamic-programming solution. The iterative version below converts the memoized search into an explicit-stack search.

Code Example

from functools import cache


def is_match(text: str, pattern: str) -> bool:
    """Match text against a pattern supporting '.' and postfix '*'."""
    if pattern.startswith("*") or "**" in pattern:
        raise ValueError("'*' must follow a literal character or '.'")

    @cache
    def match(pattern_index: int, text_index: int) -> bool:
        # Base case: the pattern is exhausted.
        if pattern_index == len(pattern):
            return text_index == len(text)

        first_match = (
            text_index < len(text)
            and (
                pattern[pattern_index] == text[text_index]
                or pattern[pattern_index] == "."
            )
        )

        if (
            pattern_index + 1 < len(pattern)
            and pattern[pattern_index + 1] == "*"
        ):
            # Recursive case: use zero occurrences; the pattern advances.
            if match(pattern_index + 2, text_index):
                return True

            # Recursive case: consume one occurrence; the text advances.
            return first_match and match(pattern_index, text_index + 1)

        # Recursive case: consume one literal or dot; both indices advance.
        return first_match and match(pattern_index + 1, text_index + 1)

    return match(0, 0)


print(is_match("aa", "a*"))  # True


def is_match_iterative(text: str, pattern: str) -> bool:
    """Match text without using Python's recursion stack."""
    if pattern.startswith("*") or "**" in pattern:
        raise ValueError("'*' must follow a literal character or '.'")

    memo: dict[tuple[int, int], bool] = {}
    # Phase 0 expands a state; phase 1 combines its memoized children.
    stack: list[tuple[int, int, int]] = [(0, 0, 0)]

    while stack:
        pattern_index, text_index, phase = stack.pop()
        state = (pattern_index, text_index)

        if state in memo:
            continue

        if pattern_index == len(pattern):
            memo[state] = text_index == len(text)
            continue

        first_match = (
            text_index < len(text)
            and (
                pattern[pattern_index] == text[text_index]
                or pattern[pattern_index] == "."
            )
        )

        if (
            pattern_index + 1 < len(pattern)
            and pattern[pattern_index + 1] == "*"
        ):
            if phase == 0:
                stack.append((pattern_index, text_index, 1))
                stack.append((pattern_index + 2, text_index, 0))
                if first_match:
                    stack.append((pattern_index, text_index + 1, 0))
            else:
                result = memo[(pattern_index + 2, text_index)]
                if first_match:
                    result = result or memo[(pattern_index, text_index + 1)]
                memo[state] = result
        elif not first_match:
            memo[state] = False
        elif phase == 0:
            stack.append((pattern_index, text_index, 1))
            stack.append((pattern_index + 1, text_index + 1, 0))
        else:
            memo[state] = memo[(pattern_index + 1, text_index + 1)]

    return memo[(0, 0)]


print(is_match_iterative("aa", "a*"))  # True

Common Pitfalls

  • Partial matching: This matcher must consume the entire text; it does not behave like re.search.

  • Unsupported syntax: Groups, alternation, +, ?, anchors, and character classes are not implemented. Use Python’s re module for those features.

  • Malformed patterns: A * without a preceding literal character or . is invalid.

  • Edge cases: An empty pattern matches only empty text; an empty text can match a* or .*; a one-character pattern a or . matches exactly one character. Repeated characters and numeric strings such as -1 are ordinary literals. Sorting, disconnected graphs, and cycles are not applicable.

  • Recursion limits: Long text or patterns can exceed Python’s default recursion limit; use the explicit-stack version.

  • Common follow-up: Interviewers may ask why memoization is needed, how the * branches work, or how to avoid recursion-depth failures.

53

What is the relationship between recursion and lambda calculus?

Lambda calculus provides a mathematical model of recursion without built-in named functions or let rec bindings. It expresses recursive self-reference through self-application and fixed-point combinators, although the untyped and simply typed calculi differ in whether general recursion is possible.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Relationship

A lambda term has the form λx. M, and M N applies the function M to the argument N. The core lambda calculus has no primitive named-function declarations, so recursion is encoded by applying a term to itself.

A fixed-point combinator turns a function F into a recursive term R satisfying F R = R after reduction. It supplies the recursive reference; the function F must still define the recursive step and base case.

The Y and Z Combinators

The standard untyped fixed-point combinator is Y = λf. (λx. f (x x)) (λx. f (x x)). Under normal-order or call-by-name reduction, Y F reduces to F (Y F), allowing F to invoke the resulting term again.

Under call-by-value evaluation, eagerly evaluating the self-application x x can prevent progress. The call-by-value fixed-point combinator Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y)) delays that evaluation.

For factorial, let R = Y F, where F implements the recursive step and base case. The call stack is schematically:

  1. R 3

  2. R 2

  3. R 1

  4. R 0 — the base case returns 1

Each recursive call moves toward the base case because the argument decreases.

Typed Lambda Calculus and Real Languages

Simply typed lambda calculus is strongly normalizing: every well-typed term terminates, so it cannot express general recursion. Adding a suitable fixed-point operator or other recursion mechanism changes that property.

Practical languages support recursion through language-specific features:

  • Haskell allows recursive let bindings.

  • OCaml and F# provide let rec bindings.

  • Recursive data types describe self-referential data; they are conceptually distinct from general recursive function bindings.

  • A primitive fix operator is a different design. Treating a as universally quantified in (a → a) → a would require a type system that admits such self-application; simply typed lambda calculus does not.

Recursive bindings are not necessarily compiled by desugaring them to a fixed-point combinator. Implementations may type-check them and generate ordinary recursive calls directly.

Evaluation, Stack Usage, and Iteration

Beta-reduction is substitution in the lambda-calculus model, not an inherent stack operation. A machine evaluator represents pending applications using a stack, continuation, or another runtime structure.

For a depth-n recursive chain with O(1) work per call and no duplicated terms, a straightforward stack-based evaluator takes:

  • Time: O(n) because it performs n constant-work recursive steps.

  • Auxiliary space: O(n), including O(n) stack depth and excluding the input.

Best, average, and worst-case time and space are all O(n) under that model. Lambda calculus alone specifies reduction rather than one machine cost model, so other evaluators can have different Big-O bounds.

Stock CPython 3.12 starts with a recursion limit of 1000, retrievable with sys.getrecursionlimit(), and Python has no tail-call optimization. Large recursive computations can therefore use an explicit stack. That differs from tail-call optimization: an explicit stack stores pending work in the heap, while TCO reuses the current frame for tail calls.

Common Pitfalls and Interview Tips

  • Using Y with call-by-value evaluation: It fails to terminate; a faithful Python encoding eventually raises RecursionError.

  • Assuming one evaluation strategy: Pure lambda calculus permits different reduction strategies, including normal-order and call-by-value evaluation.

  • Ignoring normalization: Simply typed lambda calculus cannot encode general recursion.

  • Conflating recursive data with recursive functions: Self-referential data types and recursive function bindings are separate capabilities.

  • Describing calls as jumps: Ordinary recursion uses call and return machinery; only suitable tail calls can be optimized to reuse a frame.

  • Using memoization indiscriminately: functools.cache helps when identical subproblems repeat, but it neither replaces a base case nor makes divergent recursion terminate.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 53 Recursion answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects