数据结构-递归

news/2024/10/31 3:29:10/

递归

概述

定义

计算机科学中,递归是一种解决计算问题的方法,其中解决方案取决于同一类问题的更小子集

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)
}

说明:

  1. 自己调用自己,如果说每个函数对应着一种解决方案,自己调用自己意味着解决方案是一样的(有规律的)
  2. 每次调用,函数处理的数据会较上次缩减(子集),而且最后会缩减至无需继续递归
  3. 内层函数调用(子集处理)完成,外层函数才能算调用完成

原理

假设链表中有 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
}

思路

  1. 确定能否使用递归求解
  2. 推导出递推关系,即父问题与子问题的关系,以及递归的结束条件
    在这里插入图片描述
  • 深入到最里层叫做
  • 从最里层出来叫做
  • 的过程中,外层函数内的局部变量(以及方法参数)并未消失,的时候还可以用到

单路递归 Single Recursion

E01. 阶乘

用递归方法求阶乘

  • 阶乘的定义 n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n,其中 n 为自然数,当然 0! = 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() 开始归,从归打印,自然是逆序的

递推关系

在这里插入图片描述

代码为

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

递推关系

下面的表格列出了数列的前几项

F0F1F2F3F4F5F6F7F8F9F10F11F12F13
01123581321345589144233

实现

public static int f(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return f(n - 1) + f(n - 2);
}

执行流程
在这里插入图片描述

在这里插入图片描述

  • 绿色代表正在执行(对应递),灰色代表执行结束(对应归)
  • 递不到头,不能归,对应着深度优先搜索

时间复杂度

  1. 更多 Fibonacci 参考[^8] [^9] [^10]
  2. 以上时间复杂度分析,未考虑大数相加的因素

变体1 - 兔子问题[^8]
在这里插入图片描述

  • 第一个月,有一对未成熟的兔子
  • 第二个月,它们成熟
  • 第三个月,它们能产下一对新的小兔
  • 所有兔子遵循相同规律,求第 n 个月的兔子数

分析

兔子问题如何与斐波那契联系起来呢?设第 n 个月兔子数为 f(n)

  • f(n) = 上个月兔子数 + 新生的小兔子数
  • 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
  • 因为需要一个月兔子就成熟,所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
  • 上个月兔子数,即 f(n-1)
  • 上上个月的兔子数,即 f(n-2)

因此本质还是斐波那契数列,只是从其第一项开始

变体2 - 青蛙爬楼梯

  • 楼梯有 n 阶
  • 青蛙要爬到楼顶,可以一次跳一阶,也可以一次跳两阶
  • 只能向上跳,问有多少种跳法

分析

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(3) 重复了 2 次
  • f(2) 重复了 3 次
  • f(1) 重复了 5 次
  • f(0) 重复了 3 次

随着 n 的增大,重复次数非常可观,如何优化呢?

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)
  • 请自行验证改进后的效果
  • 请自行分析改进后的空间复杂度

注意

  1. 记忆法是动态规划的一种情况,强调的是自顶向下的解决
  2. 记忆法的本质是空间换时间

递归优化-尾递归

爆栈

用递归做 n + (n-1) + (n-2) … + 1

public static long sum(long n) {if (n == 1) {return 1;}return n + sum(n - 1);
}

在我的机器上 n = 12000 时,爆栈了

Exception in thread "main" java.lang.StackOverflowErrorat 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)...

为什么呢?

  • 每次方法调用是需要消耗一定的栈内存的,这些内存用来存储方法参数、方法内局部变量、返回地址等等
  • 方法调用占用的内存需要等到方法结束时才会释放
  • 而递归调用我们之前讲过,不到最深不会回头,最内层方法没完成之前,外层方法都结束不了
    • 例如,sum(3) 这个方法内有个需要执行 3 + sum(2),sum(2) 没返回前,加号前面的 3 不能释放
    • 看下面伪码
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]的编译器能够对尾调用做优化,例如
从Java8开始,Java不提供尾叫优化(TCO)

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

不出所料,在 n = 11000 时,还是出了异常

println(sum(11000))Exception in thread "main" java.lang.StackOverflowErrorat Main.sum(Main.scala:25)at Main.sum(Main.scala:25)at Main.sum(Main.scala:25)at Main.sum(Main.scala:25)...

这是因为以上代码,还不是尾调用,要想成为尾调用,那么:

  1. 最后一行代码,必须是一次函数调用
  2. 内层函数必须摆脱与外层函数的关系,内层函数执行后不依赖于外层的变量或常量
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

