2.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) // 1
void f(Node node = 2) {
println("before:" + node.value) // 2
void f(Node node = 3) {
println("before:" + node.value) // 3
void f(Node node = null) {
if(node == null) {
return;
}
}
println("after:" + node.value) // 3
}
println("after:" + node.value) // 2
}
println("after:" + node.value) // 1
}
思路
- 确定能否使用递归求解
- 推导出递推关系,即父问题与子问题的关系,以及递归的结束条件
例如之前遍历链表的递推关系为
- 深入到最里层叫做递
- 从最里层出来叫做归
- 在递的过程中,外层函数内的局部变量(以及方法参数)并未消失,归的时候还可以用到
单路递归 Single Recursion
E01. 阶乘
用递归方法求阶乘
阶乘的定义 ,其中 为自然数,当然
递推关系
代码
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() 开始归,从归打印,自然是逆序的
递推关系
代码为
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
E01. 斐波那契数列
- 之前的例子是每个递归函数只包含一个自身的调用,这称之为 single recursion
- 如果每个递归函数例包含多个自身调用,称之为 multi recursion
递推关系
下面的表格列出了数列的前几项
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);
}
执行流程
- 绿色代表正在执行(对应递),灰色代表执行结束(对应归)
- 递不到头,不能归,对应着深度优先搜索
时间复杂度
- 递归的次数也符合斐波那契规律,
- 时间复杂度推导过程
- 斐波那契通项公式
- 简化为:
- 带入递归次数公式
- 时间复杂度为
- 更多 Fibonacci 参考[8][9][^10]
- 以上时间复杂度分析,未考虑大数相加的因素
变体1 - 兔子问题[^8]
- 第一个月,有一对未成熟的兔子(黑色,注意图中个头较小)
- 第二个月,它们成熟
- 第三个月,它们能产下一对新的小兔子(蓝色)
- 所有兔子遵循相同规律,求第 个月的兔子数
分析
兔子问题如何与斐波那契联系起来呢?设第 n 个月兔子数为
- = 上个月兔子数 + 新生的小兔子数
- 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
- 因为需要一个月兔子就成熟,所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
- 上个月兔子数,即
- 上上个月的兔子数,即
因此本质还是斐波那契数列,只是从其第一项开始
变体2 - 青蛙爬楼梯
- 楼梯有 阶
- 青蛙要爬到楼顶,可以一次跳一阶,也可以一次跳两阶
- 只能向上跳,问有多少种跳法
分析
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)<br />(1,1,2) (2,2) | 最后一跳,跳一个台阶的,基于f(3)<br />最后一跳,跳两个台阶的,基于f(2) |
5 | ... | ... |
因此本质上还是斐波那契数列,只是从其第二项开始
对应 leetcode 题目 70. 爬楼梯 - 力扣(LeetCode)
递归优化-记忆法
上述代码存在很多重复的计算,例如求 递归分解过程
可以看到(颜色相同的是重复的):
- 重复了 2 次
- 重复了 3 次
- 重复了 5 次
- 重复了 3 次
随着 的增大,重复次数非常可观,如何优化呢?
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];
}
优化后的图示,只要结果被缓存,就不会执行其子问题
- 改进后的时间复杂度为
- 请自行验证改进后的效果
- 请自行分析改进后的空间复杂度
注意
- 记忆法是动态规划的一种情况,强调的是自顶向下的解决
- 记忆法的本质是空间换时间
递归优化-尾递归
爆栈
用递归做
public static long sum(long n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}
在我的机器上 时,爆栈了
Exception in thread "main" java.lang.StackOverflowError
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
...
为什么呢?
- 每次方法调用是需要消耗一定的栈内存的,这些内存用来存储方法参数、方法内局部变量、返回地址等等
- 方法调用占用的内存需要等到方法结束时才会释放
- 而递归调用我们之前讲过,不到最深不会回头,最内层方法没完成之前,外层方法都结束不了
- 例如, 这个方法内有个需要执行 , 没返回前,加号前面的 不能释放
- 看下面伪码
long sum(long n = 3) {
return 3 + long sum(long n = 2) {
return 2 + long sum(long n = 1) {
return 1;
}
}
}
尾调用
如果函数的最后一步是调用一个函数,那么称为尾调用,例如
function a() {
return b()
}
下面三段代码不能叫做尾调用
function a() {
const c = b()
return c
}
- 因为最后一步并非调用函数
function a() {
return b() + 1
}
- 最后一步执行的是加法
function a(x) {
return b() + x
}
- 最后一步执行的是加法
一些语言[^11]的编译器能够对尾调用做优化,例如
function a() {
// 做前面的事
return b()
}
function b() {
// 做前面的事
return c()
}
function c() {
return 1000
}
a()
没优化之前的伪码
function a() {
return function b() {
return function c() {
return 1000
}
}
}
优化后伪码如下
a()
b()
c()
为何尾递归才能优化?
调用 a 时
- a 返回时发现:没什么可留给 b 的,将来返回的结果 b 提供就可以了,用不着我 a 了,我的内存就可以释放
调用 b 时
- b 返回时发现:没什么可留给 c 的,将来返回的结果 c 提供就可以了,用不着我 b 了,我的内存就可以释放
如果调用 a 时
- 不是尾调用,例如 return b() + 1,那么 a 就不能提前结束,因为它还得利用 b 的结果做加法
尾递归
尾递归是尾调用的一种特例,也就是最后一步执行的是同一个函数
尾递归避免爆栈
安装 Scala
Scala 入门
object Main {
def main(args: Array[String]): Unit = {
println("Hello Scala")
}
}
- Scala 是 java 的近亲,java 中的类都可以拿来重用
- 类型是放在变量后面的
- Unit 表示无返回值,类似于 void
- 不需要以分号作为结尾,当然加上也对
还是先写一个会爆栈的函数
def sum(n: Long): Long = {
if (n == 1) {
return 1
}
return n + sum(n - 1)
}
- Scala 最后一行代码若作为返回值,可以省略 return
不出所料,在 时,还是出了异常
println(sum(11000))
Exception in thread "main" java.lang.StackOverflowError
at Main$.sum(Main.scala:25)
at Main$.sum(Main.scala:25)
at Main$.sum(Main.scala:25)
at Main$.sum(Main.scala:25)
...
这是因为以上代码,还不是尾调用,要想成为尾调用,那么:
- 最后一行代码,必须是一次函数调用
- 内层函数必须摆脱与外层函数的关系,内层函数执行后不依赖于外层的变量或常量
def sum(n: Long): Long = {
if (n == 1) {
return 1
}
return n + sum(n - 1) // 依赖于外层函数的 n 变量
}
如何让它执行后就摆脱对 n 的依赖呢?
- 不能等递归回来再做加法,那样就必须保留外层的 n
- 把 n 当做内层函数的一个参数传进去,这时 n 就属于内层函数了
- 传参时就完成累加, 不必等回来时累加
sum(n - 1, n + 累加器)
改写后代码如下
@tailrec
def sum(n: Long, accumulator: Long): Long = {
if (n == 1) {
return 1 + accumulator
}
return sum(n - 1, n + accumulator)
}
- accumulator 作为累加器
- @tailrec 注解是 scala 提供的,用来检查方法是否符合尾递归
- 这回 sum(10000000, 0) 也没有问题,打印 50000005000000
执行流程如下,以伪码表示
// 首次调用
def sum(n = 4, accumulator = 0): Long = {
return sum(4 - 1, 4 + accumulator)
}
// 接下来调用内层 sum, 传参时就完成了累加, 不必等回来时累加,当内层 sum 调用后,外层 sum 空间没必要保留
def sum(n = 3, accumulator = 4): Long = {
return sum(3 - 1, 3 + accumulator)
}
// 继续调用内层 sum
def sum(n = 2, accumulator = 7): Long = {
return sum(2 - 1, 2 + accumulator)
}
// 继续调用内层 sum, 这是最后的 sum 调用完就返回最后结果 10, 前面所有其它 sum 的空间早已释放
def sum(n = 1, accumulator = 9): Long = {
if (1 == 1) {
return 1 + accumulator
}
}
本质上,尾递归优化是将函数的递归调用,变成了函数的循环调用
改循环避免爆栈
public static void main(String[] args) {
long n = 100000000;
long sum = 0;
for (long i = n; i >= 1; i--) {
sum += i;
}
System.out.println(sum);
}
递归时间复杂度-Master theorem[^14]
若有递归式
其中
- 是问题的运行时间, 是数据规模
- 是子问题个数
- 是子问题运行时间,每个子问题被拆成原问题数据规模的
- 是除递归外执行的计算
令 ,即
那么
例1
- 此时 ,由后者决定整个时间复杂度
- 如果觉得对数不好算,可以换为求【 的几次方能等于 】
例2
- 此时 ,由后者决定整个时间复杂度
例3
- 此时 ,时间复杂度
例4
- 此时 ,由后者决定整个时间复杂度
例5
- 此时 ,由前者决定整个时间复杂度
例6
- 此时 ,时间复杂度
例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;
}
}
- 子问题个数
- 子问题数据规模缩小倍数
- 除递归外执行的计算是常数级
- 此时 ,时间复杂度
例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);
}
- 子问题个数
- 子问题数据规模缩小倍数
- 除递归外,主要时间花在合并上,它可以用 表示
- 此时 ,时间复杂度
例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)
- 子问题个数
- 子问题数据规模缩小倍数
- 如果分区分的好,
- 如果分区没分好,例如分区1 的数据是 0,分区 2 的数据是
- 除递归外,主要时间花在分区上,它可以用 表示
情况1 - 分区分的好
- 此时 ,时间复杂度
情况2 - 分区没分好
- 此时不能用主定理求解
递归时间复杂度-展开求解
像下面的递归式,都不能用主定理求解
例1 - 递归求和
long sum(long n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}
,
下面为展开过程
...
- 其中 即
- 带入求得
时间复杂度为
例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);
}
,
下面为展开过程
...
时间复杂度
注:
- 等差数列求和为
例3 - 递归快排
快速排序分区没分好的极端情况
,
下面为展开过程
...
时间复杂度
不会推导的同学可以进入 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