java第十七课 —— 递归

2024-05-29 04:36
文章标签 java 递归 第十七

本文主要是介绍java第十七课 —— 递归,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

方法递归调用

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

递归重要规则

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

练习题

  1. 请使用递归的方式求出斐波那契 1,1,2,3,5,8,13… 给你一个整数n,求出它的值是多少。

    import java.util.Scanner;
    public class RecursionExercise{public static void main(String[] args){Scanner myScanner = new Scanner(System.in);System.out.println("请输入一个整数:");int n = myScanner.nextInt();if(n < 1){System.out.println("要求输入是大于1的整数!!!");}else{ReExercise obj = new ReExercise();System.out.println("斐波那契的结果为:" + obj.Fib(n));}}
    }
    class ReExercise{public int Fib(int n){if (n == 1 || n == 2){return 1;}else{return Fib(n - 1) + Fib(n - 2);}} 
    }
    
  2. 猴子吃桃子问题:有一堆桃子,猴子第一天吃了其中的一半,然后再多吃了一个!以后
    每天猴子都吃其中的一半,然后再多吃一个。当到第10天时,想再吃时(即还没吃)发现只有1个桃子了。问题:最初共多少个桃子?

    import java.util.Scanner;
    public class RecursionExercise{public static void main(String[] args){ReExercise obj = new ReExercise();System.out.println("吃到第10天时,最初共有:" + obj.Func(10) + "个桃子。");}
    }
    class ReExercise{public int Func(int day){if (day == 1){return 1;}else{return (Func(day - 1) + 1) * 2;}} 
    }
    // 1
    // (1+1)  *2 = 4
    // (4+1)  *2 = 10
    // (10+1) *2 = 22
    
  3. 迷宫问题: 小球在左上角出发,到右下角则走出迷宫,其中红色部分均是墙。
    在这里插入图片描述

    import java.util.Scanner;
    public class MiGong{public static void main(String[] args){ReExercise obj = new ReExercise();int[][] Map = new int[8][7];//打印墙for(int i = 0; i < 7; i++){Map[0][i] = 1;Map[7][i] = 1;}for(int i = 0; i < 8; i++){Map[i][0] = 1;Map[i][6] = 1;}Map[3][1] = 1;Map[3][2] = 1;//让老鼠找路obj.FindWay(Map, 1, 1);System.out.println("老鼠找的路径如下:");for(int i = 0; i < Map.length; i++){for(int j = 0; j < Map[i].length; j++){System.out.print(Map[i][j] + " ");}System.out.print("\n");}}
    }//FindWay是找出迷宫路径,找到返回true,否则false
    //i,j是老鼠的位置
    //找路策略:下右上左
    //Map[i][j] = 0表示未走过,1表示障碍物,2表示可以走的位置,3表示已经走过此路不通
    //当Map[6][5] = 2就说明找到通路啦。
    class ReExercise{public boolean FindWay(int Map[][], int i, int j){if(Map[6][5] == 2){return true;}else{if(Map[i][j] == 0){Map[i][j] = 2;if(FindWay(Map, i + 1, j)){return true;	}else if(FindWay(Map, i, j + 1)){return true;}else if(FindWay(Map, i - 1, j)){return true;}else if(FindWay(Map, i, j - 1)){return true;}else{Map[i][j] = 3;return false;}}else{//Map[i][j] = 1,2,3都是不能走的位置。return false;}}} 
    }
    
  4. 汉诺塔

    import java.util.Scanner;
    public class HanoiTower{public static void main(String[] args){Tower tower = new Tower();tower.move(5, 'A', 'B', 'C');}}
    class Tower{public void move(int num, char a, char b, char c){ //num 表示要移动的个数,a,b,c分别表示A塔,B塔,C塔if(num == 1){System.out.println(a + " --> " + c);}else{ //如果有多个盘,可以看成两个 ,最下面的和上面的所有盘(num-1)//(1)先移动上面所有的盘到 b,借助cmove(num - 1, a, c, b); //先移动上面所有的盘到 b,借助cSystem.out.println(a + " --> " + c); //把最下面的这个盘,移动到cmove(num - 1, b, a, c); //再把 b塔的所有盘,移动到c,借助a}}
    }
    
  5. 八皇后

    public class EightQueens {//定义max表示有多少个皇后int max = 8;int num = 0;//解法个数//定义数组array,保存皇后放置位置的结果,比如 arr = {0,4,7,5,2,6,1,3}int [] array = new int[max];public static void main(String[] args) {//测试8皇后EightQueens queen8 = new EightQueens();queen8.check(0);//从第一个皇后开始放System.out.println("一共有"+queen8.num+"解法");}/*** 编写一个方法,放置第n个皇后*  check的每一次递归时都有一个for循环,因此会有回溯* @param n*/private void check(int n){if (n == max){//n=8 相当于该放第九个皇后了(其实一共就八个皇后),有结果了,输出print();return;}//依次放入皇后,并判断是否冲突for (int i=0;i<max;i++){//先把当前皇后n,放到该行的第一列array[n]=i;//判断当放置第n个皇后到i列时是否冲突if (judge(n)){//不冲突,接着放N+1,即开始递归check(n+1);}//如果冲突就继续执行array[n]=i,在此之前i已经++了;//即将第n个皇后在本行后移一位}}/***当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突* @param n 表示第n个皇后* @return*/private boolean judge(int n){for (int i = 0; i < n; i++) {//判断第n个皇后是否和前面n-1个皇后在同一列 || 是否同一斜线if (array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){return false;}}return true;}//写一个方法,可以将皇后摆放的位置输出private void print (){num++;for (int i = 0; i < array.length; i++) {System.out.print(array[i]+ " ");}System.out.println();}
    }

    八皇后参考文章

这篇关于java第十七课 —— 递归的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012658

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

在cscode中通过maven创建java项目

在cscode中创建java项目 可以通过博客完成maven的导入 建立maven项目 使用快捷键 Ctrl + Shift + P 建立一个 Maven 项目 1 Ctrl + Shift + P 打开输入框2 输入 "> java create"3 选择 maven4 选择 No Archetype5 输入 域名6 输入项目名称7 建立一个文件目录存放项目,文件名一般为项目名8 确定