Reason about search, sort, and recursion

Identify the algorithm's promise

Linear search inspects each element until it finds a match or reaches the end. Binary search maintains a sorted candidate range and discards the half that cannot contain the target. It is not correct to apply binary search to an arbitrary unsorted array.

For insertion sort, the prefix before the current position is already sorted. Insert the next element into that prefix by shifting larger values right. Use a small trace to check that moving values does not overwrite an element you still need.

Every recursion needs progress and a base case

A recursive method calls itself on a smaller or simpler problem. The base case returns without another call. sumTo(3) waits for sumTo(2), which waits for sumTo(1), which waits for sumTo(0). Returns then travel back up the call stack.

The method below has the precondition n >= 0 and prints 6 for n = 3. Tracing only the calls is insufficient: also trace the pending additions during the returns. Test n = 0 to verify the stopping condition.

public class Demo {
    public static int sumTo(int n) {
        if (n == 0) { return 0; }
        return n + sumTo(n - 1);
    }
    public static void main(String[] args) {
        System.out.println(sumTo(3));
    }
}

Check yourself