C02: Functions, recursion, search, and debugging

A. Prerequisites and observable goals#

Level: Foundation to degree core.

B. The central question: how do we control complexity?#

A function creates a boundary around a computation. Its caller supplies arguments; its body uses parameters and local names; its return value supplies a result. Printing a value and returning it are different effects. A program that prints the right answer may still return None to its caller. A useful interface specifies both normal results and failure behavior. The smaller and clearer that contract, the easier it is to test the function independently.

Suppose square(x) returns x*x. Evaluating square(2+3) first computes the argument value 5, then the call computes 25. This resembles mathematical substitution, but a programming function may mutate objects, read a file, or fail. A pure mathematical function assigns a single output to an input within its domain; not every procedure is pure or total. Keep those distinctions visible when a routine interacts with engine state.

C. Scope and calls#

A local name belongs to an invocation, not to every call of a function collectively. In a recursive sum, one invocation waits for the return value of another. Conceptually, each waiting call keeps its parameters, locals, and a continuation—the place to resume. A physical compiler may optimize away some of this structure; the diagram is a semantic model rather than a promised stack-frame layout.

For $S(3)$, substitution gives $3+(2+(1+0))=6$. The base case is not optional: it supplies a completed result instead of another call. The argument decreases by one until reaching zero. A recursive program accepting negative integers without a rejection rule would not reach this base case. Python also places practical bounds on recursion depth; use iteration for a long linear recurrence. [PY]

D. Why binary search is about a boundary#

Given sorted data $a_0\le\cdots\le a_{n-1}$, find the first index $i$ with $a_i\ge t$, or $n$ if none exists. This is called a lower bound. It handles missing values and duplicates without a special “not found” value that might be confused with index zero.

Maintain a half-open interval $[\ell,r)$, initially $[0,n)$. All indices below $\ell$ contain values $<t$; all indices at or above $r$ contain values $\ge t$. When $\ell<r$, let $m=\ell+\lfloor(r-\ell)/2\rfloor$. If $a_m<t$, then sortedness makes every index through $m$ too small, so set $\ell=m+1$. Otherwise $m$ is a possible answer and every later index is not earlier than it, so set $r=m$. At termination $\ell=r$, the invariant identifies the exact boundary.

The arithmetic $r-\ell$ is a nonnegative integer that strictly decreases in either branch. That proves termination. Each iteration roughly halves the unresolved range, giving $O(\log(n+1))$ comparisons. This is a comparison count, not a guarantee of logarithmic wall time for an arbitrary sequence with expensive indexed access. A linked list does not provide constant-time indexing. The lab accepts an indexable sorted sequence and does not spend $O(n)$ verifying sortedness on every call.

E. A worked duplicate case#

For [1,3,3,8] and target 3, initially $(\ell,r)=(0,4)$. The midpoint is 2, where the value is 3, so $r=2$. Now $m=1$, again value 3, so $r=1$. Now $m=0$, value 1 is too small, so $\ell=1$. Stop at index 1, not index 2. Returning immediately on any equality would violate the first occurrence contract.

For target 9, the search ends at 4. That is a valid insertion position but not a valid existing element index. The caller must not blindly evaluate a[4]. Empty input ends immediately at zero without an indexed read. These boundary behaviors follow from the invariant, not from a pile of unrelated exception cases.

F. Debugging as a sequence of falsifiable hypotheses#

Reproduce a failure with the smallest input that still exhibits it. State expected and actual behavior. Locate the first incorrect state, not merely the final incorrect output. Form one specific hypothesis, change one cause, and add a regression test. For a nonterminating search, a useful hypothesis is that one branch does not shrink the interval when its length is one. For an I/O error, determine whether the file could not be opened, its text could not be decoded, its fields could not be parsed, or its parsed values violated the domain. Those are different failures and deserve different diagnostics.

A traceback identifies the call sequence where an exception propagated. It does not establish which abstraction should handle it. Low-level parsing should report malformed input; a command-line wrapper should convert that report to a nonzero exit status and a readable message. Catching every exception and returning zero hides programmer defects as success.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C02#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C02.05: lower bound on a sorted sequence; sortedness is a precondition."""
from collections.abc import Sequence

def lower_bound(values: Sequence[int], target: int) -> int:
    """First index with value >= target, or len(values) if none."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

if __name__ == "__main__":
    print(lower_bound([1, 3, 3, 7], 3))

I. Retention and readiness#

Retrieve prefix-sum state from C01, then explain a base case without saying merely “to stop recursion.” Advance when a new search variant can be specified with an invariant before code. Revisit functions and returns whenever debugging is reduced to adding print statements without a prediction.