执行流程如下,以伪码表示 sum(4, 0)

// 首次调用
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

T(n) = 2T(\frac{n}{2}) + n^4

  • 此时 x = 1 < 4,由后者决定整个时间复杂度 \Theta(n^4)
  • 如果觉得对数不好算,可以换为求【b 的几次方能等于 a】

例2

T(n) = T(\frac{7n}{10}) + n

  • a=1, b=\frac{10}{7}, x=0, c=1
  • 此时 x = 0 < 1,由后者决定整个时间复杂度 \Theta(n)

例3

T(n) = 16T(\frac{n}{4}) + n^2

  • a=16, b=4, x=2, c=2
  • 此时 x=2 = c,时间复杂度 \Theta(n^2 \log{n})

例4

T(n)=7T(\frac{n}{3}) + n^2

  • a=7, b=3, x=1.?, c=2
  • 此时 x = \log_{3}{7} < 2,由后者决定整个时间复杂度 \Theta(n^2)

例5

T(n) = 7T(\frac{n}{2}) + n^2

  • a=7, b=2, x=2.?, c=2
  • 此时 x = log_2{7} > 2,由前者决定整个时间复杂度 \Theta(n^{\log_2{7}})

例6

T(n) = 2T(\frac{n}{4}) + \sqrt{n}

  • a=2, b=4, x = 0.5, c=0.5
  • 此时 x = 0.5 = c,时间复杂度 \Theta(\sqrt{n}\ \log{n})

例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 = 1
  • 子问题数据规模缩小倍数 b = 2
  • 除递归外执行的计算是常数级 c=0

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

  • 此时 x=0 = c,时间复杂度 \Theta(\log{n})

例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=2
  • 子问题数据规模缩小倍数 b=2
  • 除递归外,主要时间花在合并上,它可以用 f(n) = n 表示

T(n) = 2T(\frac{n}{2}) + n

  • 此时 x=1=c,时间复杂度 \Theta(n\log{n})

例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=2
  • 子问题数据规模缩小倍数
    • 如果分区分的好,b=2
    • 如果分区没分好,例如分区1 的数据是 0,分区 2 的数据是 n-1
  • 除递归外,主要时间花在分区上,它可以用 f(n) = n 表示

情况1 - 分区分的好

T(n) = 2T(\frac{n}{2}) + n

  • 此时 x=1=c,时间复杂度 \Theta(n\log{n})

情况2 - 分区没分好

T(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) + c,T(1) = c

下面为展开过程

T(n) = T(n-2) + c + c

T(n) = T(n-3) + c + c + c

T(n) = T(n-(n-1)) + (n-1)c

  • 其中 T(n-(n-1)) 即 T(1)
  • 带入求得 T(n) = c + (n-1)c = nc

时间复杂度为 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) + n,T(1) = c

下面为展开过程

T(n) = T(n-2) + (n-1) + n

T(n) = T(n-3) + (n-2) + (n-1) + n

T(n) = T(1) + 2 + … + n = T(1) + (n-1)\frac{2+n}{2} = c + \frac{n^2}{2} + \frac{n}{2} -1

时间复杂度 O(n^2)

注:

  • 等差数列求和为 个数*\frac{\vert首项-末项\vert}{2}

例3 - 递归快排

快速排序分区没分好的极端情况

T(n) = T(n-1) + T(1) + n,T(1) = c

T(n) = T(n-1) + c + n

下面为展开过程

T(n) = T(n-2) + c + (n-1) + c + n

T(n) = T(n-3) + c + (n-2) + c + (n-1) + c + n

T(n) = T(n-(n-1)) + (n-1)c + 2+…+n = \frac{n^2}{2} + \frac{2cn+n}{2} -1

时间复杂度 O(n^2)

不会推导的同学可以进入 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

E03. 二分查找

public static int binarySearch(int[] a, int target) {return recursion(a, target, 0, a.length - 1);
}public static int recursion(int[] a, int target, int i, int j) {if (i > j) {return -1;}int m = (i + j) >>> 1;if (target < a[m]) {return recursion(a, target, i, m - 1);} else if (a[m] < target) {return recursion(a, target, m + 1, j);} else {return m;}
}

E04. 冒泡排序

