巧用递归算法:破解编程难题的“秘密武器”

专栏:算法的魔法世界

个人主页:手握风云

目录

一、递归

二、例题讲解

2.1. 汉诺塔问题

2.2. 合并两个有序链表

2.3. 反转链表

2.4. 两两交换链表中的节点

2.5. Pow(x, n)

三、总结


一、递归

  • 递归的概念

        一个方法在执行过程中调用自身, 就称为递归。比如前面讲到过的二叉树的前序遍历、快速排序、归并排序。二叉树的前序遍历是按照“根结点、左子树、右子树”的顺序进行遍历,当遍历到一个孩子结点时,又可以看作是一棵新的二叉树,再按照上面的顺序遍历,遇到空则返回;快速排序的思路是,随机选取一个基准值,比基准值小的放到左边,比基准值大的放到右边,然后左边再按照这个过程继续排序,右边也按照这个过程继续排序;归并排序的实录是选取中点值作为基准,将数组划分为两块进行排序,当数组被划分为只有一个元素时,进行合并排序。

  • 递归的本质

        递归是将主问题划分为解决方法相同的子问题,而子问题又可以划分为解决方法相同的子问题。当我们在解决子问题的时候就依然可以调用该方法来实现。

  • 宏观的视角看待递归

        这里我们不必在意递归的细节展开图,否则学起来会非常痛苦的。我们把递归的方法当成一个黑盒,只在乎它返回给我们的结果,不去在意这个过程是如何执行的。我们以二叉树的前序遍历为例:我们只需要把根结点传入黑盒中,打印根结点的值;再去遍历左子树,把左孩子结点传入PreOrder方法里面;再去遍历右子树,把右孩子结点传入PreOrder方法里面。我们不必在意那些细节是如何执行的,只需要每一层是如何操作的。当叶子结点的左孩子结点或者右孩子结点为空,就不能再分割成下一个子问题了,此时就是递归方法的出口了。

public void PreOrder(TreeNode root){if(root == null){return;}System.out.print(root.val+" ");PreOrder(root.left);PreOrder(root.right);
}
  • 如何写好一个递归

        1.先找到相同的子问题(重点)!这里涉及到递归方法的方法头设计与子问题的设计是相同的。2.只关心某一个子问题是如何执行的,有关方法体的书写。3.注意递归方法的出口。

二、例题讲解

2.1. 汉诺塔问题

        我们先来模拟一下示例1的过程:先将A中的0移动到C上,再将A中的1移动B上,然后将C中的0移动到B上,接着将A的2移动到C上,再把B中的0移动到A上,继续将B中的1移动到C上,最后把0移动到C上。

        我们首先要搞懂为什么汉诺塔可以用递归来解决?我们先来看N=1的情况,就可以直接将盘子移动到C上;当N=2时,先利用B进行辅助,将0移动到B上,再将1移动到C上,最后将0移动到C上;当N=3时,把最上面两个的0和1先转移到C上,过程可以参照N=2的过程,再将2转移到C上,B上的两个盘子按照第一步的过程转移到C上;而当N=4时,我们也可以把最上面的3个先转移到B上,再将最大的盘子移到C上,最后将B上的盘子移动到C上。

        编写递归代码:1.先写出方法的头,该方法的过程都是先将A上的盘子借助B转移到C上,所以我们就可以写作;2.方法体的书写,先将最上面的n-1个盘子转移到B上,接着将最大的盘子转移到C上,最后再把B上的盘子转移到C上;最后确定一下递归的出口,当n=1时,与其他过程不一样,直接把A上的盘子放到C上,不需要借助B。

//方法头
private void dfs(List A,List B,List C,int n);
//方法体的书写
dfs(A,C,B,n-1);
C.add(A.remove(A.size() - 1));
dfs(B,A,C,n-1);

        完整代码实现:

class Solution {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A, B, C, A.size());}private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {if (n == 1) {c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, n - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, n - 1);}
}

