LeetCode 热题 - 递归

递归 (recursion) 是我们刷 LeetCode 题常用的解题方法，这里我们来深入讲解下这个实现算法的方法

什么是递归

递归其实就是函数调用自身，它的作用是将一个大规模问题缩小规模，转换为子问题，将看似复杂的问题变得简洁和易于理解。这里首先给出一套递归的解题模板，如下

func recursion(input) {    // 1. 判断输入是否非法    if input is invalid {        return    }        // 2. 递归结束条件    if match condition {        return some value    }        // 3. 缩小问题规模，转换为子问题，确定递推公式    result1 := recursion(input1)    result2 := recursion(input2)        // 4. 整合结果    return combine(result1, result2)}

斐波那契数是非常经典的递归题，这里我们通过斐波那契数来加深下对递归的理解，题目地址为 Fibonacci Number。首先通过斐波那契数的性质，我们确定如下递推公式

F(0) = 0F(1) = 1F(N) = F(n-1) + F(n-2), N > 1

根据递推公式，我们就可以写出如下代码了

func fib(N int) int {    if N <= 1 {        return N    }
    return fib(N-1) + fib(N-2)}

递归中的重复计算

通常情况下，递归是一种直观有效的实现算法的方法，但是如果使用不当是会带来性能问题的，比方说重复计算。我们还是通过斐波那契数来举例，如下

fib(4) = fib(3) + fib(2) = fib(2) + fib(1) + fib(2)

可以看到一些中间结果被多次重复计算了，为了解决这个问题我们可以使用记忆化 (memoization)，其实很简单就是用容器来保存中间结果，这里我们可以使用 hashmap

var m = make(map[int]int)
func fib(N int) int {    if N < 2 {        return N    }
    if val, ok := m[N]; ok {        return val    }
    m[N] = fib(N-1) + fib(N-2)
    return m[N]}

栈溢出

我们知道函数调用的话需要分配栈空间，调用完成后会释放对应的栈空间，那么如果递归的层数非常深，那么就会导致栈内存空间不够用，stack overflow。我们继续通过斐波那契数来举例子，如下

func fib(N int) int {    if N <= 1 {        return N    }
    return fib(N-1) + fib(N-2)}
func main() {    fib(100000)}
// fatal error: stack overflow

这种时候，其实我们依旧可以使用记忆化来优化，但是更好的方式其实是使用迭代，这个后面会写一篇文章来讲

计算递归的时间复杂度和空间复杂度

递归的时间复杂度 O(T) 是其递归调用数量 R 和非递归计算的时间复杂度的乘积 O(s)

O(T) = R * O(s)

我们还是以斐波那契数来举例子，首先我们计算下 fib(4) 的调用树，如下

根据二叉树的性质，节点数量是 2^n 级别的，这里我们就可以估算 R = 2^n，而非递归计算的时间复杂度为 O(n)。根据公式可以得出时间复杂度为 O(2^n)

递归的空间复杂度计算主要分两部分，分别是递归相关空间 (recursion related space) 和非递归相关空间 (non-recursion related space)。递归相关空间包含函数堆栈空间。非递归相关空间如同字面意思就是和递归过程没有关联的内存空间。这里我们以使用了记忆化优化后的斐波那契数来举例子

递归相关空间: O(n) # 主要开销是堆栈空间非递归相关空间: O(n) # 主要开销是 hashmap

综上可以得出空间复杂度为 O(n)

尾递归

在讲尾递归前，首先了解下函数调用时栈空间的变化。通过下图可以看到每次调用函数都会重新分配栈空间，递归的深度越深，需要开辟的栈空间就越多，最终会导致栈空间不够用，stack overflow

尾递归是尾调用的特殊情况，尾递归调用是函数中的最后一条指令是执行递归调用。至于尾调用 (Tail Call) 和尾递归 (Tail Recursion) 的关系后面会写一篇文章说明。那么尾递归能带来什么好处呢？它可以避免递归调用时多次开辟占空间，直接复用同一块栈空间，如下所示

然而并不是所有的编程语言都支持这种优化，比如 JavaScript(ES6)，Lua 支持尾调用优化。而绝大多数编程语言，比如 Java 和 Python 就不支持尾调用优化