分析搜索、排序与递归

明确算法保证的性质

线性搜索逐个检查元素，直到找到匹配或到达末尾。二分搜索维护已排序的候选范围，并排除不可能含目标的一半。不能对任意未排序数组直接使用二分搜索。

插入排序中，当前位置之前的前缀已排序。将较大元素右移，再把下一个元素放入此前缀。通过小规模追踪检查移动时是否覆盖了仍需要的值。

递归需要推进与基本情况

递归方法在更小或更简单的问题上调用自身，基本情况不再递归。sumTo(3) 等待 sumTo(2)，后者等待 sumTo(1)，再等待 sumTo(0)。返回值随后沿调用栈逐层传回。

下面方法的前置条件是 n >= 0，n = 3 时输出 6。追踪调用还不够，也要记录返回时等待执行的加法。测试 n = 0 以验证停止条件。

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));
    }
}

自我检测