public static void main(String[] args) {int[] a = {3, 2, 6, 1, 5, 4, 7};bubble(a, 0, a.length - 1);System.out.println(Arrays.toString(a));
}private static void bubble(int[] a, int low, int high) {if(low == high) {return;}int j = low;for (int i = low; i < high; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);j = i;}}bubble(a, low, j);
}private static void swap(int[] a, int i, int j) {int t = a[i];a[i] = a[j];a[j] = t;
}
  • low 与 high 为未排序范围
  • j 表示的是未排序的边界,下一次递归时的 high
    • 发生交换,意味着有无序情况
    • 最后一次交换(以后没有无序)时,左侧 i 仍是无序,右侧 i+1 已然有序
  • 视频中讲解的是只考虑 high 边界的情况,参考以上代码,理解在 low … high 范围内的处理方法

E05. 插入排序

public static void main(String[] args) {int[] a = {3, 2, 6, 1, 5, 7, 4};insertion(a, 1, a.length - 1);System.out.println(Arrays.toString(a));
}private static void insertion(int[] a, int low, int high) {if (low > high) {return;}int i = low - 1;int t = a[low];while (i >= 0 && a[i] > i) {a[i + 1] = a[i];i--;}if(i + 1 != low) {a[i + 1] = t;}    insertion(a, low + 1, high);
}
  • 已排序区域:[0 … i … low-1]
  • 未排序区域:[low … high]
  • 视频中讲解的是只考虑 low 边界的情况,参考以上代码,理解 low-1 … high 范围内的处理方法
  • 扩展:利用二分查找 leftmost 版本,改进寻找插入位置的代码

E06. 约瑟夫问题[^16]

n 个人排成圆圈,从头开始报数,每次数到第 m 个人(m 从 1 开始)杀之,继续从下一个人重复以上过程,求最后活下来的人是谁?

方法1

根据最后的存活者 a 倒推出它在上一轮的索引号

f(n,m)本轮索引为了让 a 是这个索引,上一轮应当这样排规律
f(1,3)0x x x a(0 + 3) % 2
f(2,3)1x x x 0 a(1 + 3) % 3
f(3,3)1x x x 0 a(1 + 3) % 4
f(4,3)0x x x a(0 + 3) % 5
f(5,3)3x x x 0 1 2 a(3 + 3) % 6
f(6,3)0x x x a

方法2

设 n 为总人数,m 为报数次数,解返回的是这些人的索引,从0开始

f(n, m)规律
f(1, 3)0
f(2, 3)0 1 => 13%2=1
f(3, 3)0 1 2 => 0 13%3=0
f(4, 3)0 1 2 3 => 3 0 13%4=3
f(5, 3)0 1 2 3 4 => 3 4 0 13%5=3
f(6, 3)0 1 2 3 4 5 => 3 4 5 0 13%6=3

一. 找出等价函数

规律:下次报数的起点为 k = m % n

  • 首次出列人的序号是 k-1,剩下的的 n-1 个人重新组成约瑟夫环
  • 下次从 k 开始数,序号如下
    • k,\ k+1, \ …\ ,\ 0,\ 1,\ k-2,如上例中 3\ 4\ 5\ 0\ 1

这个函数称之为 g(n-1,m),它的最终结果与 f(n,m) 是相同的。

二. 找到映射函数

现在想办法找到 g(n-1,m) 与 f(n-1, m) 的对应关系,即

3 \rightarrow 0 \
4 \rightarrow 1 \
5 \rightarrow 2 \
0 \rightarrow 3 \
1 \rightarrow 4 \

映射函数为

mapping(x) =
\begin{cases}
x-k & x=[k…n-1] \
x+n-k & x=[0…k-2]
\end{cases}

等价于下面函数

mapping(x) = (x + n - k)%{n}

代入测试一下

3 \rightarrow (3+6-3)%6 \rightarrow 0 \
4 \rightarrow (4+6-3)%6 \rightarrow 1 \
5 \rightarrow (5+6-3)%6 \rightarrow 2 \
0 \rightarrow (0+6-3)%6 \rightarrow 3 \
1 \rightarrow (1+6-3)%6 \rightarrow 4 \

综上有

f(n-1,m) = mapping(g(n-1,m))

三. 求逆映射函数

映射函数是根据 x 计算 y,逆映射函数即根据 y 得到 x

mapping^{-1}(x) = (x + k)%n

代入测试一下

0 \rightarrow (0+3)%6 \rightarrow 3 \
1 \rightarrow (1+3)%6 \rightarrow 4 \
2 \rightarrow (2+3)%6 \rightarrow 5 \
3 \rightarrow (3+3)%6 \rightarrow 0 \
4 \rightarrow (4+3)%6 \rightarrow 1 \

因此可以求得

g(n-1,m) = mapping^{-1}(f(n-1,m))

四. 递推式

代入推导