2.2. 合并两个有序链表

        我们在数据结构里面已经讲过:先创建一个傀儡结点当作新链表的头结点,然后利用双指针遍历两个链表,结点值小的放在傀儡结点之后,同时指针向后移动,同时还得需要一个tmp引用永远指向新链表的尾结点,这样方便构建新的链表。

        本次我们将以递归的方式来完成这道题。我们还是利用双指针的做法,这里我们不创建傀儡结点,直接以两个链表较小的结点值作为新链表的头结点,然后以两个链表剩下的部分再继续进行合并两个有序链表的操作。递归的过程:先比较结点值的大小,结点值小的结点接入新链表中,同时指针向后移动。当两个指针都为空时,递归结束。

        完整代码实现:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null) return list2;if(list2 == null) return list1;if(list1.val >= list2.val){list2.next = mergeTwoLists(list1,list2.next);return list2;}else {list1.next =  mergeTwoLists(list1.next,list2);return list1;}}
}

2.3. 反转链表

        我们在数据结构的部分也分析过这道题:先将链表的头节点置为空,然后将剩下的结点以头插的方式进行反转。

        宏观视角:我们先思考如何将前两个结点进行反转,将head.next.next的引用指向head,再将head.next置为空,但这样后面的结点会丢失,所以这种做法不可取。如果我们先将头结点后面的部分进行反转,然后再将反转后的尾结点连上反转前的头节点即可。

        将链表看作一棵树:我们将链表看作一棵只有一个叶子结点的树形结构,先对二叉树进行深度遍历,直到遍历到最后的空结点,然后返回尾结点作为新链表的头结点,然后再返回。当返回上一个结点时,将结点5的next指向4,将结点4的next置为空,因为这样就可以也将结点1的next也同样置为空。这样当我们返回到结点1时,既可以将前面的部分反转,也可以将结点1置为空。

        完整代码实现:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) return head;ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

2.4. 两两交换链表中的节点

        利用上一题的思路,也可以利用宏观视角,传入头结点,直接利用给定的方法当作递归的方法头,先交换前两个结点,后面的看作是一个整体,具体怎么交换我们不关心,只需要相信swapPairs方法一定能够交换。将后面以交换的部分与前两个已经交换的结点连起来,就能得到最终结果。我们先让结点2的next指向结点1,再让结点1的next指向结点4,就可以完成前两个结点交换,并且逆置后的引用也会指向后面剩余的结点。当结点为空时,就是递归的出口。

        完整代码实现:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode tmp = swapPairs(head.next.next);ListNode ret = head.next;ret.next = head;head.next = tmp;return ret;}
}

2.5. Pow(x, n)

        这道题要让我们实现快速幂的算法。比如我们要求3^{16},如果利用循环,就需要将3累乘16次,但如果我们采取递归的思路,先将3^{16}拆成3^{8}3^{8}相乘,再将3^{8}拆成3^{4}3^{4}……直到将其拆分为1。递归的方法头,也就是题目当中所给的myPow方法,每一个子问题是要求tmp = myPow(x,n/2)。如果n是偶数,就直接返回tmp*tmp;如果n是奇数,最后还得再乘一个x。如果n=0,直接返回1,同时也是递归的出口。如果n是负数,我们只需返回它的倒数即可。

        完整代码实现:

class Solution {public double myPow(double x, int n) {return n < 0 ? 1 / pow(x, -n) : pow(x, n);}public double pow(double x, int n) {if (n == 0) return 1.0;double tmp = pow(x, n / 2);return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;}
}

三、总结

        递归与循环一样,都是去执行相同的子问题,那么二者之间是可以相互转化的,那么我们什么时候用循环迭代效率更好,什么时候用递归效率更高。

        如下图所示,递归的细节展开图与二叉树的深搜极其相似。我们要想将递归转化为循环的话,就得借助栈来实现,因为当我们遍历一个子问题,我们需要保存上一个的信息方便调用方法执行右侧。但一个递归的细节展开图越复杂时,用递归就比较好解决;如果展开图只有一个分支,用循环迭代就比较方便。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/66.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 一、斐波那契数 相关题目&#xff1a;Leetcode509 文档讲解&#xff1a;Leetcode509 视频讲解&#xff1a;Leetcode509 1. Leetcode509. 斐波那契数 斐波那契数 &#xff08;通常…

CAD导入arcgis中保持面积不变的方法

1、加载CAD数据&#xff0c;选择面数据&#xff0c;如下&#xff1a; 2、加载进来后&#xff0c;右键导出数据&#xff0c;导出成面shp数据&#xff0c;如下&#xff1a; 3、选择存储路径&#xff0c;导出面后计算面积&#xff0c;如下&#xff1a; 4、与CAD中的闭合线面积核对…

