递归的实战演练(进阶) | 算法必看系列六

本文涉及的产品
函数计算FC,每月15万CU 3个月
简介: 通过实际题目(初级题、中级题&高阶题)深入理解递归四步解题套路。

原文链接

递归的实战演练(进阶)

初级题

接下来我们来看下一道经典的题目: 反转二叉树 将左边的二叉树反转成右边的二叉树。
image.png
接下来让我们看看用我们之前总结的递归解法四步曲如何解题。
1.定义一个函数,这个函数代表了翻转以 root 为根节点的二叉树

publicstaticclass TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode invertTree(TreeNode root) {
}

2.查找问题与子问题的关系,得出递推公式 我们之前说了,解题要采用自上而下的思考方式,那我们取前面的1, 2,3 结点来看,对于根节点 1 来说,假设 2, 3 结点下的节点都已经翻转,那么只要翻转 2, 3 节点即满足需求

image.png
对于2, 3 结点来说,也是翻转其左右节点即可,依此类推,对每一个根节点,依次翻转其左右节点,所以我们可知问题与子问题的关系是 翻转(根节点) = 翻转(根节点的左节点) + 翻转(根节点的右节点) 即

invert(root) = invert(root->left) + invert(root->right)

而显然递归的终止条件是当结点为叶子结点时终止(因为叶子节点没有左右结点)

3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中

public TreeNode invertTree(TreeNode root) {
    // 叶子结果不能翻转
    if (root == null) {
        returnnull;
    }
    // 翻转左节点下的左右节点
    TreeNode left = invertTree(root.left);
    // 翻转右节点下的左右节点
    TreeNode right = invertTree(root.right);

    // 左右节点下的二叉树翻转好后,翻转根节点的左右节点
    root.right = left;
    root.left = right;
    return root;
}

4.时间复杂度分析 由于我们会对每一个节点都去做翻转,所以时间复杂度是 O(n),那么空间复杂度呢,这道题的空间复杂度非常有意思,我们一起来看下,由于每次调用 invertTree 函数都相当于一次压栈操作, 那最多压了几次栈呢, 仔细看上面函数的下一段代码

TreeNode left = invertTree(root.left);

从根节点出发不断对左结果调用翻转函数, 直到叶子节点,每调用一次都会压栈,左节点调用完后,出栈,再对右节点压栈....,下图可知栈的大小为3, 即树的高度,如果是完全二叉树 ,则树的高度为logn, 即空间复杂度为O(logn)
image.png
最坏情况,如果此二叉树是如图所示(只有左节点,没有右节点),则树的高度即结点的个数 n,此时空间复杂度为 O(n),总的来看,空间复杂度为O(n)
image.png
说句题外话,这道题当初曾引起轰动,因为 Mac 下著名包管理工具 homebrew 的作者 Max Howell 当初解不开这道题,结果被 Google 拒了,也就是说如果你解出了这道题,就超越了这位世界大神,想想是不是很激动。

中级题

接下来我们看一下大学时学过的汉诺塔问题:  如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数
image.png
接下来套用我们的递归四步法看下这题怎么解
1.定义问题的递归函数,明确函数的功能,我们定义这个函数的功能为:把 A 上面的 n 个圆盘经由 B 移到 C

// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
}

2.查找问题与子问题的关系 首先我们看如果 A 柱子上只有两块圆盘该怎么移

image.png
前面我们多次提到,分析问题与子问题的关系要采用自上而下的分析方式,要将 n 个圆盘经由 B 移到 C 柱上去,可以按以下三步来分析:
将上面的 n-1 个圆盘看成是一个圆盘,这样分析思路就与上面提到的只有两块圆盘的思路一致了;
将上面的 n-1 个圆盘经由 C 移到 B ,此时将 A 底下的那块最大的圆盘移到 C ;
再将 B 上的 n-1 个圆盘经由A移到 C上
有人问第一步的 n - 1 怎么从 C 移到 B,重复上面的过程,只要把 上面的 n-2个盘子经由 A 移到 B, 再把A最下面的盘子移到 C,最后再把上面的 n - 2 的盘子经由A 移到 B 下..., 怎么样,是不是找到规律了,不过在找问题的过程中 切忌把子问题层层展开,到汉诺塔这个问题上切忌再分析 n-3,n-4 怎么移,这样会把你绕晕,只要找到一层问题与子问题的关系得出可以用递归表示即可。

由以上分析可得

