【Java算法】递归


🔥个人主页: 中草药
🔥专栏:【算法工作坊】算法实战揭秘
🍇一.递归
概念
递归是一种解决问题的方法,其中函数通过调用自身来求解问题。这种方法的关键在于识别问题是否可以被分解为若干个相似但规模更小的子问题。递归函数有两个主要组成部分:
- 基本情况(Base Case):这是递归调用的终止条件。每个递归函数都必须有一个或多个明确的基本情况,否则递归将无限进行下去。
- 递归步骤(Recursive Step):这是函数调用自身的部分。在此步骤中,问题被分解为更小的子问题,然后递归地求解这些子问题。
递归的本质可以理解为 可以把一个主问题拆分成若干个相同的子问题
宏观的理解递归
递归其实是比较抽象的一种算法,完全熟练的运用它,需要时间的积累与深入的理解,因此我们可以学会宏观的去看待递归,帮助我们去解决算法问题
1.不必过分关注递归的细节展开图
2.把递归的函数看做一个黑盒(不去深究)
3.相信这个黑盒一定能完成这个任务
用法
如何写好一个递归
- 先找到相同的子问题--->函数头的设计
- 只关心某一个子问题是如何解决的--->函数体的书写
- 注意一下递归函数的出口
应用场景
递归非常适合处理以下类型的问题:
- 分治法:问题可以被分解为独立且较小的子问题。
- 树形结构:例如文件系统的目录树、DOM树等。
- 回溯算法:如八皇后问题、迷宫寻路等。
🍈二. 面试题 08.06. 汉诺塔问题
题目链接:面试题 08.06. 汉诺塔问题
代码
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A,B,C,A.size());return;}public 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);}
算法原理
汉诺塔问题是递归问题的一个经典问题,和常规问题一样,拆分成细小的步骤
汉诺塔问题通常有三个柱子A、B、C,以及n个不同大小的圆盘,初始时所有的圆盘都堆叠在柱子A上,要求将它们全部移动到柱子C上,但在移动过程中必须遵守以下规则:
- 每次只能移动一个圆盘。
- 在任何时刻,一个较大圆盘都不能放在较小圆盘上面
代码详解
hanota方法是主入口点,它接受三个列表作为参数,分别代表三个柱子A、B、C。dfs方法是一个递归函数,它接受四个参数:柱子A、B、C以及当前要移动的圆盘数量n。- 当
n == 1时,这是递归的基本情况,直接将A上的最后一个圆盘移动到C。 - 对于
n > 1的情况,首先递归地将n-1个圆盘从A借助B移动到C;然后将A上的最后一个圆盘直接移动到C;最后再递归地将n-1个圆盘从B借助A移动到C。
🍉 三. 21.合并两个有序链表
题目链接:21.合并两个有序链表
代码
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//不能用elseif(list1==null){return list2;}if(list2==null){return list1;}if(list1.val<=list2.val){list1.next=mergeTwoLists(list1.next,list2);return list1;}else{list2.next=mergeTwoLists(list1,list2.next);return list2;}}
算法原理
- 特殊情况处理:首先检查输入的两个链表
list1和list2是否为空。- 如果
list1为空,则直接返回list2。 - 如果
list2为空,则直接返回list1。
- 如果
- 递归合并:如果两个链表都不为空,则比较当前节点的值。
- 如果
list1的当前节点值小于等于list2的当前节点值,那么将list1的next指向list1.next和list2的合并结果,并返回list1。 - 否则,将
list2的next指向list1和list2.next的合并结果,并返回list2。
- 如果
这段代码使用了递归的方式来合并两个有序链表。其基本思想是:
- 基本情况:如果其中一个链表为空,那么合并的结果就是另一个链表。
- 递归步骤:如果两个链表都不为空,则比较当前节点的值。
- 如果
list1的当前节点值小于等于list2的当前节点值,那么list1将成为合并后链表的一部分,然后递归地去合并list1的下一个节点和list2。 - 如果
list2的当前节点值小于list1的当前节点值,那么list2将成为合并后链表的一部分,然后递归地去合并list1和list2的下一个节点。
- 如果
🍊四. 206.反转链表
代码
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;}
算法原理
这里可以比较这道题的 迭代代码 加深理解
public ListNode reverseList1(ListNode head) {if(head==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curn=cur.next;cur.next=head;head=cur;cur=curn;}return head;}
-
基本情况:如果当前节点
head为空或者当前节点是链表的最后一个节点(即head.next == null),那么直接返回head。这是因为如果链表为空或者只剩一个节点,就不需要反转了,直接返回即可。 -
递归步骤:如果当前节点不是最后一个节点,递归地反转
head.next,即反转当前节点之后的所有节点。这里newHead将是反转后的新头节点,即原来链表的最后一个节点成为了新的头节点。 -
链接反转:在递归调用返回后,将当前节点
head连接到新头节点newHead后面。这一步是通过将head.next.next = head;来实现的,即将head插入到新反转链表的头部。- 注意,这里的
head.next是原来链表中的下一个节点,现在它已经是反转链表的头节点了,所以我们通过head.next.next来访问原来链表的下下个节点,现在变成了反转链表的第二个节点。
- 注意,这里的
-
断开连接:将
head的next设为null,这样原来的链表就被切断了,从而完成了反转。
🍋五. 24.两两交换链表中的节点
题目链接:24.两两交换链表中的节点
代码
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;}
算法原理
此代码,建议先用一个小链表模拟实现以下该过程,帮助理解这个递归

