002.递归和master公式

前置知识：无

递归 §

用获取数组最大值这个例子来理解递归

func getMax(arr []int) int {
	n := len(arr)
	if n == 0 {
		panic("arr is empty")
	}
	return process(arr, 0, n - 1)
}
 
func process(arr []int, left, right int) int {
	if left == right { // base case
		return arr[left]
	}
	mid := left + (right - left) >> 1
	lMax = process(arr, left, mid) // 自己调用自己，递归
	rMax = process(arr, mid + 1, right)
	return max(lMax, rMax)
}

base case §

递归压栈终止条件，子问题已经不能再分解了

从思想上理解递归 §

对于新手来说，递归去画调用图是非常重要的，有利于分析递归

从实际上理解递归 §

递归不是玄学，底层是利用系统栈（函数调用栈）来实现的

任何递归函数都一定可以改成非递归 §

不用系统帮你压栈（系统栈空间），自己压栈呗（内存空间）

递归改成非递归的必要性 §

• 工程上几乎一定要改，除非确定数据量再大递归也一定不深，归并排序、快速排序、线段树、很多的平衡树等，后面都讲
• 算法笔试或者比赛中（能通过就不改）

递归与迭代

master 公式 §

master 公式用于估算子问题规模相同的递归算法的时间复杂度

所有子问题规模相同的递归才能用 master 公式

master 公式 ：$T(n)=a\ast T(\frac{n}{b})+O(n^c)$，$a$、$b$、$c$ 都是常数

• $a$：几个子问题（一个递归会开几个子递归）
• $b$：一个子问题处理 $\frac{1}{b}$ 的数据量（一个子递归处理父递归的多少数据量）
• $c$：非递归部分的时间复杂度

计算递归算法时间复杂度：

• 如果 $lo{g}_b^a<c$，复杂度为：$O(n^c)$
• 如果 $lo{g}_b^a>c$，复杂度为：$O(n^{lo{g}_b^a})$
• 如果 $lo{g}_b^a=c$，复杂度为：$O(n^c\ast lo{g}^n)$

一个补充：$T(n)=2\ast T(\frac{n}{2})+O(n\ast lo{g}^n)$，虽然它不符合 master 公式的形式，但是比较常见

其时间复杂度是 $O(n\ast (lo{g}^n{)}^2)$，证明过程比较复杂，记住即可

举例 1 §

用 master 公式计算上面 获取数组最大值递归算法 的时间复杂度

func process(arr []int, left, right int) int {
	// O(1)
	if left == right {
		return arr[left]
	}
 
	// O(1)
	mid := left + (right - left) >> 1
 
	// 两个子递归，每个子递归处理一半数据
	lMax = process(arr, left, mid)
	rMax = process(arr, mid + 1, right)
 
	// O(1)
	return max(lMax, rMax)
}

每次递归将一个问题分解成两个子问题，每个子问题处理当前递归 $\frac{1}{2}$ 的数据（一共两个子问题，两个子问题规模相同），即：所有子问题规模相同，可以用 master 公式

$a=2,b=2,c=0$，代入 master 公式：$T(n)=2\ast T(\frac{n}{2})+O(n^0)$，$lo{g}_2^2=1>0$，所以该递归算法的时间复杂度为 $O(n^{lo{g}_2^2})=O(n)$

举例 2 §

修改一下：

func process(arr []int, left, right int) int {
	// O(1)
	if left == right {
		return arr[left]
	}
 
	// O(1)
	leftThreeTwo := left + (right - left) / 3 * 2
	rightThreeTwo := right - (right - left) / 3 * 2
 
	// 两个子递归，每个子递归处理 2/3 数据
	lMax = process(arr, left, leftThreeTwo)
	rMax = process(arr, rightThreeTwo, right)
 
	// O(n)
	for i := left; i <= right; i++ {
		fmt.Println(arr[i])
	}
 
	// O(1)
	return max(lMax, rMax)
}

$a=2,b=\frac{3}{2},c=1$，$T(n)=2\ast T(\frac{2n}{3})+O(n^1)$，$lo{g}_{\frac{3}{2}}^2>1$，时间复杂度 $=O(n^{lo{g}_{\frac{3}{2}}^2})$

举例 3 §

修改一下：

func process(arr []int, left, right int) int {
	// O(1)
	if left == right {
		return arr[left]
	}
 
	// O(1)
	leftThreeTwo := left + (right - left) / 3 * 2
 
	// 两个子递归
	lMax = process(arr, left, leftThreeTwo) // 处理 2/3 数据
	rMax = process(arr, leftThreeTwo + 1, right) // 处理 1/3 数据
 
	// O(1)
	return max(lMax, rMax)
}

$T(n)=T(\frac{2n}{3})+T(\frac{n}{3})+O(n^0)$

两个子问题规模不同，不适用 master 公式