递归和master公式

递归的本质是系统帮我们进行了压栈，栈的名字叫做系统栈。但系统栈的空间十分有限，因此在工程上我们需要把递归改写成用内存中的栈来模拟系统压栈，以此来实现非递归。

master公式又叫主定理，是一种估算递归时间复杂度的公式。但有个前提条件:只有是子问题规模相同的递归才能使用。

T(N) = a * T(N / b)+ O(N ^ c), a 、b 、c都是常数。

a是调用的子问题的次数

b是问题被分为多少个子问题的个数

c是调用之外的时间复杂度

如果log_ba < c, 复杂度为: (N ^ c)。

如果log_ba > c, 复杂度为: (N ^ log_ba)。

如果log_ba == c, 复杂度为: (N ^ c * logN)。

补充:T(N) = a * T(N / b)+ O(N * logN)，时间复杂度是O(N * (logN) ^ 2)。