基本情况:如果当前节点head为空或head.next为空(即链表为空或只有一个节点),则直接返回head。这是因为单个节点或空链表无需交换。
递归步骤:
- 首先递归地调用
swapPairs(head.next.next),这意味着我们假设head.next.next之后的部分已经被正确地交换好了。递归的目的是处理当前节点之后的所有节点。 tmp变量存储了从head.next.next开始的交换好的链表部分。ret变量存储了head.next,即当前节点的下一个节点,它将成为新的头节点。- 接下来,将
ret.next设置为head,这样就实现了head和head.next这两个节点的交换。 - 最后,将
head.next设置为tmp,这样就将剩余部分的链表正确地连接到了交换后的两个节点之后。
🍌六. 50.Pow(x,n)
题目链接:50.Pow(x,n)
代码
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;//相当于x的0次方幂}double tmp=pow(x,n/2);//若为奇数,还需要在 * 上一个xreturn n%2==0?tmp*tmp:tmp*tmp*x;}
算法原理

当拿到这道题,大多数人首先会想到循环,但问题是常规的这种循环会超时,因此我们应该将问题用递归的方式去简化,拆分成相同的子问题
这个算法采用了分治的思想,通过递归地将问题规模减半来快速计算幂。
- 基本情况:当
n为0时,任何数的0次幂都是1。 - 递归步骤:
- 如果
n是偶数,那么x^n可以表示为(x^(n/2))^2。 - 如果
n是奇数,那么x^n可以表示为x * (x^(n-1))。
- 如果
通过递归地计算x^(n/2),我们可以将问题规模减半,从而大大减少了计算次数。这种方法的时间复杂度大约是O(log n),相比直接循环相乘的O(n)复杂度要高效得多。
相关文章:
【Java算法】递归
🔥个人主页: 中草药 🔥专栏:【算法工作坊】算法实战揭秘 🍇一.递归 概念 递归是一种解决问题的方法,其中函数通过调用自身来求解问题。这种方法的关键在于识别问题是否可以被分解为若干个相似但规模更小…...
NIDS——suricata(三)
一、监控ICMP流量 1、ICMP流量特征 四大特征分别为:消息类型(Type)、代码(Code)、校验和(Checksum)、数据字段(Data Field)。这里我们使用 type消息类型。 ICMP 消息的类…...
运动耳机哪个牌子最好用?年度精选五款好用的骨传导耳机推荐
相信大家都已经深有体会,拿那种常规的入耳式无线蓝牙耳机来做运动耳机,很难满足运动需要。如果选择前两年流行的颈挂式无线运动蓝牙耳机,虽然简单轻巧,但也是入耳式设计,长时间佩戴耳朵不舒服。这样看来,运…...
鞋服企业信息化建设若干架构分享
鞋服企业的信息化建设有着自身的一些特点,这些特点主要体现在以下几个方面: 集成化:鞋服企业的信息化建设往往需要集成多种系统,如企业资源规划系统(ERP)、客户关系管理系统(CRM)、供…...
比较顺序3s1和3s2的搜索难度
在行列可自由变换的平面上,3点结构只有6个 (A,B)---6*30*2---(0,1)(1,0) 分类A和B,让A是6个3点结构,让B全是0。当收敛误差为7e-4,收敛199次取迭代次数平均值, 让训练集A-B矩阵的高分别是3,4,5…...
Vue3 el-switch @change事件在初始化时会自动调用问题
接收一个vue3项目,突然有一天,table里有个switch开关,请求数据之后就开始执行switch的change事件,我还啥都没操作,就报一推重复请求 <template><el-switch v-model"rec" inline-prompt :active-val…...
全面解析性能测试中的瓶颈分析与优化策略!
在软件开发的生命周期中,性能测试是确保应用程序在不同负载下稳定运行的关键步骤。性能瓶颈是导致系统性能下降的主要原因,及时发现并解决这些瓶颈,能够显著提升系统的响应速度和用户体验。本文将深入探讨性能测试中的瓶颈分析方法与优化策略…...
2018年Android面试题含答案--适合中高级(下)
熟悉Android系统的童鞋都知道,系统出于体验和性能上的考虑,app在退到后台时系统并不会真正的kill掉这个进程,而是将其缓存起来。打开的应用越多,后台缓存的进程也越多。在系统内存不足的情况下,系统开始依据自身的一套…...
基于SSM的汽车租赁系统+LW示例参考
系列文章目录 1.基于SSM的洗衣房管理系统原生微信小程序LW参考示例 2.基于SpringBoot的宠物摄影网站管理系统LW参考示例 3.基于SpringBootVue的企业人事管理系统LW参考示例 4.基于SSM的高校实验室管理系统LW参考示例 5.基于SpringBoot的二手数码回收系统原生微信小程序LW参考示…...
[晕事]今天做了件晕事44 wireshark 首选项IPv4:Reassemble Fragented IPv4 datagrams
不知不觉,已经来到了晕事系列的第四十四个晕事。今天办的晕事和Wireshark查看网络包相关。说,在Wireshark的编辑-首选项协议里的IPv4协议,有一个参数设置是:Reassemble Fragented IPv4 datagrams。 这个参数的含义是指定Wireshar…...
Unity人工智能开发学习心得
在Unity中进行人工智能研究与应用主要集中在几个关键领域,包括使用Unity ML-Agents插件进行强化学习、利用神经网络技术和深度学习技术训练AI,以及基于行为树技术设计游戏人工智能。 使用Unity ML-Agents插件进行强化学习:Unity ML-Agent…...
0911,类与类之间的关系,设计原则,工厂模式
01_figure.cc //简单工厂 #include <math.h> #include <iostream> #include <string> #include <memory>using std::cout; using std::endl; using std::string; using std::unique_ptr;//-------------------------------------------------// /…...
【2024最新版】零基础Python快速入门篇
完整代码已打包,需要的小伙伴可以戳这里 [学习资料] 安装和运行 1.安装 要使用"Python"首先要把它安装到你电脑里。打开 [Python官网]下载安装包。 在Windows上安装 打开安装包,选择"Use admin privileges when installing py.exe&qu…...
掌握Go语言中的映射、常量与指针
映射(Maps) Go语言中的映射(map)等同于其他编程语言中的哈希表。映射的最大优势是可以使用任何可比较的数据类型作为键,也就是所谓的“map key”或“键”。尽管Go语言中的映射并没有限制哪些数据类型可以作为键&#…...
@35岁的网安人 答应我拿下这些证书
一、CISP注册信息安全专业人员 注册信息安全专业人员(Certified Information Security Professional,简称“CISP"),中国信息安全测评中心依据中编办赋予的职能,建立和发展的一整套完整的信息安全保障人才培训体系。CISP证书是国家对信息…...
flutter Image
Flutter中,Image是一个用于显示图片的控件,可以显示网络图片、本地图片以及Asset中的图片。Image控件支持多种常见的图片格式,例如PNG、JPEG、GIF等。 const Image({super.key,required this.image,this.frameBuilder,this.loadingBuilder,th…...
基于RP2350 MCU的树莓派Pico 2开发板及MicroPython编程使用
2021年1月21日,树莓派基金会同时发布了第1代RP2040 MCU芯片和基于RP2040 MCU的第1代树莓派Pico开发板(Raspberry Pi Pico/ Raspberry Pi Pico 1)。2024年8月8日,树莓派基金会又发布了第2代RP2350 MCU芯片并推出了基于RP2350 MCU的第2代树莓派Pico开发板(Raspberry Pi Pico 2)…...
Docker数据挂载本地目录
docker内的数据映射可以不通过数据卷,直接映射到本地的目录。下面将以mysql容器示例,完成容器的数据映射。 注意:每一个不同的镜像,将来创建容器后内部有哪些目录可以挂载,可以参考DockerHubDocker Hub Container Ima…...
身份证实名认证接口如何用C#实现
一、什么是身份证实名认证? 身份证实名认证又叫身份证实名核验、身份证二要素、身份实名核验、身份证验证,输入姓名、身份证号,校验此两项是否匹配,同时返回生日、性别、籍贯等信息,同时支持港澳台证件核验。 二、身…...
Java开发者无痛丝滑入门Python
哈喽各位道友,经过两周的更新,凡人编程传的第一个“系列”学习笔记《Python基础》已经全部上线啦,现在免费分享给大家,学习路线在下面,点击链接即可跳转对应笔记。 这套笔记有什么不一样的地方呢?这套笔记…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...