\begin{aligned}
f(n,m) = \ & g(n-1,m) \
= \ & mapping^{-1}(f(n-1,m)) \
= \ & (f(n-1,m) + k) % n \
= \ & (f(n-1,m) + m%n) % n \
= \ & (f(n-1,m) + m) % n \
\end{aligned}

最后一步化简是利用了模运算法则

(a+b)%n = (a%n + b%n) %n 例如

  • (6+6)%5 = 2 = (6+6%5)%5
  • (6+5)%5 = 1 = (6+5%5)%5
  • (6+4)%5 = 0 = (6+4%5)%5

最终递推式

f(n,m) =
\begin{cases}
(f(n-1,m) + m) % n & n>1\
0 & n = 1
\end{cases}

E02. 汉诺塔[^13]

Tower of Hanoi,是一个源于印度古老传说:大梵天创建世界时做了三根金刚石柱,在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘,大梵天命令婆罗门把圆盘重新摆放在另一根柱子上,并且规定

  • 一次只能移动一个圆盘
  • 小圆盘上不能放大圆盘

下面的动图演示了4片圆盘的移动方法
在这里插入图片描述

使用程序代码模拟圆盘的移动过程,并估算出时间复杂度

思路

  • 假设每根柱子标号 a,b,c,每个圆盘用 1,2,3 … 表示其大小,圆盘初始在 a,要移动到的目标是 c

  • 如果只有一个圆盘,此时是最小问题,可以直接求解

    • 移动圆盘1 a ——> c
  • 如果有两个圆盘,那么

    • 圆盘1 a ——> b
    • 圆盘2 a ——> c
    • 圆盘1 b ——> c
  • 如果有三个圆盘,那么

    • 圆盘12 a ——> b
    • 圆盘3 a ——> c
    • 圆盘12 b ——> c
  • 如果有四个圆盘,那么

    • 圆盘 123 a ——> b
    • 圆盘4 a ——> c
    • 圆盘 123 b ——> c

题解

public class E02HanoiTower {/*源 借 目h(4, a, b, c) -> h(3, a, c, b)a -> ch(3, b, a, c)*/static LinkedList<Integer> a = new LinkedList<>();static LinkedList<Integer> b = new LinkedList<>();static LinkedList<Integer> c = new LinkedList<>();static void init(int n) {for (int i = n; i >= 1; i--) {a.add(i);}}static void h(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {if (n == 0) {return;}h(n - 1, a, c, b);c.addLast(a.removeLast());print();h(n - 1, b, a, c);}private static void print() {System.out.println("-----------------------");System.out.println(a);System.out.println(b);System.out.println(c);}public static void main(String[] args) {init(3);print();h(3, a, b, c);}
}

E03. 杨辉三角[^6]

分析

把它斜着看

        11   11   2   11   3   3   1
1   4   6   4   1
  • 行 i,列 j,那么 [i][j] 的取值应为 [i-1][j-1] + [i-1][j]
  • 当 j=0 或 i=j 时,[i][j] 取值为 1

题解

public static void print(int n) {for (int i = 0; i < n; i++) {if (i < n - 1) {System.out.printf("%" + 2 * (n - 1 - i) + "s", " ");}for (int j = 0; j < i + 1; j++) {System.out.printf("%-4d", element(i, j));}System.out.println();}
}public static int element(int i, int j) {if (j == 0 || i == j) {return 1;}return element(i - 1, j - 1) + element(i - 1, j);
}

优化1

是 multiple recursion,因此很多递归调用是重复的,例如

