递归法

递归是一种化解复杂问题的方法。通过解决较小规模的子问题，调用自身来简化计算。
其整体结构形如

def fn(n):
    # 1. 处理异常
    if n < 1:
        return
    # 2. 判断是否到达了某种结束条件
    if n == 1:
        return
    # 3. 缩小问题的规模。例如汉诺塔的规模减1，归并排序的规模减半
    a = fn(n - 1)
    b = fn(n / 2)
    # 4. 合并结果
    combine(a, b)

时间复杂度分析

递归算法分析时间复杂度比较困难。可使用公式法以及迭代法来推导。

公式法

如果时间复杂度满足这个关系：T(n) = a * T(n/b) + f(n) 那么就可以使用公式法
其中 a * T(n/b) 表示递归部分，f(n) 表示处理数据部分，对应上面的 combine(a, b)
当 a 和 b 都确定的时候，递归部分的时间复杂度就是 O(n^logbᵃ)

根据多项式中，时间复杂度取较大的原则就有：

1. 当递归部分的执行时间 nlog(b)a 大于 f(n) 的时候，最终的时间复杂度就是 O(n^logba)。
2. 当递归部分的执行时间 nlog(b)a 小于 f(n) 的时候，最终的时间复杂度就是 f(n)。
3. 当递归部分的执行时间 nlog(b)a 等于 f(n) 的时候，最终的时间复杂度就是 O(n^logba)logn

例如归并排序
T(n) = 2 * T(n/2) + n
n ^ log2(2) = n ^ 1 = n
符合情况3，那么时间复杂度就是 O(nlogn)

再来一个例子:

def fn(n):
    if n == 0:
        return
    return fn(n / 4) + fn(n / 4)

这里公式为 T(n) = 2 * T(n / 4) + 1
n ^ log4(2) = n ^ 0.5
当 n > 1 的时候，n ^ 0.5 > 1 所以这个函数的时间复杂度为 O(n^0.5)

迭代法

例如汉诺塔问题：

def hano(a, b, c, n):
    if n < 1:
        return
    # 将 n 个盘子从a借助b移动到c。
    # 可以抽象为，从a借助c移动 n - 1 个盘子到b
    # 再从b借助a移动 n - 1 个盘子到 c
    hano(a, c, b, n - 1)
    print("%s -> %s" % (a, c))
    hano(b, a, c, n - 1)

其中 if 语句和 print 语句的执行时间不会随着程序规模增长发生变化。所以整个函数的执行时间为：
T(n) = 2 * T(n - 1) + 1 对其展开:

T(n - 1) = 2 * T(n - 2) + 1
T(n) = 2 * (2 * T(n - 2) + 1) + 1= 2^2 * T(n - 2) + 2 + 1
T(n) = 2 * (2 * (2 * T(n - 3) + 1) + 1) + 1 = 2 ^ 3 * T(n - 3) + (4 + 2 + 1)
...
观察到后面是一个等比数列2^k * T(n - k)
那么第 k 个将是: `T(n) = 2^k * T(n - k) + (2^(k-1) + 2^(k-2) + ... + 1) = 2^k * T(n - k) + (2^k - 1)
当 k = n 的时候
T(n) = 2^n * T(0) + (2^n - 1)
因为 T(0) = 1
T(n) = 2*2^n - 1
因为时间复杂度和常系数无关，那最终的时间复杂度就是 O(2^n)