关键词:
🍅 作者主页:Roninaxious
🍅 欢迎点赞 👍 收藏 ⭐留言 📝
🚢前言
🎐何为递归
递归顾名思义就是´递´和´归´
👀所谓的‘递’也就是“向下递去”,这个问题可以分解为若干个且形式相同的子问题,这些子问题可以使用相同的思路来解决。
👀所谓的‘归’也就是“归来的意思”,什么时候归来?所以涉及到了临界点,也就是‘递’中的分解终止条件。
🎐递归的工作原理
💦根据递归两字的含义,不难发现,它包含了递去和归来两个层面。
💦根据以上分析可以发现这个流程和栈的工作原理一致,递归调用就是通过栈这种数据结构完成的。整个过程实际上就是一个栈的入栈和出栈问题。然而我们并不需要关心这个栈的实现,这个过程是由系统来完成的。
🎐递归 == 数学归纳法 ?
众所周知,计算机是数学的一个分支。这是一个不可否认的问题,在编程过程中,我们总能在数学中找到答案。递归提高了代码的可读性,但同时加大了内存的消耗,递归让人又爱又恨;不可否认,递归很重要!那么它和数学归纳法有什么联系呢?
💦归纳法
对于一个命题S(n),n为大于0的自然数;如何证明命题成立呢?
👀1.当n=1时,命题成立
👀2.当n=k时,命题成立
👀3.证明n=k+1时命题也成立
🧧递归本质上是类似归纳法,但又有点稍微不同🧧
递归是从F(n)倒推到F(1),然后在F(1)回溯到F(n);相比于归纳法多了一步。 |
💟 对于递归你了解多少了呢?💟
🚢如何正确使用递归
使用递归需要注意很多点,否者造成无限递归⛓就是在造孽了
🎐递归常用流程
* void func(mode)
*
* if(endCondition) //临界条件
*
* constExpression //处理方法
*
* else
*
* accumrateExpreesion //归纳项
* mode=expression //步进表达式
* func(mode) //调用本身,递归
*
*
🙄注意一定不要在自己脑子里递来递去的,你的脑子能压几个栈呢,否者很容易就陷入死脑筋之中🙄
🎐递归的三大要素
💥1、缩小问题规模
👀这个缩小问题规模可以根据归纳法先进行回推,比如让求S(n),我们可以先求当n=1的解决方法,再求n=2时的解决方法…一直归纳到S(n);这样我们就可以推导出关系式S(n)=S(n-1)+?
稍后会根据经典问题思考如何缩小问题规模。 |
💥2、明确递归终止条件
👀递归既然有去有回,就必须有一个临界条件,当程序到达这个临界值就必须进行归来;否者就肯定会造成无线递归下去,什么栈也扛不住!
💥3、给出递归终止时的处理办法
👀根据上文中阐述的递归的工作原理,递归是通过栈来实现的;当程序到达临界条件时,后续必须进行出栈。了解函数的压栈和出栈过程,函数出栈也就是返回到上一个函数的调用处继续执行。例如求解F(n),递推式是F(n)=F(n-1)+F(n-2),终止条件F(1)=1,F(0)=0;它的流程是每次进行压栈F(n-1)、F(n-2),当达到终止条件时进行函数的出栈,那么返回什么值呢?根据递归的倒数第一步F(2)=F(1)+F(0)所以返回的是F(1)+F(0),也就是1.
🚢经典问题一之迷宫求解
❓问题描述❓
- 找到迷宫路出口
🎐迷宫求解流程分析
右下角为迷宫的出口,方块为墙,圆形块为迷宫入口;如何找到一条通路从入口到出口?
🎈为了表示方便,我以二位数组为例进行操作。拟定二位数组中的1代表墙,2代表通路,3代表路已经走过且不通,0代表未走过的路。
❤️ 初始化迷宫
📑首先迷宫有四个方向可以走(上下左右),所以我们应该先自定义一个策略,规定✨下右上左✨(优先走下,然后右->上->左),也就是当下不通时,走右…
🎆根据递归三要素
1.分解成子问题 |
2.递归终止条件 |
这个当然就是出口了,也就是map[5][6] == 2;
🎐源代码
public class Labyrinth
private static final int X_MAX = 7;
private static final int Y_MAX = 8;
private static int[][] map = new int[X_MAX][Y_MAX];
/**
* 迷宫问题--递归
* 思路:
* 策略:规定下右上左为行走策略
* 1代表障碍物,2代表走过的路,3代表路已经走过且不通,0代表未走过的路
*/
public static boolean setWays(int[][] arr, int x, int y)
if (arr[5][6] == 2) //终止条件
return true;
else
if (arr[x][y] == 0)
arr[x][y] = 2;
if (setWays(arr, x, y + 1)) //下
return true;
else if (setWays(arr, x + 1, y)) //右
return true;
else if (setWays(arr, x, y - 1)) //上
return true;
else if (setWays(arr, x - 1, y - 1)) //左
return true;
else //如果下右上左都不能走,所以此路不同,置为3
arr[x][y] = 3;
return false;
else //arr[x][y] != 0 ? 有可能是1,2,3
return false;
//测试
public static void main(String[] args)
for (int i = 0; i < X_MAX; i++)
map[i][0] = 1;
map[i][Y_MAX - 1] = 1;
for (int j = 1; j < Y_MAX - 1; j++)
map[0][j] = 1;
map[X_MAX - 1][j] = 1;
map[1][2] = 1;
map[1][3] = 1;
map[2][3] = 1;
map[3][3] = 1;
map[3][2] = 1;
setWays(map, 1, 1);
printMap(map);
//打印迷宫地图
public static void printMap(int[][] arr)
for (int j = 0; j < Y_MAX; j++)
for (int i = 0; i < X_MAX; i++)
System.out.print(arr[i][j] + " ");
System.out.println();
❤️ 运行结果
🚢经典问题二之链表反转一(全反转)
🔰问题描述🔰
- 给定一个链表,将其反转
- 例如:1->2->3->4 ---- 4->3->2->1
🎐链表反转流程分析
📑对于该问题,将其整体分为两部分1和n-1,将其反转即可;然后再将n-1部分整体分为两部分,再将其反转即可。
🎆根据递归三要素
1.分解成子问题 |
2.递归终止条件 |
对于这个终止条件,这个应该比较简单,当递归到最后一个节点时开始进行归来操纵,也就是head.next == null || head == null;对于这个head == null是因为空链表的情况。
3.递归终止处理办法 |
由于我们最后反转链表之后,要将最后一个节点定义为头节点。所以需要将该节点返回。
if (head == null || head.next == null)
return head;
🎐源代码
package com.zsh.algorithm.recursion;
/**
* @author:Ronin
* @since:2021/9/16
* @email:1817937322@qq.com
*/
/**
* 反转单链表 question one
* eg:1->2->3->4 ---- 4->3->2->1
*/
public class ReverseLinkedList
/**
* 链表反转
* 思路:将链表分成两部分(1.第一个头节点 2.头节点之后的所有)
* 递归回溯时将指针反转即可
* 递归出口条件:head || head.next == null
* @param head
* @return
*/
static Node reverse(Node head)
if (head == null || head.next == null)
return head;
Node currentNode = reverse(head.next);
head.next.next = head;
head.next = null;
return currentNode;
// public static void main(String[] args)
// Node node = new Node(1);
// Node node2 = new Node(2);
// Node node3 = new Node(3);
// LinkedListNode linkedListNode = new LinkedListNode();
// linkedListNode.add(node);
// linkedListNode.add(node2);
// linkedListNode.add(node3);
// Node reverseHead = reverse(linkedListNode.head);
// linkedListNode.print(reverseHead);
//
//class Node
// int num;
// Node next;
// public Node()
// public Node(int i)
// this.num = i;
//
//
//class LinkedListNode
// Node head = null;
//
// public void add(Node addNode)
// if (head == null)
// head = addNode;
// return;
//
// Node temp = head;
// while (temp.next != null)
// temp = temp.next;
//
// temp.next = addNode;
// temp = addNode;
// temp.next = null;
//
//
// public void print(Node reverseHead)
// Node temp = reverseHead;
// while (temp != null)
// System.out.print(temp.num);
// System.out.print("->");
// temp = temp.next;
//
//
//
🚢经典问题二之链表反转二(反转前n个节点)
🔰问题描述🔰
- 反转单链表2
- 反转前n个节点 1->2->3->4->5->6
- reverse(node head, 3)
- 3->2->1->4->5->6
🎐链表反转2流程分析
如果已经了解了全部节点的链表反转,那么这个应该也比较简单;反转前n个节点,当然就是临界条件改变了。全部节点的反转是在最后一个节点作为临界值,而这个只需要加入一个新的变量n进行控制前n个节点反转即可。
下图是出栈得流程
🎐源代码
public class ReverseLinkedListFront
static Node cur = null;
static Node reverse(Node head, int n)
if (n <= 1 || head.next == null)
cur = head.next;
return head;
Node lastNode = reverse(head.next, n-1);
head.next.next = head;
head.next = cur;
return lastNode;
// public static void main(String[] args)
// Node node = new Node(1);
// Node node2 = new Node(2);
// Node node3 = new Node(3);
// LinkedListNode linkedListNode = new LinkedListNode();
// linkedListNode.add(node);
// linkedListNode.add(node2);
// linkedListNode.add(node3);
// Node reverseHead = reverse(linkedListNode.head, 3);
// linkedListNode.print(reverseHead);
//
🚢经典问题二之链表反转三(反转中间部分)
飞速总结中…
❤️爆肝万字!一文最全总结之spring从入门到入土❤️(建议收藏)(代码片段)
文章目录最新更新前言1.Spring概述1.1介绍2.IoC入门2.1什么是IoC2.2IoC入门案例1(基础案例)2.3IoC入门案例2(依赖注入)2.4IoC入门案例3(面向接口编程)2.5IoC入门案例4(整合JUnit4)3.IoC详解3.1Bean的创建... 查看详情
❤️爆肝万字!一文最全总结之spring从入门到入土❤️(建议收藏)(代码片段)
文章目录前言1.Spring概述1.1介绍2.IoC入门2.1什么是IoC2.2IoC入门案例1(基础案例)2.3IoC入门案例2(依赖注入)2.4IoC入门案例3(面向接口编程)2.5IoC入门案例4(整合JUnit4)3.IoC详解3.1Bean的创建3.2依赖注... 查看详情
pythonopencv实战画图——这次一定能行!爆肝万字,建议点赞收藏~❤️❤️❤️(代码片段)
📢📢📢📣📣📣🌻🌻🌻Hello,大家好我叫是Dream呀,一个有趣的Python博主,小白一枚,多多关照😜😜😜🏅🏅 查看详情
❤️爆肝万字整理的综合架构web服务之nginx详解❤️,附建议收藏(代码片段)
文章目录nginx服务配置详细介绍关于作者前言一、nginxweb入门简介1.1什么是nginx1.2常见的网站服务1.3nginx网站服务特点1.4网站页面访问原理二、nginx服务部署安装2.1实验环境2.2YUM安装2.3源码编译安装2.4nginx重要文件目录结构2.5虚拟主... 查看详情
❤️大学三年沉淀,把我的学习经验分享给你,爆肝万字带你走进编程世界!❤️(代码片段)
Hello,大家好,我是Alex。时光匆匆,暑假过的很快,转眼又到了大学的开学季,我也是又混进了我们学院的新生群,发现大家对计算机充满着迷之向往,啊哈哈哈,不过没有人带着入门还是很容易... 查看详情
❤️爆肝四万字的mysql总结全面整理+详细解释❤️(代码片段)
文章目录1.初识MySQL1.2数据库分类1.3MySQL简介1.4MySQL安装1.5MySQL(压缩包)安装配置1.6SQLyog使用的注意事项1.7连接数据库和一些基本命令2.操作数据库2.1操作数据库2.2数据库的数据类型(列类型)2.3数据库的字段属性2.4创建数据库表(... 查看详情
(大厂必备)厂长熬夜爆肝万字之多线程高并发juc编程⭐学妹已收藏(代码片段)
🔥(大厂必备)厂长熬夜爆肝万字之多线程高并发JUC编程(一)⭐学妹已收藏❤️大家好,我是java厂长,今天带你们体验一把多线程高并发的面试高频!❤️关于作者作者介绍🍓博客主页:作者主页🍓... 查看详情
(大厂必备)厂长熬夜爆肝万字之多线程高并发juc编程⭐学妹已收藏(代码片段)
🔥(大厂必备)厂长熬夜爆肝万字之多线程高并发JUC编程(二)⭐学妹已收藏❤️大家好,我是java厂长,今天再次带你们体验一把多线程高并发的面试高频!❤️关于作者作者介绍🍓博客主页:作者主页... 查看详情
爆肝一周面试10多家中大厂后的万字总结——❤️javaweb篇❤️(建议收藏)(代码片段)
⭐欢迎订阅《大厂面试突击》专栏,面试10多家大厂总结出的高频面试知识,免费阶段大家赶快订阅⭐更多精品专栏简介点这里⭐更多大厂全路线学习视频+笔记,PC端看左侧「关于作者」,手机端「私信」博主... 查看详情
熬夜爆肝万字c#基础入门大总结建议收藏(代码片段)
往期文章分享点击跳转=>熬夜再战Android从青铜到王者-UI组件快速搭建App界面点击跳转=>熬夜再战Android从青铜到王者-几个适配方案点击跳转=>熬夜再战Android从青铜到王者-开发效率插件篇点击跳转=>Unity粒子特... 查看详情
❤️爆肝六万字最全总结java数据库编程mybatis(建议收藏)(代码片段)
前言今天复习Java数据库编程,二话不说MyBatis手把手保姆级教程献上,再也不用担心学不会!资料:链接:https://pan.baidu.com/s/1FIDi_9QiTuhb4x7pksGOUQ提取码:kevf1.MyBatis入门文章目录前言1.MyBatis入门1.1概述1.2下载1.3与JDBC对比1.4入门案... 查看详情
❤️爆肝六万字最全总结java数据库编程mybatis(建议收藏)(代码片段)
前言今天复习Java数据库编程,二话不说MyBatis手把手保姆级教程献上,再也不用担心学不会!资料:链接:https://pan.baidu.com/s/1FIDi_9QiTuhb4x7pksGOUQ提取码:kevf1.MyBatis入门文章目录前言1.MyBatis入门1.1概述1.2下载1.3与JDBC对比1.4入门案... 查看详情
❤️3万字《算法+数据结构》刷了3333道算法题后的一点总结❤️(建议收藏)
文章目录1️⃣前言:追忆我的刷题经历2️⃣算法和数据结构的重要性👪1、适用人群🎾2、有何作用📜3、算法简介🌲4、数据结构3️⃣如何开始持续的刷题📑1、立军令状👩❤️👩2、培养兴... 查看详情
❤️3万字《算法+数据结构》刷了3333道算法题后的一点总结❤️(建议收藏)
文章目录1️⃣前言:追忆我的刷题经历2️⃣算法和数据结构的重要性👪1、适用人群🎾2、有何作用📜3、算法简介🌲4、数据结构3️⃣如何开始持续的刷题📑1、立军令状👩❤️👩2、培养兴... 查看详情
❤️❤️爆肝3万字整理小白入门与提升分布式版本管理软件:git,图文并茂(建议收藏)--已码一万字❤️❤️(代码片段)
小白快速快入门Git什么是GitSVNVSGit什么是版本控制安装Git谁在操作?Git本地仓库本地仓库构造重点Git常用基本操作gitaddgitcommitgitdiffgitloggitresetgitmvcheckoutgittagclearGithub使用教程什么是Github安装Github添加远程仓库找到key打开Github... 查看详情
❤️❤️新生代农民工爆肝8万字,整理python编程从入门到实践(建议收藏)已码:8万字❤️❤️(代码片段)
人生苦短,我用Python开发环境搭建安装Python验证是否安装成功安装Pycharm配置pycharm编码规范基本语法规则保留字单行注释多行注释行与缩进多行语句数据类型空行等待用户输入print输出运算符算术运算符逻辑运算符成员运算符... 查看详情
❤️爆肝十二万字《python从零到精通教程》,从零教你变大佬❤️(建议收藏)(代码片段)
文章目录强烈推荐系列教程,建议学起来!!一.pycharm下载安装二.python下载安装三.pycharm上配置python四.配置镜像源让你下载嗖嗖的快4.1pycharm内部配置4.2手动添加镜像源4.3永久配置镜像源五.插件安装(比如汉化ÿ... 查看详情
❤️爆肝3万字,最硬核丨mysql知识体系命令全集建议收藏❤️(代码片段)
🍅作者主页:不吃西红柿 🍅简介:CSDN博客专家🏆、信息技术智库公号作者✌ 简历模板、PPT模板、学习资料、面试题库、技术互助【关注我,都给你】🍅 欢迎点赞👍收藏⭐留言 📝 ... 查看详情