数据结构和算法(3):递归
概述
定义
计算机科学中,递归是一种解决计算问题的方法,其中解决方案取决于同一类问题的更小子集
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.
比如单链表递归遍历的例子:
void f(Node node) {if(node == null) {return;}println("before:" + node.value)f(node.next);println("after:" + node.value)
}
说明:
- 自己调用自己,如果说每个函数对应着一种解决方案,自己调用自己意味着解决方案是一样的(有规律的)
- 每次调用,函数处理的数据会较上次缩减(子集),而且最后会缩减至无需继续递归
- 内层函数调用(子集处理)完成,外层函数才能算调用完成
原理
假设链表中有 3 个节点,value 分别为 1,2,3,以上代码的执行流程就类似于下面的伪码
// 1 -> 2 -> 3 -> null f(1)void f(Node node = 1) {println("before:" + node.value) // 1void f(Node node = 2) {println("before:" + node.value) // 2void f(Node node = 3) {println("before:" + node.value) // 3void f(Node node = null) {if(node == null) {return;}}println("after:" + node.value) // 3}println("after:" + node.value) // 2}println("after:" + node.value) // 1
}
思路
- 确定能否使用递归求解
- 推导出递推关系,即父问题与子问题的关系,以及递归的结束条件
例如之前遍历链表的递推关系为
f(n)={停止n=nullf(n.next)n≠nullf(n) = \\begin{cases} 停止& n = null \\\\ f(n.next) & n \\neq null \\end{cases} f(n)={停止f(n.next)n=nulln=null
- 深入到最里层叫做递
- 从最里层出来叫做归
- 在递的过程中,外层函数内的局部变量(以及方法参数)并未消失,归的时候还可以用到
单路递归 Single Recursion
E01. 阶乘
用递归方法求阶乘
-
阶乘的定义 n!=1⋅2⋅3⋯(n−2)⋅(n−1)⋅nn!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅nn!=1⋅2⋅3⋯(n−2)⋅(n−1)⋅n,其中 nnn 为自然数,当然 0!=10! = 10!=1
-
递推关系
f(n)={1n=1n∗f(n−1)n>1f(n) = \\begin{cases} 1 & n = 1\\\\ n * f(n-1) & n > 1 \\end{cases} f(n)={1n∗f(n−1)n=1n>1
代码
private static int f(int n) {if (n == 1) {return 1;}return n * f(n - 1);
}
拆解伪码如下,假设 n 初始值为 3
f(int n = 3) { // 解决不了,递return 3 * f(int n = 2) { // 解决不了,继续递return 2 * f(int n = 1) {if (n == 1) { // 可以解决, 开始归return 1;}}}
}
E02. 反向打印字符串
用递归反向打印字符串,n 为字符在整个字符串 str 中的索引位置
- 递:n 从 0 开始,每次 n + 1,一直递到 n == str.length() - 1
- 归:从 n == str.length() 开始归,从归打印,自然是逆序的
递推关系
f(n)={停止n=str.length()f(n+1)0≤n≤str.length()−1f(n) = \\begin{cases} 停止 & n = str.length() \\\\ f(n+1) & 0 \\leq n \\leq str.length() - 1 \\end{cases} f(n)={停止f(n+1)n=str.length()0≤n≤str.length()−1
代码为
public static void reversePrint(String str, int index) {if (index == str.length()) {return;}reversePrint(str, index + 1);System.out.println(str.charAt(index));
}
拆解伪码如下,假设字符串为 “abc”
void reversePrint(String str, int index = 0) {void reversePrint(String str, int index = 1) {void reversePrint(String str, int index = 2) {void reversePrint(String str, int index = 3) { if (index == str.length()) {return; // 开始归}}System.out.println(str.charAt(index)); // 打印 c}System.out.println(str.charAt(index)); // 打印 b}System.out.println(str.charAt(index)); // 打印 a
}
多路递归 Multi Recursion
- 之前的例子是每个递归函数只包含一个自身的调用,这称之为 single recursion
- 如果每个递归函数例包含多个自身调用,称之为 multi recursion
E01. 斐波那契数列
递推关系
f(n)={0n=01n=1f(n−1)+f(n−2)n>1f(n) = \\begin{cases} 0 & n=0 \\\\ 1 & n=1 \\\\ f(n-1) + f(n-2) & n>1 \\end{cases} f(n)=⎩⎨⎧01f(n−1)+f(n−2)n=0n=1n>1
下面的表格列出了数列的前几项
F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 |
实现
public static int f(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return f(n - 1) + f(n - 2);
}
执行流程
- 绿色代表正在执行(对应递),灰色代表执行结束(对应归)
- 递不到头,不能归,对应着深度优先搜索
时间复杂度
- 递归的次数也符合斐波那契规律,2∗f(n+1)−12 * f(n+1)-12∗f(n+1)−1
- 时间复杂度推导过程
- 斐波那契通项公式 f(n)=15∗(1+52n−1−52n)f(n) = \\frac{1}{\\sqrt{5}}*({\\frac{1+\\sqrt{5}}{2}}^n - {\\frac{1-\\sqrt{5}}{2}}^n)f(n)=51∗(21+5n−21−5n)
- 简化为:f(n)=12.236∗(1.618n−(−0.618)n)f(n) = \\frac{1}{2.236}*({1.618}^n - {(-0.618)}^n)f(n)=2.2361∗(1.618n−(−0.618)n)
- 带入递归次数公式 2∗12.236∗(1.618n+1−(−0.618)n+1)−12*\\frac{1}{2.236}*({1.618}^{n+1} - {(-0.618)}^{n+1})-12∗2.2361∗(1.618n+1−(−0.618)n+1)−1
- 时间复杂度为 Θ(1.618n)\\Theta(1.618^n)Θ(1.618n)
- 更多 Fibonacci 参考[8][9][^10]
- 以上时间复杂度分析,未考虑大数相加的因素
变体1 - 兔子问题[^8]
- 第一个月,有一对未成熟的兔子(黑色,注意图中个头较小)
- 第二个月,它们成熟
- 第三个月,它们能产下一对新的小兔子(蓝色)
- 所有兔子遵循相同规律,求第 nnn 个月的兔子数
分析
兔子问题如何与斐波那契联系起来呢?设第 n 个月兔子数为 f(n)f(n)f(n)
- f(n)f(n)f(n) = 上个月兔子数 + 新生的小兔子数
- 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
- 因为需要一个月兔子就成熟,所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
- 上个月兔子数,即 f(n−1)f(n-1)f(n−1)
- 上上个月的兔子数,即 f(n−2)f(n-2)f(n−2)
因此本质还是斐波那契数列,只是从其第一项开始
变体2 - 青蛙爬楼梯
- 楼梯有 nnn 阶
- 青蛙要爬到楼顶,可以一次跳一阶,也可以一次跳两阶
- 只能向上跳,问有多少种跳法
分析
n | 跳法 | 规律 |
---|---|---|
1 | (1) | 暂时看不出 |
2 | (1,1) (2) | 暂时看不出 |
3 | (1,1,1) (1,2) (2,1) | 暂时看不出 |
4 | (1,1,1,1) (1,2,1) (2,1,1) (1,1,2) (2,2) |
最后一跳,跳一个台阶的,基于f(3) 最后一跳,跳两个台阶的,基于f(2) |
5 | … | … |
-
因此本质上还是斐波那契数列,只是从其第二项开始
-
对应 leetcode 题目 70. 爬楼梯 - 力扣(LeetCode)
递归优化-记忆法
上述代码存在很多重复的计算,例如求 f(5)f(5)f(5) 递归分解过程
可以看到(颜色相同的是重复的):
- f(3)f(3)f(3) 重复了 2 次
- f(2)f(2)f(2) 重复了 3 次
- f(1)f(1)f(1) 重复了 5 次
- f(0)f(0)f(0) 重复了 3 次
随着 nnn 的增大,重复次数非常可观,如何优化呢?
Memoization 记忆法(也称备忘录)是一种优化技术,通过存储函数调用结果(通常比较昂贵),当再次出现相同的输入(子问题)时,就能实现加速效果,改进后的代码
public static void main(String[] args) {int n = 13;int[] cache = new int[n + 1];Arrays.fill(cache, -1);cache[0] = 0;cache[1] = 1;System.out.println(f(cache, n));
}public static int f(int[] cache, int n) {if (cache[n] != -1) {return cache[n];}cache[n] = f(cache, n - 1) + f(cache, n - 2);return cache[n];
}
优化后的图示,只要结果被缓存,就不会执行其子问题
- 改进后的时间复杂度为 O(n)O(n)O(n)
- 请自行验证改进后的效果
- 请自行分析改进后的空间复杂度
注意
- 记忆法是动态规划的一种情况,强调的是自顶向下的解决
- 记忆法的本质是空间换时间
递归时间复杂度-Master theorem
若有递归式
T(n)=aT(nb)+f(n)T(n) = aT(\\frac{n}{b}) + f(n) T(n)=aT(bn)+f(n)
其中
- T(n)T(n)T(n) 是问题的运行时间,nnn 是数据规模
- aaa 是子问题个数
- T(nb)T(\\frac{n}{b})T(bn) 是子问题运行时间,每个子问题被拆成原问题数据规模的 nb\\frac{n}{b}bn
- f(n)f(n)f(n) 是除递归外执行的计算
令 x=logbax = \\log_{b}{a}x=logba,即 x=log子问题缩小倍数子问题个数x = \\log_{子问题缩小倍数}{子问题个数}x=log子问题缩小倍数子问题个数
那么
T(n)={Θ(nx)f(n)=O(nc)并且c<xΘ(nxlogn)f(n)=Θ(nx)Θ(nc)f(n)=Ω(nc)并且c>xT(n) = \\begin{cases} \\Theta(n^x) & f(n) = O(n^c) 并且 c \\lt x\\\\ \\Theta(n^x\\log{n}) & f(n) = \\Theta(n^x)\\\\ \\Theta(n^c) & f(n) = \\Omega(n^c) 并且 c \\gt x \\end{cases} T(n)=⎩⎨⎧Θ(nx)Θ(nxlogn)Θ(nc)f(n)=O(nc)并且c<xf(n)=Θ(nx)f(n)=Ω(nc)并且c>x
例1
T(n)=2T(n2)+n4T(n) = 2T(\\frac{n}{2}) + n^4T(n)=2T(2n)+n4
- 此时 x=1<4x = 1 < 4x=1<4,由后者决定整个时间复杂度 Θ(n4)\\Theta(n^4)Θ(n4)
- 如果觉得对数不好算,可以换为求【bbb 的几次方能等于 aaa】
例2
T(n)=T(7n10)+nT(n) = T(\\frac{7n}{10}) + nT(n)=T(107n)+n
- a=1,b=107,x=0,c=1a=1, b=\\frac{10}{7}, x=0, c=1a=1,b=710,x=0,c=1
- 此时 x=0<1x = 0 < 1x=0<1,由后者决定整个时间复杂度 Θ(n)\\Theta(n)Θ(n)
例3
T(n)=16T(n4)+n2T(n) = 16T(\\frac{n}{4}) + n^2T(n)=16T(4n)+n2
- a=16,b=4,x=2,c=2a=16, b=4, x=2, c=2a=16,b=4,x=2,c=2
- 此时 x=2=cx=2 = cx=2=c,时间复杂度 Θ(n2logn)\\Theta(n^2 \\log{n})Θ(n2logn)
例4
T(n)=7T(n3)+n2T(n)=7T(\\frac{n}{3}) + n^2T(n)=7T(3n)+n2
- a=7,b=3,x=1.?,c=2a=7, b=3, x=1.?, c=2a=7,b=3,x=1.?,c=2
- 此时 x=log37<2x = \\log_{3}{7} < 2x=log37<2,由后者决定整个时间复杂度 Θ(n2)\\Theta(n^2)Θ(n2)
例5
T(n)=7T(n2)+n2T(n) = 7T(\\frac{n}{2}) + n^2T(n)=7T(2n)+n2
- a=7,b=2,x=2.?,c=2a=7, b=2, x=2.?, c=2a=7,b=2,x=2.?,c=2
- 此时 x=log27>2x = log_2{7} > 2x=log27>2,由前者决定整个时间复杂度 Θ(nlog27)\\Theta(n^{\\log_2{7}})Θ(nlog27)
例6
T(n)=2T(n4)+nT(n) = 2T(\\frac{n}{4}) + \\sqrt{n}T(n)=2T(4n)+n
- a=2,b=4,x=0.5,c=0.5a=2, b=4, x = 0.5, c=0.5a=2,b=4,x=0.5,c=0.5
- 此时 x=0.5=cx = 0.5 = cx=0.5=c,时间复杂度 Θ(nlogn)\\Theta(\\sqrt{n}\\ \\log{n})Θ(n logn)
例7. 二分查找递归
int f(int[] a, int target, int i, int j) {if (i > j) {return -1;}int m = (i + j) >>> 1;if (target < a[m]) {return f(a, target, i, m - 1);} else if (a[m] < target) {return f(a, target, m + 1, j);} else {return m;}
}
- 子问题个数 a=1a = 1a=1
- 子问题数据规模缩小倍数 b=2b = 2b=2
- 除递归外执行的计算是常数级 c=0c=0c=0
T(n)=T(n2)+n0T(n) = T(\\frac{n}{2}) + n^0T(n)=T(2n)+n0
- 此时 x=0=cx=0 = cx=0=c,时间复杂度 Θ(logn)\\Theta(\\log{n})Θ(logn)
例8. 归并排序递归
void split(B[], i, j, A[])
{if (j - i <= 1) return; m = (i + j) / 2; // 递归split(A, i, m, B); split(A, m, j, B); // 合并merge(B, i, m, j, A);
}
- 子问题个数 a=2a=2a=2
- 子问题数据规模缩小倍数 b=2b=2b=2
- 除递归外,主要时间花在合并上,它可以用 f(n)=nf(n) = nf(n)=n 表示
T(n)=2T(n2)+nT(n) = 2T(\\frac{n}{2}) + nT(n)=2T(2n)+n
- 此时 x=1=cx=1=cx=1=c,时间复杂度 Θ(nlogn)\\Theta(n\\log{n})Θ(nlogn)
例9. 快速排序递归
algorithm quicksort(A, lo, hi) is if lo >= hi || lo < 0 then return// 分区p := partition(A, lo, hi) // 递归quicksort(A, lo, p - 1) quicksort(A, p + 1, hi)
- 子问题个数 a=2a=2a=2
- 子问题数据规模缩小倍数
- 如果分区分的好,b=2b=2b=2
- 如果分区没分好,例如分区1 的数据是 0,分区 2 的数据是 n−1n-1n−1
- 除递归外,主要时间花在分区上,它可以用 f(n)=nf(n) = nf(n)=n 表示
情况1 - 分区分的好
T(n)=2T(n2)+nT(n) = 2T(\\frac{n}{2}) + nT(n)=2T(2n)+n
- 此时 x=1=cx=1=cx=1=c,时间复杂度 Θ(nlogn)\\Theta(n\\log{n})Θ(nlogn)
情况2 - 分区没分好
T(n)=T(n−1)+T(1)+nT(n) = T(n-1) + T(1) + nT(n)=T(n−1)+T(1)+n
- 此时不能用主定理求解
递归时间复杂度-展开求解
像下面的递归式,都不能用主定理求解
例1 - 递归求和
long sum(long n) {if (n == 1) {return 1;}return n + sum(n - 1);
}
T(n)=T(n−1)+cT(n) = T(n-1) + cT(n)=T(n−1)+c,T(1)=cT(1) = cT(1)=c
下面为展开过程
T(n)=T(n−2)+c+cT(n) = T(n-2) + c + cT(n)=T(n−2)+c+c
T(n)=T(n−3)+c+c+cT(n) = T(n-3) + c + c + cT(n)=T(n−3)+c+c+c
…
T(n)=T(n−(n−1))+(n−1)cT(n) = T(n-(n-1)) + (n-1)cT(n)=T(n−(n−1))+(n−1)c
- 其中 T(n−(n−1))T(n-(n-1))T(n−(n−1)) 即 T(1)T(1)T(1)
- 带入求得 T(n)=c+(n−1)c=ncT(n) = c + (n-1)c = ncT(n)=c+(n−1)c=nc
时间复杂度为 O(n)O(n)O(n)
例2 - 递归冒泡排序
void bubble(int[] a, int high) {if(0 == high) {return;}for (int i = 0; i < high; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);}}bubble(a, high - 1);
}
T(n)=T(n−1)+nT(n) = T(n-1) + nT(n)=T(n−1)+n,T(1)=cT(1) = cT(1)=c
下面为展开过程
T(n)=T(n−2)+(n−1)+nT(n) = T(n-2) + (n-1) + nT(n)=T(n−2)+(n−1)+n
T(n)=T(n−3)+(n−2)+(n−1)+nT(n) = T(n-3) + (n-2) + (n-1) + nT(n)=T(n−3)+(n−2)+(n−1)+n
…
T(n)=T(1)+2+...+n=T(1)+(n−1)2+n2=c+n22+n2−1T(n) = T(1) + 2 + ... + n = T(1) + (n-1)\\frac{2+n}{2} = c + \\frac{n^2}{2} + \\frac{n}{2} -1T(n)=T(1)+2+...+n=T(1)+(n−1)22+n=c+2n2+2n−1
时间复杂度 O(n2)O(n^2)O(n2)
注:
- 等差数列求和为 个数∗∣首项−末项∣2个数*\\frac{\\vert首项-末项\\vert}{2}个数∗2∣首项−末项∣
例3 - 递归快排
快速排序分区没分好的极端情况
T(n)=T(n−1)+T(1)+nT(n) = T(n-1) + T(1) + nT(n)=T(n−1)+T(1)+n,T(1)=cT(1) = cT(1)=c
T(n)=T(n−1)+c+nT(n) = T(n-1) + c + nT(n)=T(n−1)+c+n
下面为展开过程
T(n)=T(n−2)+c+(n−1)+c+nT(n) = T(n-2) + c + (n-1) + c + nT(n)=T(n−2)+c+(n−1)+c+n
T(n)=T(n−3)+c+(n−2)+c+(n−1)+c+nT(n) = T(n-3) + c + (n-2) + c + (n-1) + c + nT(n)=T(n−3)+c+(n−2)+c+(n−1)+c+n
…
T(n)=T(n−(n−1))+(n−1)c+2+...+n=n22+2cn+n2−1T(n) = T(n-(n-1)) + (n-1)c + 2+...+n = \\frac{n^2}{2} + \\frac{2cn+n}{2} -1T(n)=T(n−(n−1))+(n−1)c+2+...+n=2n2+22cn+n−1
时间复杂度 O(n2)O(n^2)O(n2)
不会推导的同学可以进入 https://www.wolframalpha.com/
- 例1 输入 f(n) = f(n - 1) + c, f(1) = c
- 例2 输入 f(n) = f(n - 1) + n, f(1) = c
- 例3 输入 f(n) = f(n - 1) + n + c, f(1) = c