备赛蓝桥杯-Python-考前突击

额&#xff0c;&#xff0c;离蓝桥杯开赛还有十个小时&#xff0c;最近因为考研复习节奏的问题&#xff0c;把蓝桥杯的优先级后置了&#xff0c;突然才想起来还有一个蓝桥杯呢。。 到目前为止python基本语法熟练了&#xff0c;再补充一些常用函数供明天考前再背背&#xff0c;算…

Matlab 汽车ABS的bangbang控制和模糊PID控制

1、内容简介 Matlab 197-汽车ABS的bangbang控制和模糊PID控制 可以交流、咨询、答疑 2、内容说明 略 摘要&#xff1a;本文旨在设计一种利用模糊控制理论优化的pid控制器&#xff0c;控制abs系统&#xff0c;达到对滑移率最佳控制范围的要求 &#xff0c;所提出的方案采用级联…

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模(C/C++/Java组)

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模&#xff08;C/C/Java组&#xff09; 时间限制: 3s 内存限制: 512MB 提交: 6633 解决: 1263 题目描述 给定 n, m &#xff0c;问是否存在两个不同的数 x, y 使得 1 ≤ x < y ≤ m 且 n mod x n mod y 。 输入格式 输入包含多…

蓝桥杯C/C++省赛/国赛注意事项及运行环境配置

大佬的蓝桥杯考前急救指南 对拍&#xff08;手动生成测试数据&#xff09;代码&#xff1a; #include <bits/stdc.h> // 包含所有标准库的头文件 using namespace std; // 使用标准命名空间int main() {srand(time(0)); // 设置随机数种子为当前时间&#xff0c;确保每次…

13、nRF52xx蓝牙学习(GPIOTE组件方式的任务配置)

下面再来探讨下驱动库如何实现任务的配置&#xff0c;驱动库的实现步骤应该和寄存器方式对应&#xff0c;关 键点就是如何调用驱动库的函数。 本例里同样的对比寄存器方式编写两路的 GPOITE 任务输出&#xff0c;一路配置为输出翻转&#xff0c;一路设 置为输出低电平。和 …

使用Apache POI(Java)创建docx文档和表格

1、引入poi 依赖组件 <dependency><groupId>org.apache.poi</groupId><artifactId>poi-scratchpad</artifactId><version>4.0.0</version> </dependency> <dependency><groupId>org.apache.poi</groupId>&…

利用 RNN 预测股票价格:从数据处理到可视化实战

在金融领域&#xff0c;预测股票价格走势一直是众多投资者和研究者关注的焦点。今天&#xff0c;我们将利用深度学习中的循环神经网络&#xff08;RNN&#xff09;来构建一个简单的股票价格预测模型&#xff0c;并详细介绍从数据加载、预处理、模型搭建、训练到最终结果可视化的…

华为RH2288H V3服务器极速重装:从RedHat到openEuler 24超详细重装指南

1 登录iBMC口 2 配置启动项 点击&#xff1a;配置&#xff0c;点击&#xff1a;系统启动项 点击&#xff1a;单次有效&#xff0c;选择&#xff1a;光驱&#xff0c;点击&#xff1a;保存 3 进Remote Contro 点击&#xff1a;远程控制&#xff0c;进入如下界面 点击&#xff1…

+++++背到厌倦。持续更新

Spring IoC 的工作流程: 读取 BeanDefinition: Spring 容器启动时&#xff0c;会读取 Bean 的配置信息 (例如 XML 配置文件、注解或 Java 代码)&#xff0c;并将这些配置信息转换为 BeanDefinition 对象。创建 Bean 实例: 根据 BeanDefinition 中的信息&#xff0c;Spring 容器…

【机器学习算法】基于python商品销量数据分析大屏可视化预测系统(完整系统源码+数据库+开发笔记+详细启动教程)✅

目录 一、项目背景 二、技术思路 三、算法介绍 四、项目创新点 五、开发技术介绍 六、项目展示 一、项目背景 本项目基于Python技术栈构建了"商品销量数据分析与预测系统"&#xff0c;通过自动化爬取淘宝商品多维数据&#xff08;价格、销量、评价、品类等&a…