  • recursion(3, 1) 分解为
    • recursion(2, 0) + recursion(2, 1)
  • 而 recursion(3, 2) 分解为
    • recursion(2, 1) + recursion(2, 2)

这里 recursion(2, 1) 就重复调用了,事实上它会重复很多次,可以用 static AtomicInteger counter = new AtomicInteger(0) 来查看递归函数的调用总次数

事实上,可以用 memoization 来进行优化:

public static void print1(int n) {int[][] triangle = new int[n][];for (int i = 0; i < n; i++) {// 打印空格triangle[i] = new int[i + 1];for (int j = 0; j <= i; j++) {System.out.printf("%-4d", element1(triangle, i, j));}System.out.println();}
}public static int element1(int[][] triangle, int i, int j) {if (triangle[i][j] > 0) {return triangle[i][j];}if (j == 0 || i == j) {triangle[i][j] = 1;return triangle[i][j];}triangle[i][j] = element1(triangle, i - 1, j - 1) + element1(triangle, i - 1, j);return triangle[i][j];
}
  • 将数组作为递归函数内可以访问的遍历,如果 triangle[i][j] 已经有值,说明该元素已经被之前的递归函数计算过,就不必重复计算了

优化2

public static void print2(int n) {int[] row = new int[n];for (int i = 0; i < n; i++) {// 打印空格createRow(row, i);for (int j = 0; j <= i; j++) {System.out.printf("%-4d", row[j]);}System.out.println();}
}private static void createRow(int[] row, int i) {if (i == 0) {row[0] = 1;return;}for (int j = i; j > 0; j--) {row[j] = row[j - 1] + row[j];}
}

注意:还可以通过每一行的前一项计算出下一项,不必借助上一行,这与杨辉三角的另一个特性有关,暂不展开了

力扣对应题目,但递归不适合在力扣刷高分,因此只列出相关题目,不做刷题讲解了

  • 118. 杨辉三角 - 力扣(LeetCode)
  • 119. 杨辉三角 II - 力扣(LeetCode)

http://www.ppmy.cn/news/242744.html

相关文章

Android RK3588-12 默认开启位置信息

默认开启位置信息 modified: frameworks/base/packages/SettingsProvider/res/values/defaults.xml diff --git a/frameworks/base/packages/SettingsProvider/res/values/defaults.xml b/frameworks/base/packages/SettingsProvider/res/values/defaults.xml index ca3c14b…

uni-app 启动手机模拟器

1、下载蓝叠模拟器 下载完成后设置 adb链接和root 设置竖屏 2、设置uni-app adb 环境变量 在 HBuilderX目录下>plugins目录下>launcher目录下>tools目录下>adbs 复制该路径后打开电脑高级环境变量 3、配置 HBuilderX adb 点击工具>设置>运行配置配置adb路…

android ps2 模拟器,手机目前安卓系统PS2模拟器最好用的是一款叫做呆萌PS2模拟器的APP!这一款竟然是国产的!...

原标题&#xff1a;手机目前安卓系统PS2模拟器最好用的是一款叫做呆萌PS2模拟器的APP&#xff01;这一款竟然是国产的&#xff01; 手机目前安卓系统是有PS2模拟器的&#xff0c;最好用的是一款叫做呆萌PS2模拟器的APP&#xff0c;而且这一款还是国人开发的哦&#xff0c;以下我…

uniapp app运行到手机模拟器

用过两种模拟器&#xff0c;一种是mumu模拟器&#xff0c;一种是雷电模拟器 模拟器下好后 mumu模拟器 按照官方说的来就行&#xff0c;官方链接 mumu模拟器的默认端口是7555 然后就可以运行了 雷电模拟器 雷电模拟器 雷电模拟器 先到设置里多点几次版本号打开开发者选项 打…

安卓psp模拟器哪个好_手机psp模拟器哪个好_安卓PSP模拟器中文官方版下载_66游戏网...

模拟器PSP是为PlayStation(PSP)Android平台伟大的模拟器内置800款PSP游戏。你可以发挥自己的PSP游戏在Android设备上。在有额外的功能和最佳的游戏兼容性高清晰度顶级最好的游戏体验。仿真器PSP行之有效的大多数智能手机和平板电脑。这是PSP上最好的模拟器&#xff0c;具有良好…

移动端必备——手机模拟器

作为一个测试&#xff0c;今天才知道有手机模拟器的存在真的是有点过分了&#xff08;作为一个不玩游戏且主要测试web端的测试而言也挺正常的&#xff09;&#xff0c;如果要测试移动端&#xff0c;这个真的是一个神器。今天体验了一下觉得真的蛮不错的&#xff0c;只是有些深入…

Android模拟器群控,安卓模拟器多开哪个好 流畅不卡、省资源、群控刷机都有

原标题&#xff1a;安卓模拟器多开哪个好 流畅不卡、省资源、群控刷机都有 安卓模拟器多开哪个好呢?一般多开的玩家分为两种&#xff0c;一种就是自己多开挂机玩&#xff0c;另外一种就是工作室需求&#xff0c;需要挂机开更多&#xff0c;对安卓模拟器多开的流畅性、稳定性及…

Charles配合手机模拟器抓取APP数据包教程

本教程演示在Mac OS Monterey 12.2.1版本的操作系统上&#xff0c;使用的Charles的版本是1.9.56&#xff0c;模拟器为网易MuMu模拟器&#xff0c;版本号4.6.2。 Charles的设置 相关软件的安装此处不再展开描述&#xff0c;正常来说&#xff0c;安装Charles和MuMu模拟器&#…