Data Structures & Algorithms / Ordered structures and graph reasoning / Lesson 12

Recursion, divide and conquer, and selection

Prove decreasing subproblems, distinguish call depth from total work, and select only as much order as the task needs.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A recursive call needs a smaller valid problem
A shallow call tree can still contain linear work
Selection does not require a fully sorted output

A recursive call needs a smaller valid problem

Recursion delegates a subproblem to the same contract. Correctness needs a base case, a strictly decreasing measure, and a combination rule that turns valid subresults into the promised result. Saying the function calls itself is not a termination proof. The first program finds a maximum over a nonempty half-open interval without copying slices. Each child interval is smaller until one element remains, and comparing the two returned maxima gives the parent maximum. Empty input is rejected because a maximum is undefined under this numeric contract, rather than inventing zero that would fail all-negative data.

python Self-contained Python3 algorithm example using synthetic local data.

def divide_max(values):
    if not values:
        raise ValueError("Maximum requires nonempty input")
    def solve(left, right):
        if right - left == 1:
            return values[left]
        middle = left + (right - left) // 2
        a = solve(left, middle)
        b = solve(middle, right)
        return a if a >= b else b
    return solve(0, len(values))

print(divide_max([-8, -2, -5, -9]))
print(divide_max([7]))

Expected output

-2
7

The interval shrinks without allocating sublists. Negative-only input demonstrates why an arbitrary zero base value would be wrong.

A shallow call tree can still contain linear work

The maximum example has logarithmic call depth because intervals are balanced, but it visits every element and combines n-1 pairs, so total work is linear. Call depth and call count are different quantities. Its auxiliary call frames use O(log n) space, excluding the input. A naive recursive function that removes just one element per call has linear depth even if each step looks simple. Python does not promise tail-call elimination, so replacing a loop with tail recursion can create a recursion-limit dependency. Do not change the process recursion limit as a routine algorithm repair.

Selection does not require a fully sorted output

If the task asks for the zero-based kth smallest value, arranging every other value is unnecessary. Quickselect partitions around a pivot and continues only into the region containing k. The second program uses three regions so duplicate pivot values form an equal block. A target inside that block is resolved immediately. Its deterministic first-element pivot can be badly unbalanced, giving quadratic worst-case work; this code deliberately does not claim expected linear time. Randomized or carefully chosen pivots need their own assumptions and analysis, and a three-way partition does not automatically balance distinct sorted inputs.

python Self-contained Python3 algorithm example using synthetic local data.

def select_k(values, k):
    if not 0 <= k < len(values):
        raise ValueError("k is outside the input")
    work = list(values)
    while True:
        pivot = work[0]
        lower = [value for value in work if value < pivot]
        equal = [value for value in work if value == pivot]
        higher = [value for value in work if value > pivot]
        if k < len(lower):
            work = lower
        elif k < len(lower) + len(equal):
            return pivot
        else:
            k -= len(lower) + len(equal)
            work = higher

print(select_k([7, 2, 2, 9, 4], 2))
print(select_k([3, 3, 3], 1))

Expected output

4
3

The code copies and partitions lists, preserving the caller’s input. It is a clear out-of-place teaching selection, not an in-place optimized implementation.

Analyze partition costs and discarded regions

Each selection iteration scans the current work list several times, which is still linear in that current size under bounded-cost comparisons. Balanced progress yields a geometric sum of sizes; removing only one distinct pivot repeatedly yields a quadratic sum. The equal block guarantees progress for ordinary totally ordered finite values because the pivot itself belongs there. NaN or inconsistent comparisons can violate that partition argument, so the accepted domain must exclude them or define special handling. Peak list storage is linear in current input size, but cumulative allocation and copying can be much larger.

Choose a simpler algorithm when its contract fits

For a few small inputs, sorted(values)[k] is often the most reviewable implementation even though it computes more order. For streaming largest-k results, a bounded heap offers a different memory and update contract. For a single minimum, a linear scan is simpler than sorting or selection machinery. Theoretical improvement matters only relative to the task, representation, and failure risks. Do not replace clear application code with a fragile custom partition solely to quote a favorable average bound. Establish whether the workload actually needs the stronger algorithm and whether its accepted numeric domain matches reality.

Test decreasing measures and rank preservation

Compare divide_max with max on all nonempty tiny arrays including all-negative data. Compare every valid select_k rank with sorted on arrays containing many duplicates, already sorted values, reverse order, and a singleton. Check invalid ranks are rejected and the input is unchanged. A useful selection property is that at most k values are strictly below the result and more than k values are at most the result. These rank inequalities handle duplicates without demanding a unique selected occurrence. Tests supplement, rather than replace, the partition and termination arguments.

Common errors and fixes

A recursive maximum returns zero for all-negative input

Why it happens: An invented neutral value does not belong to the maximum contract.
How to fix it: Use an actual element base case and reject empty input.
Prevent it next time: Test a negative singleton and negative-only array.

Quickselect is called worst-case linear with any pivot

Why it happens: Pivot-balance assumptions were omitted.
How to fix it: State the actual deterministic worst case or implement a proven strategy.
Prevent it next time: Include sorted distinct data in analysis.

Duplicate-heavy selection fails to shrink

Why it happens: Equal pivot values were not assigned a progress-preserving region.
How to fix it: Use a correct equality block and adjust rank by discarded counts.
Prevent it next time: Test all-equal inputs at every valid rank.

Check your understanding

1. Why is divide_max linear despite logarithmic depth?

Show worked solution

The depth measures only the longest active chain. Across the whole recursion tree, every input element is visited and n-1 combine comparisons are performed. Summing all nodes gives linear work, while only logarithmically many frames are simultaneously active for balanced splits.

2. What happens when k falls inside the equal-pivot block?