【数据结构】递归算法与应用

简介: 【数据结构】递归算法与应用

一、递归概述

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

二、递归的调用机制

  1. 当程序执行到一个方法时,就会开辟一个独立的空间(栈)
  2. 每个空间的数据(局部变量)都是独立的

三、递归解决的问题

  1. 各种数学问题如:8 皇后问题,汉诺塔,阶乘问题,迷宫问题,球和篮子的问题(google 编程大赛)
  2. 各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等
  3. 将用栈解决的问题 --> 递归代码比较简洁

四、递归的原则

  1. 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
  2. 方法的局部变量是独立的,不会相互影响,比如n变量
  3. 如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据
  4. 递归必须向退出递归的条件逼近,否则就是无限递归,出现 StackOverflowError
  5. 当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完华。

五、迷宫问题

package work.rexhao.recursion;

import java.util.Scanner;

public class mazeDemo {
   

    static int size;
    static String[] map;
    static int ans = 0;
    static boolean[][] flag;

    public static void main(String[] args) {
   
        System.out.println("输入地图的大小:");
        Scanner sc = new Scanner(System.in);
        size = Integer.parseInt(sc.nextLine());
        System.out.println("输入地图:");
        map = new String[size];
        flag = new boolean[size][size];
        for (int i = 0; i < size; i++) {
   
            map[i] = sc.nextLine();
        }
        int x = 0, y = 0;
        for (int i = 0; i < size; i++) {
   
            for (int j = 0; j < size; j++) {
   
                if (map[i].charAt(j) == 'B') {
   
                    x = i;
                    y = j;
                }
            }
        }
        maze(x, y);
        System.out.println(ans);
        sc.close();
    }

    public static void maze(int x, int y) {
   
        if (check(x, y) && map[x].charAt(y) == 'E') {
   
            ans++;
            return;
        }
        flag[x][y] = true;
        if (check(x + 1, y)) {
   
            maze(x + 1, y);
        }
        if (check(x - 1, y)) {
   
            maze(x - 1, y);
        }
        if (check(x, y + 1)) {
   
            maze(x, y + 1);
        }
        if (check(x, y - 1)) {
   
            maze(x, y - 1);
        }
        flag[x][y] = false;
    }

    public static boolean check(int x, int y) {
   
        if (x >= size || y >= size || x < 0 || y < 0) {
   
            return false;
        } else
            return (map[x].charAt(y) == '.' || map[x].charAt(y) == 'E') && !flag[x][y];
    }
}

六、回溯算法(八皇后问题)

1、八皇后问题介绍

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

2、思路分析

  1. 相同剪枝:如果在同一行/列,舍弃
  2. 斜向剪枝:对于y=x方向,行+列为定值;对于y=-x方向,行-列为定值

3、代码实现

package work.rexhao.recursion;

public class queueEight {
   
    public static int[] chess = new int[8];
    public static int ans = 0;
    public static int[] x1; // 对角线1
    public static int[] x2; // 对角线2

    public static void main(String[] args) {
   
        queue(chess, 0);
        System.out.println(ans);
    }

    public static void queue(int[] chess, int times) {
   
        /*
         * 退出条件
         */
        if (times == 8) {
   
            /*
             * 重复
             */
            for (int i = 0; i < 8; i++) {
   
                for (int j = 0; j < 8; j++) {
   
                    if(i == j) continue;
                    if (chess[i] == chess[j]) {
   
                        return;
                    }
                }
            }
            /*
             * 对角线
             */
            x1 = new int[20];
            x2 = new int[20];
            for (int i = 0; i < 8; i++) {
   
                x1[chess[i] - i + 8]++;
                x2[i + chess[i]]++;
            }
            for (int i = 0; i < 20; i++) {
   
                if (x1[i] > 1 || x2[i] > 1) {
   
                    return;
                }
            }
            for(int i: chess) {
   
                System.out.print(i + " ");
            }
            System.out.println();
            ans++;
            return;
        }

        /*
         * 递归
         */
        for (int i = 1; i < 9; i++) {
   
            chess[times] = i;
            queue(chess, times + 1);
        }

    }
}
目录
相关文章
|
26天前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
158 86
|
2月前
|
存储 监控 JavaScript
基于布隆过滤器的 Node.js 算法在局域网电脑桌面监控设备快速校验中的应用研究
本文探讨了布隆过滤器在局域网电脑桌面监控中的应用,分析其高效空间利用率、快速查询性能及动态扩容优势,并设计了基于MAC地址的校验模型,提供Node.js实现代码,适用于设备准入控制与重复数据过滤场景。
77 0
|
8天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
65 3
|
19天前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
|
19天前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用
|
19天前
|
机器学习/深度学习 算法 安全
小场景大市场:猫狗识别算法在宠物智能设备中的应用
将猫狗识别算法应用于宠物智能设备,是AIoT领域的重要垂直场景。本文从核心技术、应用场景、挑战与趋势四个方面,全面解析这一融合算法、硬件与用户体验的系统工程。
|
3月前
|
机器学习/深度学习 人工智能 算法
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习模型、算法与应用的全方位解析
深度学习,作为人工智能(AI)的一个重要分支,已经在多个领域产生了革命性的影响。从图像识别到自然语言处理,从语音识别到自动驾驶,深度学习无处不在。本篇博客将深入探讨深度学习的模型、算法及其在各个领域的应用。
483 3
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
76 1
|
2月前
|
算法 数据可视化
matlab版本粒子群算法(PSO)在路径规划中的应用
matlab版本粒子群算法(PSO)在路径规划中的应用

热门文章

最新文章