尚硅谷Java数据结构与java算法——递归

在这里插入图片描述

递归

6.2递归的概念

简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

2 递归调用机制

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

package DataStructures.a05_Recursion;

/**
 * 认识递归
 */
public class RecursionTest {
    public static void main(String[] args) {
        test(4);
        System.out.println("-------------------------------");
        test1(4);
        System.out.println("-------------------------------");
        System.out.println(factorial(3));
    }
    //打印问题.
    public static void  test(int n ){
        if (n>2){
            test(n-1);
        }else {
            System.out.println("n="+n);
        }
    }
    public static void  test1(int n ){
        if (n>2){
            test1(n-1);
        }
        System.out.println("n="+n);
    }

    //阶乘问题
    public  static int factorial(int n){
        if (n==1){
            return 1;
        }else {
            return factorial(n-1)*n; // 1 * 2 * 3
        }
    }

}

迷宮

在这里插入图片描述

1、

在这里插入图片描述

2、

package DataStructures.a05_Recursion;

/**
 * 迷宫问题
 */
public class a02_MiGong {
    public static void main(String[] args) {
        // 先创建一个二维数组,模拟迷宫
        // 地图
        int[][] map = new int[8][7];
        // 使用1 表示墙
        // 上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        // 左右全部置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板, 1 表示
        map[3][1] = 1;
        map[3][2] = 1;
//		map[1][2] = 1;
//		map[2][2] = 1;
        // 输出地图
        System.out.println("地图的情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        //使用递归回溯给小球找路
        setWay(map, 1, 1);
        setWay2(map, 1, 1);

        //输出新的地图, 小球走过,并标识过的递归
        System.out.println("小球走过,并标识过的 地图的情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    //使用递归回溯来给小球找路
    //说明
    //1. map 表示地图
    //2. i,j 表示从地图的哪个位置开始出发 (1,1)
    //3. 如果小球能到 map[6][5] 位置,则说明通路找到.
    //4. 约定: 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙  ; 2 表示通路可以走 ; 3 表示该点已经走过,但是走不通
    //5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯
    /**
     *
     * @param map 表示地图
     * @param i 从哪个位置开始找
     * @param j
     * @return 如果找到通路,就返回true, 否则返回false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] ==2 ){// 通路已经找到ok
            return true;
        }else {
            if (map[i][j] == 0){//如果当前这个点还没有走过
                //按照策略 下->右->上->左  走
                map[i][j]=2;// 假定该点是可以走通.
                if(setWay(map, i+1, j)) {//向下走
                    return true;
                } else if (setWay(map, i, j+1)) { //向右走
                    return true;
                } else if (setWay(map, i-1, j)) { //向上
                    return true;
                } else if (setWay(map, i, j-1)){ // 向左走
                    return true;
                } else {
                    //说明该点是走不通,是死路
                    map[i][j] = 3;
                    return false;
                }
            }else {// 如果map[i][j] != 0 , 可能是 1, 2, 3
                return false;
            }
        }
    }
    //修改找路的策略,改成 上->右->下->左
    public static boolean setWay2(int[][] map, int i, int j) {
        if(map[6][5] == 2) { // 通路已经找到ok
            return true;
        } else {
            if(map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 上->右->下->左
                map[i][j] = 2; // 假定该点是可以走通.
                if(setWay2(map, i-1, j)) {//向上走
                    return true;
                } else if (setWay2(map, i, j+1)) { //向右走
                    return true;
                } else if (setWay2(map, i+1, j)) { //向下
                    return true;
                } else if (setWay2(map, i, j-1)){ // 向左走
                    return true;
                } else {
                    //说明该点是走不通,是死路
                    map[i][j] = 3;
                    return false;
                }
            } else { // 如果map[i][j] != 0 , 可能是 1, 2, 3
                return false;
            }
        }
    }
}


3、对迷宫问题的讨论

1)小球得到的路径,和程序员设置的找路策略有关即:找路的上下左右的顺序相关
2)再得到小球路径时,可以先使用(下右上左),再改成(上右下左),看看路径是不是有变化
3)测试回溯现象
4)思考: 如何求出最短路径? 思路-》代码实现.

八皇后

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出:在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法
在这里插入图片描述

package DataStructures.a05_Recursion;
/**
 * 八皇后问题
 */
public class a03_Queue8 {
    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} 
    int[] array = new int[max];
    static int count = 0;
    static int judgeCount = 0;
    
    public static void main(String[] args) {
        //测试一把 , 8皇后是否正确
        a03_Queue8 queue8 = new a03_Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法", count);
        System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w

    }

    //编写一个方法,放置第n个皇后
    //特别注意: check 是 每一次递归时,进入到check中都有  for(int i = 0; i < max; i++),因此会有回溯
    private void check(int n) {
        if(n == max) {  //n = 8 , 其实8个皇后就既然放好
            print();
            return;
        }

        //依次放入皇后,并判断是否冲突
        for(int i = 0; i < max; i++) {
            //先把当前这个皇后 n , 放到该行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时,是否冲突
            if(judge(n)) { // 不冲突
                //接着放n+1个皇后,即开始递归
                check(n+1); //  
            }
            //如果冲突,就继续执行 array[n] = i; 即将第n个皇后,放置在本行得 后移的一个位置
        }
    }

    //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
    /**
     *
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        judgeCount++;
        for(int i = 0; i < n; i++) {
            // 说明
            //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
            // n = 1  放置第 2列 1 n = 1 array[1] = 1
            // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
            //3. 判断是否在同一行, 没有必要,n 每次都在递增
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
                return false;
            }
        }
        return true;
    }

    //写一个方法,可以将皇后摆放的位置输出
    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

热门文章

暂无图片
编程学习 ·

exe4j详细使用教程(附下载安装链接)

一、exe4j介绍 ​ exe4j是一个帮助你集成Java应用程序到Windows操作环境的java可执行文件生成工具&#xff0c;无论这些应用是用于服务器&#xff0c;还是图形用户界面&#xff08;GUI&#xff09;或命令行的应用程序。如果你想在任务管理器中及Windows XP分组的用户友好任务栏…
暂无图片
编程学习 ·

AUTOSAR从入门到精通100讲(126)-浅谈车载充电系统通信方案

01 引言 本文深入研究车载充电系统策略,设计出一套基于电动汽车电池管理系统与车载充电机的CAN通信协议,可供电动汽车设计人员参考借鉴。 02 电动汽车充电系统通讯网络 电动汽车整车控制系统中采用的是CAN总线通信方式,由一个整车内部高速CAN网络、内部低速CAN网络和一个充电…
暂无图片
编程学习 ·

CMake(九):生成器表达式

当运行CMake时&#xff0c;开发人员倾向于认为它是一个简单的步骤&#xff0c;需要读取项目的CMakeLists.txt文件&#xff0c;并生成相关的特定于生成器的项目文件集(例如Visual Studio解决方案和项目文件&#xff0c;Xcode项目&#xff0c;Unix Makefiles或Ninja输入文件)。然…
暂无图片
编程学习 ·

47.第十章 网络协议和管理配置 -- 网络配置(八)

4.3.3 route 命令 路由表管理命令 路由表主要构成: Destination: 目标网络ID,表示可以到达的目标网络ID,0.0.0.0/0 表示所有未知网络,又称为默认路由,优先级最低Genmask:目标网络对应的netmaskIface: 到达对应网络,应该从当前主机哪个网卡发送出来Gateway: 到达非直连的网络,…
暂无图片
编程学习 ·

元宇宙技术基础

请看图&#xff1a; 1、通过AR、VR等交互技术提升游戏的沉浸感 回顾游戏的发展历程&#xff0c;沉浸感的提升一直是技术突破的主要方向。从《愤怒的小鸟》到CSGO,游戏建模方式从2D到3D的提升使游戏中的物体呈现立体感。玩家在游戏中可以只有切换视角&#xff0c;进而提升沉浸…
暂无图片
编程学习 ·

flink的伪分布式搭建

一 flink的伪分布式搭建 1.1 执行架构图 1.Flink程序需要提交给 Job Client2.Job Client将作业提交给 Job Manager3.Job Manager负责协调资源分配和作业执行。 资源分配完成后&#xff0c;任务将提交给相应的 Task Manage。4.Task Manager启动一个线程以开始执行。Task Manage…
暂无图片
编程学习 ·

十进制正整数与二进制字符串的转换(C++)

Function one&#xff1a; //十进制数字转成二进制字符串 string Binary(int x) {string s "";while(x){if(x % 2 0) s 0 s;else s 1 s;x / 2;}return s; } Function two&#xff1a; //二进制字符串变为十进制数字 int Decimal(string s) {int num 0, …
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

树莓派驱动DHT11温湿度传感器

1&#xff0c;直接使用python库 代码如下 import RPi.GPIO as GPIO import dht11 import time import datetimeGPIO.setwarnings(True) GPIO.setmode(GPIO.BCM)instance dht11.DHT11(pin14)try:while True:result instance.read()if result.is_valid():print(ok)print(&quo…
暂无图片
编程学习 ·

ELK简介

ELK简介 ELK是三个开源软件的缩写&#xff0c;Elasticsearch、Logstash、Kibana。它们都是开源软件。不过现在还新增了一个 Beats&#xff0c;它是一个轻量级的日志收集处理工具(Agent)&#xff0c;Beats 占用资源少&#xff0c;适合于在各个服务器上搜集日志后传输给 Logstas…
暂无图片
编程学习 ·

Linux 基础

通常大数据框架都部署在 Linux 服务器上&#xff0c;所以需要具备一定的 Linux 知识。Linux 书籍当中比较著名的是 《鸟哥私房菜》系列&#xff0c;这个系列很全面也很经典。但如果你希望能够快速地入门&#xff0c;这里推荐《Linux 就该这么学》&#xff0c;其网站上有免费的电…
暂无图片
编程学习 ·

Windows2022 无线网卡装不上驱动

想来 Windows2022 和 windows10/11 的驱动应该差不多通用的&#xff0c;但是死活装不上呢&#xff1f; 搜一下&#xff0c;有人提到 “默认安装时‘无线LAN服务’是关闭的&#xff0c;如果需要开启&#xff0c;只需要在“添加角色和功能”中&#xff0c;选择开启“无线LAN服务…
暂无图片
编程学习 ·

【嵌入式面试宝典】版本控制工具Git常用命令总结

目录 创建仓库 查看信息 版本回退 版本检出 远程库 Git 创建仓库 git initgit add <file> 可反复多次使用&#xff0c;添加多个文件git commit -m <message> 查看信息 git status 仓库当前的状态git diff 差异对比git log 历史记录&#xff0c;提交日志--pret…
暂无图片
编程学习 ·

用Postman生成测试报告

newman newman是一款基于nodejs开发的可以运行postman脚本的工具&#xff0c;使用Newman&#xff0c;可以直接从命令运行和测试postman集合。 安装nodejs 下载地址&#xff1a;https://nodejs.org/en/download/ 选择自己系统相对应的版本内容进行下载&#xff0c;然后傻瓜式安…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…