Skip to content
Hello Python
Algorithm1 Practice4 Interview

Recursion

Solve a problem by reducing it to smaller instances with explicit base cases. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Recursion when the prompt's constraints and required operations match this shape: Solve a problem by reducing it to smaller instances with explicit base cases.

Pybit demonstrates Recursion in a professional Python interview workspace.
On this page · Trust a Smaller Contract

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Recursion Code Labs

Trust a Smaller Contract

A recursive function solves the current problem by trusting the same function on a strictly smaller input. Define what one call returns without mentally expanding the entire call tree.

Write the Base Case First

The base case must produce a complete answer without another call. It also identifies the decreasing measure—length, remaining depth, interval size, or unvisited nodes—that proves termination.

Trace Recursive Calls and Returns

Reference
def countdown_trace(n):
    events = []
    def visit(value):
        events.append(["call", value])
        if value > 0:
            visit(value - 1)
        events.append(["return", value])
    visit(n)
    return events
Practice

Implement countdown_trace(n). Return events ["call", n] while descending to zero, then ["return", n] while unwinding.

Public tests

  • Separate descent and unwind

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Separate Work Before and After Return

Work before the recursive call happens while descending; work after it happens while the call stack unwinds. Preorder and postorder behavior differ only in this placement, but their outputs can be completely different.

Sum a Nested List

Reference
def nested_sum(value):
    if isinstance(value, int):
        return value
    return sum(nested_sum(item) for item in value)
Practice

Implement nested_sum(value). value is an integer or a nested list of values. Return the sum of all integers.

Public tests

  • Trust the smaller nested contract

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Recursion or Iteration

Use recursion when the data or proof is naturally recursive and depth is safely bounded. Use iteration for a simple linear state transition or potentially deep input. Python has finite call-stack depth and does not optimize tail calls.

Explain It in an Interview

Say: “The call contract is this, the base case handles this smallest input, and every recursive argument decreases this measure.” Then combine returned values and account for both total calls and O(depth) call-stack space.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Recursion complete workflowO(n)O(n)When one traversal identifies the root and another partitions left from right, index ranges avoid copying subarrays at each recursive call. Each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder.

Space

O(n) for the focused Partition Traversal Ranges implementation.

Assumptions

  • The preorder start identifies the frame root, and its inorder position uniquely splits left and right node sets. Using the left-set size to partition preorder creates two smaller matching frames until every node is assigned.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Recursion invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The call arguments fully describe the current subproblem.
  3. Every recursive branch either reaches a base case or strictly reduces the remaining work.
  4. When one traversal identifies the root and another partitions left from right, index ranges avoid copying subarrays at each recursive call. Preserve this claim after every transition.
  5. Each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. Preserve this claim after every transition.

When To Use Or Avoid Recursion

Use It When

  • Use Recursion when this precondition is stated or can be proved: Every recursive call reduces a well-defined measure and all terminal states have explicit base cases.
  • Use it when this maintained state removes repeated work: The call arguments fully describe the current subproblem.

Choose Another Tool When

  • Avoid Recursion when this precondition is absent: Every recursive call reduces a well-defined measure and all terminal states have explicit base cases.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Every recursive call reduces a well-defined measure and all terminal states have explicit base cases.

Avoid

def partition_traversal_ranges(preorder, inorder):
    pass

Use instead

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Where you will hit this: Partition Traversal Ranges(opens in a new tab)

Breaking the state transition

Omits one position from both preorder child boundaries, producing incorrect or nonshrinking recursive frames.

Prevent it: Preserve this proof obligation: The decreasing measure guarantees termination, and each return preserves the contract of its smaller subproblem.

Avoid

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pl, pr, il, ir):
        if pl >= pr: return
        frames.append([pl, pr, il, ir])
        root = positions[preorder[pl]]
        left_size = root - il
        partition(pl + 1, pl + left_size, il, root)
        partition(pl + left_size, pr, root + 1, ir)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Use instead

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Where you will hit this: Partition Traversal Ranges(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pl, pr, il, ir):
        if pl >= pr: return
        frames.append([pl, pr, il, ir])
        root = positions[preorder[pl]]
        left_size = root - il
        partition(pl + 1, pl + left_size, il, root)
        partition(pl + left_size, pr, root + 1, ir)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Use instead

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames

Where you will hit this: Build Tree from Inorder and Postorder(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.