Shulou(Shulou.com)06/03 Report--

This article mainly shows you "Java how to achieve recursive algorithm", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "Java how to achieve recursive algorithm" this article.

Introduction 1. Introduction

Recursion: recursion means that the method calls itself, passing in a different variable each time. Recursion helps programmers solve complex problems while making the code concise.

The difference between iteration and recursion: iteration uses a loop structure and recursion uses a selection structure. Using recursion can make the structure of the program clearer, more concise, and easier for people to understand, thus reducing the time it takes to read the code. Its time complexity is the number of recursions.

However, a large number of recursive calls make a copy of the function, which consumes a lot of time and memory, while iteration does not require this kind of effort.

The recursive function is divided into the calling phase and the fallback phase, and the recursive fallback order is the reverse order of its calling order.

Divide and conquer: when a problem is large and difficult to solve, you can consider dividing the problem into several small modules and solving them one by one.

2. Case

The problem of rabbit breeding. Fibonacci series.

Calculate n!.

A string of any length is output in reverse.

Recursive implementation of half-and-half search algorithm.

Tower of Hanoi problem

The problem of eight queens

Second, the labyrinth problem

Problem: find an effective path from the starting point to the end point.

Code example: maze

Public class MiGong {/ * 0: this point has not been passed. 1: indicates the wall, 2: can walk, 3: the point has passed, but cannot get through.\ * Strategy: bottom-> right-> top-> left. If the point fails, go back to * / private int [] [] map; private int desX; private int desY. / * build the maze of row*col * * @ param row row * @ param col column * / public MiGong (int row, int col) {if (row 0 & & j)

< map[0].length - 1) { map[i][j] = 1; } } /** * 设置迷宫的终点位置 * * @param desX 横坐标 * @param desY 纵坐标 */ public void setDes(int desX, int desY) { this.desX = desX; this.desY = desY; } public boolean setWay(int i, int j) { // 通路已经找到 if (map[desX][desY] == 2) { return true; } else { if (map[i][j] != 0) { return false; } // map[i][j] == 0 按照策略 下->

Right-> top-> left recursion / / assumes that the point is passable. Map [I] [j] = 2; if (setWay (I + 1, j)) {return true;} else if (setWay (I, j + 1)) {return true;} else if (setWay (I-1, j)) {return true } else if (setWay (I, j-1)) {return true;} else {/ / indicates that this point is impassable and that it is a dead end map [I] [j] = 3; return false } / / display map public void show () {for (int I = 0; I

< map.length; i++) { for (int j = 0; j < map[0].length; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } }} 　　代码示例：测试类 // 测试类public class Main { public static void main(String[] args) { MiGong miGong = new MiGong(8, 7); miGong.addBaffle(3, 1); miGong.addBaffle(3, 2); miGong.setDes(6, 5); // 设置目的地 System.out.println("初始地图的情况"); miGong.show(); miGong.setWay(1, 1); // 设置起始位置 System.out.println("小球走过的路径,地图的情况"); miGong.show(); }} // 结果 初始地图的情况 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 小球走过的路径,地图的情况 1 1 1 1 1 1 1 1 2 0 0 0 0 1 1 2 2 2 0 0 1 1 1 1 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 2 2 1 1 1 1 1 1 1 1 三、八皇后问题 问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 代码示例：八皇后 public class Queue8 { private static final int MAX = 8; // 保存皇后放置的位置,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3} private final int[] array = new int[MAX]; public static int count = 0; public static int judgeCount = 0; public void check() { this.check(0); } // check 是每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯 private void check(int n) { // n = 8, 表示8个皇后就已经放好 if (n == MAX) { print(); return; } for (int i = 0; i < MAX; i++) { array[n] = i; // 判断当放置第n个皇后到i列时，是否冲突 // 不冲突 if (!judge(n)) { // 接着放n+1个皇后,即开始递归 check(n + 1); } } } private boolean judge(int n) { judgeCount++; for (int i = 0; i < n; i++) { // 同一列 或 同一斜线 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { return true; } } return false; } private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); }} 代码示例：测试类 // 测试类public class Main { public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(); System.out.printf("一共有%d解法", Queue8.count); System.out.printf("一共判断冲突的次数%d次", Queue8.judgeCount); // 1.5w }}四、汉诺塔问题1、问题 2、思想 如果 n = 1，A ->

C

If n > = 2, it is always regarded as two disks, the bottom one of the ①. All the disks on the ②. Then, steps:

(1) first put all the above disks A-> B

(2) put the bottom disk A-> C

(3) change all the plates of Tower B from B-> C

3. Code

Code example: tower of Hanoi problem

/ / Hanoi public class Hanoitower {/ / using divide-and-conquer algorithm public static void move (int num, char a, char b, char c) {/ / if there is only one disk if (num = = 1) {System.out.println ("first disk from" + a + "- >" + c) } else {/ / n > = 2, which is always regarded as two disks, the one at the bottom of ①. All the disks on the ②. Step: / / 1. First put all the above disks A-> B. The move process uses c move (num-1, a, c, b); / / 2. Change the bottom disk A-> C System.out.println ("No." + num + "disk from" + a + "- >" + c); / / 3. Change all the disks of Tower B from B-> C. The mobile process uses a move (num-1, b, a, c);}

Code example: test class

/ / Test class public class Main {public static void main (String [] args) {Hanoitower.move (3, 'Aids,' bones,'C');}}

/ / result

The first disk is from A-> C

The second disk is from A-> B

The first disk is from C-> B

The third disk is from A-> C

The first disk is from B-> A

The second disk is from B-> C

The first disk is from A-> C

These are all the contents of the article "how to implement recursive algorithms in Java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.