leetcode热门100题解析（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) }

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

F(0) = 0 F(1) = 1 F(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) 的调用树，如下

leetcode热门100题解析（LeetCode热题-）(1)

根据二叉树的性质，节点数量是 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

leetcode热门100题解析（LeetCode热题-）(2)