5. 递归算法

尾递归 Tail Recursion

我们称递归调用在函数最后一步的递归方式为 尾递归
例如我们在计算阶乘的时候，如果我们这样写：

def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n-1, acc*n)

那么调用自身的步骤在最后，就是尾递归，这种递归形式由于和 正向递推没有很大的区别，有一些编译器会将其变成 iteration 的形式进行执行，从而避免 stack-overflow 的问题，其占用的时间和空间都会比一般的递归小很多

递归与压栈操作

在函数被调用的时候，我们称一个本地变量存储在名为 program stack 的栈结构中

• 在调用函数之后，其arguments 会被 push onto program stack
• 在函数执行完之后，arguments 就会被 pop 出栈
• 在函数中执行 return, 返回值会被push 到 prog stack 中
• 如果 return 的值被收到，那么返回值会被 pop 走，且本地变量会被重新存储
• 函数栈可以被嵌套 (nested), 6 个 nested calls 表示 6 个嵌套变量
• 每一个线程下只会有一个 stack
• stack 的尺寸是有限的，因此无穷递归会导致函数栈很快被用尽

主定理 master theorem

主定理是一个递归算法的时间复杂度的计算方法，其形式如下：

$T(n) = aT(\frac{n}{b}) + O(n^d)$

$T(n) = \begin{cases} O(n^{\log_b a}) & \text{if } a > b^d \\ O(n^d \log n) & \text{if } a = b^d \\ O(n^d) & \text{if } a < b^d \end{cases}$

不适用的情况

• $T(n)$ 不是一个单调的函数 not monotonic: 例如 $T(n) = \sin n$
• $f(n)$ 不是一个多项式 not a polynomial: 例如 $f(n) = 2^{n}$
• $b$ 不是一个常数例如 $T(n) = T(\sqrt{\sin n})$
• 递归逐一递减的情况 $T(n) = T(n-1) + \cdots$
• 递归的形式不符合 $T(n) = aT(\frac{n}{b}) + O(n^d)$