Searching and Sorting

Linear search: Simpler code, but more costly to run
Binary search: Requires sorted data, code slightly more complex, but much more efficient

Use linear search for a "few" searches with unsorted data
Sort if doing "lots and lots" of searches

example

Recursion

A function that calls itself is recursive.
Expressive but a danger of infinite loops.

Three Laws of Recursion:
1. Must have non-recursive base-case
2. Must test for base-case before recursive call
3. Recursive call must be "simpler", i.e., must "move toward" the base-case

examples