move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C`)

一定要先得出递归公式,哪怕是伪代码也好!这样第三步推导函数编写就容易很多,终止条件我们很容易看出,当 A 上面的圆盘没有了就不移了
3.根据以上的递归伪代码补充函数的功能

// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) {
        return;
    }
    // 将上面的  n-1 个圆盘经由 C 移到 B
    hanoid(n-1, a, c, b);
    // 此时将 A 底下的那块最大的圆盘移到 C
    move(a, c);
    // 再将 B 上的 n-1 个圆盘经由A移到 C上
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}

从函数的功能上看其实比较容易理解,整个函数定义的功能就是把 A 上的 n 个圆盘 经由 B 移到 C,由于定义好了这个函数的功能,那么接下来的把 n-1 个圆盘 经由 C 移到 B 就可以很自然的调用这个函数,所以明确函数的功能非常重要,按着函数的功能来解释,递归问题其实很好解析,切忌在每一个子问题上层层展开死抠,这样这就陷入了递归的陷阱,计算机都会栈溢出,何况人脑
4.时间复杂度分析 从第三步补充好的函数中我们可以推断出

f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1 = 2(2f(n-2) + 1) + 1 = 2 * 2 * f(n-2) + 2 + 1 = 22 * f(n-3) + 2 + 1 = 22 * f(n-3) + 2 + 1 =  22 * (2f(n-4) + 1) = 23 * f(n-4) + 22  + 1 = ....        // 不断地展开 = 2n-1 + 2n-2 + ....+ 1

显然时间复杂度为 O(2^n),很明显指数级别的时间复杂度是不能接受的,汉诺塔非递归的解法比较复杂,大家可以去网上搜一下

进阶题

现实中大厂中的很多递归题都不会用上面这些相对比较容易理解的题,更加地是对递归问题进行相应地变形, 来看下面这道题

细胞分裂 有一个细胞 每一个小时分裂一次,一次分裂一个子细胞,第三个小时后会死亡。那么n个小时候有多少细胞?

照样我们用前面的递归四步曲来解
1.定义问题的递归函数,明确函数的功能 我们定义以下函数为 n 个小时后的细胞数

public int allCells(int n) {
}

2.接下来寻找问题与子问题间的关系(即递推公式) 首先我们看一下一个细胞出生到死亡后经历的所有细胞分裂过程

image.png
图中的 A 代表细胞的初始态, B代表幼年态(细胞分裂一次), C 代表成熟态(细胞分裂两次),C 再经历一小时后细胞死亡 以 f(n) 代表第 n 小时的细胞分解数 fa(n) 代表第 n 小时处于初始态的细胞数, fb(n) 代表第 n 小时处于幼年态的细胞数 fc(n) 代表第 n 小时处于成熟态的细胞数 则显然 f(n) = fa(n) + fb(n) + fc(n) 那么 fa(n) 等于多少呢,以n = 4 (即一个细胞经历完整的生命周期)为例
仔细看上面的图
可以看出 fa(n) = fa(n-1) + fb(n-1) + fc(n-1), 当 n = 1 时,显然 fa(1) = 1

fb(n) 呢,看下图可知 fb(n) = fa(n-1)。当 n = 1 时 fb(n) = 0
image.png
fc(n) 呢,看下图可知 fc(n) = fb(n-1)。当 n = 1,2 时 fc(n) = 0
image.png
综上, 我们得出的递归公式如下
image.png
3.根据以上递归公式我们补充一下函数的功能

public int allCells(int n) {
    return aCell(n) + bCell(n) + cCell(n);
}

/**
 * 第 n 小时 a 状态的细胞数
 */
public int aCell(int n) {
    if(n==1){
        return1;
    }else{
        return aCell(n-1)+bCell(n-1)+cCell(n-1);
    }
}

/**
 * 第 n 小时 b 状态的细胞数
 */
public int bCell(int n) {
    if(n==1){
        return0;
    }else{
        return aCell(n-1);
    }
}

/**
 * 第 n 小时 c 状态的细胞数
 */
public int cCell(int n) {
    if(n==1 || n==2){
        return0;
    }else{
        return bCell(n-1);
    }
}

只要思路对了,将递推公式转成代码就简单多了,另一方面也告诉我们,可能一时的递归关系我们看不出来,此时可以借助于画图来观察规律

4.求时间复杂度 由第二步的递推公式我们知道 f(n) = 2aCell(n-1) + 2aCell(n-2) + aCell(n-3)

之前青蛙跳台阶时间复杂度是指数级别的,而这个方程式显然比之前的递推公式(f(n) = f(n-1) + f(n-2)) 更复杂的,所以显然也是指数级别的

总结

大部分递归题其实还是有迹可寻的, 按照之前总结的解递归的四个步骤可以比较顺利的解开递归题,一些比较复杂的递归题我们需要勤动手,画画图,观察规律,这样能帮助我们快速发现规律,得出递归公式,一旦知道了递归公式,将其转成递归代码就容易多了,很多大厂的递归考题并不能简单地看出递归规律,往往会在递归的基础上多加一些变形,不过万遍不离其宗,我们多采用自顶向下的分析思维,多练习,相信递归不是什么难事。

来源 | 五分钟学算法
作者 | 码海

相关实践学习
【文生图】一键部署Stable Diffusion基于函数计算
本实验教你如何在函数计算FC上从零开始部署Stable Diffusion来进行AI绘画创作,开启AIGC盲盒。函数计算提供一定的免费额度供用户使用。本实验答疑钉钉群:29290019867
建立 Serverless 思维
本课程包括: Serverless 应用引擎的概念, 为开发者带来的实际价值, 以及让您了解常见的 Serverless 架构模式
相关文章
|
10天前
|
存储 缓存 算法
前端算法:优化与实战技巧的深度探索
【10月更文挑战第21天】前端算法:优化与实战技巧的深度探索
10 1
|
25天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
16 1
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
50 2
|
2月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
51 4
|
25天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
31 0
|
3月前
|
机器学习/深度学习 存储 算法
强化学习实战:基于 PyTorch 的环境搭建与算法实现
【8月更文第29天】强化学习是机器学习的一个重要分支,它让智能体通过与环境交互来学习策略,以最大化长期奖励。本文将介绍如何使用PyTorch实现两种经典的强化学习算法——Deep Q-Network (DQN) 和 Actor-Critic Algorithm with Asynchronous Advantage (A3C)。我们将从环境搭建开始,逐步实现算法的核心部分,并给出完整的代码示例。
212 1
|
13天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
10天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
11天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。