1. 재귀란 무엇인가요?
간단히 말하면 재귀는 메소드가 호출될 때마다 다른 변수를 전달하는 것입니다. 재귀는 프로그래머가 복잡한 문제를 해결하고 코드를 간결하게 만드는 데 도움이 됩니다.
실제 응용 시나리오, 미로 문제(역추적), 재귀(재귀)를 살펴보세요
재귀를 이해하는 데 도움이 되는 두 가지 작은 사례를 나열하겠습니다. 여기서는 재귀 호출 메커니즘을 검토하겠습니다.
인쇄 문제
팩토리얼 문제
public static void test(int n) { if (n > 2) { test(n - 1); } System.out.println("n=" + n); } public static int factorial(int n) { if (n == 1) { return 1; } else { return factorial(n - 1) * n; } }
재귀를 사용하여 해결하는 문제는 무엇인가요?
여러 여왕 문제, 하노이 탑, 계승 문제, 미로 문제, 공의 합 바구니 문제(구글 프로그래밍 대회).
재귀는 퀵 정렬, 병합 정렬, 이진 검색, 분할 정복 알고리즘 등 다양한 알고리즘에도 사용됩니다.
스택으로 해결될 문제-->코드가 비교적 간결합니다.
재귀를 위해 따라야 할 중요한 규칙
메서드가 실행되면 보호되는 새로운 독립 공간(스택 공간)이 생성됩니다.
메서드의 지역 변수는 독립적이며 n 변수와 같이 서로 영향을 주지 않습니다.
메소드에 참조 유형 변수(예: 배열)가 사용되는 경우 참조 유형의 데이터가 공유됩니다.
재귀는 재귀를 종료하기 위한 조건에 접근해야 합니다. 그렇지 않으면 무한 재귀가 되고 StackOverflowError가 나타나며 죽게 됩니다 :).
메서드가 실행을 완료하거나 반환을 만나면 반환됩니다. 이를 호출하는 사람은 누구든지 호출하는 사람에게 결과를 반환합니다. 동시에 메서드가 실행을 완료하거나 반환하면 메서드도 실행을 완료합니다.
2. 코드 사례 1 - 미로 문제
설명: 공이 가는 경로는 프로그래머가 설정한 경로 찾기 전략, 즉 위쪽, 아래쪽, 왼쪽의 경로 찾기 순서와 관련됩니다. , 오른쪽은 공과 관련된 경로를 선택할 때 먼저 (오른쪽 아래, 왼쪽 위)를 사용한 다음 (오른쪽 위, 왼쪽 아래)로 변경하여 경로가 변경되는지 확인할 수 있습니다. 역추적 현상을 테스트합니다.
package com.szh.recursion; /** * 走迷宫问题 */ public class MiGong { //使用递归回溯来给小球找路, 说明: //1. map 表示地图 //2. i,j 表示从地图的哪个位置开始出发 (1,1) //3. 如果小球能到 map[6][5] 位置,则说明通路找到. //4. 约定:当 map[i][j] 为 0 表示该点没有走过; 当为 1 表示墙; 2 表示通路可以走; //5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯 public static boolean setWay(int[][] map, int i, int j) { //此时走到了迷宫终点 if (map[6][5] == 2) { 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 { //左 return true; } } else { //map[i][j] != 0, 即只能为1、2。 1表示墙(无法走),2表示已经走过了,所以此时直接返回false 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 { //左 return true; } } else { return false; } } } 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; } //多添加两块墙体 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(); } } }
3. 코드 사례 2 - 여덟 여왕 문제
여덟 여왕 문제는 오래되고 유명한 문제이자 역추적 알고리즘의 전형적인 사례입니다. 이 문제는 1848년에 국제적인 체스 선수인 Max Bethel에 의해 제기되었습니다. 8×8 체스 격자에 8명의 여왕을 배치하여 서로 공격할 수 없도록 하십시오. 즉, 두 명의 여왕이 같은 위치에 있을 수 없습니다. 행, 열 또는 대각선으로?
첫 번째 퀸은 첫 번째 행과 첫 번째 열에 먼저 배치됩니다.
두 번째 퀸을 두 번째 행과 첫 번째 열에 배치한 다음 괜찮은지 확인하고 그렇지 않은 경우 계속해서 두 번째 열과 세 번째 열에 배치한 다음 모든 열을 배치하여 적합한 것을 찾습니다. .
계속해서 세 번째 퀸, 즉 첫 번째와 두 번째 열... 여덟 번째 퀸이 충돌하지 않는 위치에 배치될 수 있을 때까지는 올바른 해결책이라고 볼 수 있습니다.
올바른 솔루션을 얻었을 때 스택이 이전 스택으로 롤백되면 역추적을 시작합니다. 즉, 첫 번째 퀸을 첫 번째 열에 놓고 모든 올바른 솔루션을 얻습니다.
그런 다음 돌아가서 첫 번째 여왕을 두 번째 열에 계속 배치하고 1, 2, 3, 4단계를 반복해서 수행합니다.
package com.szh.recursion; /** * 八皇后问题 */ public class Queue8 { //定义max表示共有多少个皇后 private int max = 8; //定义数组,保存皇后放置的位置结果,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3} int[] array = new int[max]; //共有多少种解法 private static int count = 0; //共有多少次冲突 private static int judgeCount = 0; //编写一个方法,放置第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个皇后,放置在本行第i列向后的那一列 } } //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的n-1个皇后冲突 private boolean judge(int n) { //每摆放一个皇后,就循环去和之前摆好的皇后位置相比较,看是否冲突 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皇后是否在同一斜线 //3. 判断是否在同一行, 没有必要,n 表示第几个皇后,这个值每次都在递增,所以必然不在同一行 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { judgeCount++; return false; } } return true; } //打印皇后摆放的具体位置 private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("一共有%d解法\n", count); System.out.printf("一共判断冲突的次数%d次", judgeCount); } }
사실 코드를 디버깅하면 역추적 과정을 볼 수 있으니 더 말하지 않겠습니다.
위 내용은 Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

이 기사에서는 Java 프로젝트 관리, 구축 자동화 및 종속성 해상도에 Maven 및 Gradle을 사용하여 접근 방식과 최적화 전략을 비교합니다.

이 기사에서는 Maven 및 Gradle과 같은 도구를 사용하여 적절한 버전 및 종속성 관리로 사용자 정의 Java 라이브러리 (JAR Files)를 작성하고 사용하는 것에 대해 설명합니다.

이 기사는 카페인 및 구아바 캐시를 사용하여 자바에서 다단계 캐싱을 구현하여 응용 프로그램 성능을 향상시키는 것에 대해 설명합니다. 구성 및 퇴거 정책 관리 Best Pra와 함께 설정, 통합 및 성능 이점을 다룹니다.

이 기사는 캐싱 및 게으른 하중과 같은 고급 기능을 사용하여 객체 관계 매핑에 JPA를 사용하는 것에 대해 설명합니다. 잠재적 인 함정을 강조하면서 성능을 최적화하기위한 설정, 엔티티 매핑 및 모범 사례를 다룹니다. [159 문자]

Java의 클래스 로딩에는 부트 스트랩, 확장 및 응용 프로그램 클래스 로더가있는 계층 적 시스템을 사용하여 클래스로드, 링크 및 초기화 클래스가 포함됩니다. 학부모 위임 모델은 핵심 클래스가 먼저로드되어 사용자 정의 클래스 LOA에 영향을 미치도록합니다.


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

Atom Editor Mac 버전 다운로드
가장 인기 있는 오픈 소스 편집기

ZendStudio 13.5.1 맥
강력한 PHP 통합 개발 환경

안전한 시험 브라우저
안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

에디트플러스 중국어 크랙 버전
작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

드림위버 CS6
시각적 웹 개발 도구
