递归

可以使用递归的三个条件：

  1. 大问题可以拆成子问题
  2. 子问题的求解方式与大问题一样
  3. 存在最小子问题

递归的实现运用的是系统栈，运行时进行进栈操作，返回值时进行出栈操作，有栈满的情况。

当每次递归的子问题的规模相同时，递归符合master公式：

T(N) = a*T(N/b)+O(N^d)  a,b,d为常数
a:子问题调用的次数
b:子问题的规模（相对于父问题规模N的几倍）
d:除去子问题之外的时间复杂度
master公式：也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。

T(N) = a*T(N/b)+O(N^d)
1.当d<log(b,a)时，时间复杂度为O(n^(logb a))
2.当d=log(b,a)时，时间复杂度为O((n^d)*logn)
3.当d>log(b,a)时，时间复杂度为O(n^d)

任何递归行为都可以改为非递归

局部最小

  1. N-1 < N : N-1为局部最小
  2. N-1 > N : N为局部最小
  3. N-2 > N-1,N > N-1 : N-1为局部最小