Recursive Algorithms

AQA 4.1.1.16 — Recursive algorithms

Retrieval: Year 12 (Sequence 5) implemented Binary Search iteratively, with a while loop repeatedly halving the search range. This lesson rewrites it recursively, using exactly the design process from the previous lesson — the algorithm's logic doesn't change at all, only how the repetition is expressed.

Understand — the same halving idea, expressed recursively

Binary Search's core idea — check the middle, then search only the half that could still contain the target — is naturally recursive: "search a range" reduces to "check the middle, then search a smaller range," which is precisely the shape of a recursive case. The base case is just as natural: the range has become empty, meaning the target genuinely isn't present.

See it — recursive binary search

def binary_search_recursive(sorted_list, target, low, high):
    if low > high:                    # base case: range is empty
        return -1
    mid = (low + high) // 2
    if sorted_list[mid] == target:
        return mid
    elif sorted_list[mid] < target:
        return binary_search_recursive(sorted_list, target, mid + 1, high)   # search right half
    else:
        return binary_search_recursive(sorted_list, target, low, mid - 1)    # search left half

numbers = [3, 7, 12, 19, 25, 34, 41]
print(binary_search_recursive(numbers, 25, 0, len(numbers) - 1))   # 4

Trace it — searching for 12

Each recursive call has its own stack frame (Sequence 10's earlier lesson) holding its own low/high/mid — completely independent of every other call's copy of the same variable names.

Evaluate — recursive vs iterative binary search

Both versions perform exactly the same comparisons, in exactly the same order — the recursive version isn't "smarter" or "more efficient" than the loop-based one from Year 12. The genuine trade-off is memory: the iterative version uses one loop, needing no extra stack frames at all; the recursive version pushes a new stack frame for every halving, meaning roughly log₂(n) frames at its deepest point for a list of size n. For most realistic list sizes this is negligible, but it's a real, measurable cost the iterative version simply doesn't have.

Debug it — diagnose, explain, fix, test, justify

def binary_search_recursive(sorted_list, target, low, high):
    mid = (low + high) // 2
    if sorted_list[mid] == target:
        return mid
    elif sorted_list[mid] < target:
        return binary_search_recursive(sorted_list, target, mid + 1, high)
    else:
        return binary_search_recursive(sorted_list, target, low, mid - 1)

numbers = [3, 7, 12, 19, 25, 34, 41]
print(binary_search_recursive(numbers, 100, 0, len(numbers) - 1))

Searching for a value that genuinely isn't in the list (100) crashes with IndexError: list index out of range instead of returning -1.

1. Diagnose: compare this version against the working one above — what's structurally missing?
2. Explain: what specifically goes wrong with low and high once the target has been ruled out from the entire list, and why does that make mid an invalid index?
3. Fix: restore the missing base case.
4. Test: confirm searching for 100 now correctly returns -1, and searching for a value that is present still returns the correct index.
5. Justify: explain why this bug specifically only appears for a target that isn't in the list, never for one that is.

(The base case (if low > high: return -1) is missing entirely. Without it, low keeps increasing past high (or high keeps decreasing past low) every time the target is ruled out from a half, until mid computes an index outside the list's actual bounds. A target that IS present is always found before low and high can cross, so the missing base case never gets exercised for a successful search - only an absent target ever reaches the broken state.)

Common mistake

Assuming a recursive rewrite of an algorithm you already know automatically works correctly, without separately checking its base case — the searching logic transfers directly from the iterative version, but the base case has to be deliberately re-derived for the recursive structure, exactly as the debug task above demonstrates.

Challenge

Implement recursive linear search, linear_search_recursive(items, target, index), that checks items[index] and recurses on index + 1 if it doesn't match, with an appropriate base case for both "found" and "reached the end without finding it."

Looking ahead: Sequence 13 (Advanced Algorithms) uses exactly this recursive pattern for graph traversal (Depth-First Search) and Merge Sort — the same base-case-plus-shrinking-recursive-case design you've now practised twice.