This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
What is recursion
- Recursion is a procedure or function between defined or instructions or indirect calls itself a kind of method, it is usually the problem of a large complex layers into a relatively small size of the original problem similar problem to solve, recursion strategy only need a small amount of program can describe the problem solving process need repeat calculation, greatly reduced the amount of program code, Recursion has the ability to define an infinite set of objects in finite statements. In general, recursion requires boundary conditions, recursive forward sections and recursive return sections. When the boundary conditions are not satisfied, recursion advances, and when the boundary conditions are satisfied, recursion returns. == Summary: is to call themselves, but there should be recursive exit, or fall into an infinite loop ==
- 2. Recursion is commonly understood:
Suppose you are in a movie theater and you want to know what row you are sitting in, but there are so many people in front of you that you are too lazy to count, so you ask the people in front of you, “What row are you sitting in?” When the person in front of you (code name A) answers you, you know which row you are in. Just add A’s answer by one and you are in your row. Unexpectedly, A is lazier than you and he doesn’t want to count, so he also asks the person in front of him, B, “Which row are you in?” So that A knows which row it is in using exactly the same steps as you do (== calls itself ==). Then B does the same thing, == until they get to the first row of questions (or to the person who knows what row they are in, indicating the exit to the end of the recursion) ==, the person in the first row tells the person asking the question “I’m in the first row”, and finally everyone knows what row they are in
Pros and cons of recursion
2.1 Advantages of recursion
The code is more concise and clear, and readable
2.2 Disadvantages of recursion
Because recursion requires a system stack, space consumption is much higher than non-recursive code. Also, if the recursion is too deep, the system may not hold up.
Three, recursive use of matters needing attention
To use recursion, two conditions need to be met:
- There are iterative processes (calling themselves)
- There are conditions to jump out of the iterative process (recursive exit)
Iv. Classical Recursive algorithm (practical application)
4.1 Factorial, e.g. 5 factorial code implementation is as follows:
The mathematical formula for finding 5 factorial is 5×4×3×2×1
@Test
public void t1(a) {
System.out.println(jieCheng(5));
}
public int jieCheng(int a) {
//a>1 is a recursive exit
if (a > 1) {
//jiecheng(a-1) calls itself for itself
return a * jieCheng(a - 1);
} else {
returna; }}Copy the code4.2 to 1 + 2 + 3 + 4 +… And + 100
@Test
public void t2(a) {
// Result is 5050
// System.out.println(sum(100));
System.out.println(sum2(1.100));
}
/** * method 1 * computes the sum of one increment from 1 to Max@param max
* @return* /
public int sum(int max) {
if (max > 1) {
return max + sum(max - 1);
} else {
returnmax; }}/** * Method 2 * calculates the sum of one increment from min to Max, which is more general than method 1 *@param min
* @param max
* @return* /
public int sum2(int min, int max) {
if (min < max) {
return min + sum2(min += 1, max);
} else {
returnmin; }}Copy the code4.3 there is a column of numbers 1,1,2,3,5,8,13,21,34… , and find out what the 30th number is using recursion
Variants of this problem:
- Rabbits are fertile two months after birth, and a pair of rabbits can give birth to one pair of bunnies every month. If all rabbits died, how many pairs of rabbits could be bred after a year?
- Fibonacci numbers
@Test
public void t3(a) {
// Result: 832040
System.out.println(count(30));
}
public int count(int i) {
// Recursive exit
if (i == 1 || i == 2) {
return 1;
} else {
// Call yourself
return count(i - 1) + count(i - 2); }}Copy the code4.4 Stair climbing algorithm: given that a staircase has n steps, each time you can choose to take one or two steps to find how many different ways to walk
Analyze the algorithm: A: If there are 0 steps, then there are 0 ways to move. B: If there is one step, there is one way to go. C: If there are two steps, there are two ways to walk (one step at a time, two steps; Two at a time);
@Test
public void t4(a){
// Result: 8
System.out.println(climbStairs(5));
}
public int climbStairs(int n ){
// Recursive exit
if(n<=0) {return 0;
}
// Recursive exit
if(n==1) {return 1;
}
// Recursive exit
if(n==2) {return 2;
}
// Call yourself
return climbStairs(n-1)+climbStairs(n-2);
}
Copy the code4.5 Hanoi
The Hannott tower problem is an ancient conundrum consisting of a number of plates placed on three towers, as shown in the picture below, all of which have different diameters. And we had a hole plate makes it just on the tower, beginning of all the plates are on a bridge, the goal of this puzzle is around to all the plates from a tower, to tower c, can move only one plate at a time, and no one plate can be placed in its smaller plate,
So no matter how many plates, we will it as only two plates, suppose n plates on the top of a, we will be as there are only two dishes, only (n – 1) and n these two plates, a first above which a plate on the tower of the n – 1 b above, then n plate into the target tower above, and then a top is empty, as the middle tower, Take the plates below n-2 as a plate and put them on tower A in the middle. Then put the plates below N-1 on tower C. This is to find n-2 plates on tower A and empty plate B, and so on until they are all put in the refrigerator
In a nutshell:
- Move from initial tower A to contain n-1 plates on top of C
- Take the remaining plate from A and put it on top of C
- And then let’s say THAT B has n-1 plates on it, and let’s call it n and then let’s put n-1 plates in the middle on top of A
- Put the remaining plate on top of B on top of C.
…
public static void main(String[] args) {
move(3."A"."B"."C");
}
/** * Hannotta problem **@paramDish Number of dishes *@paramFrom initial tower *@paramTemp Intermediate tower *@paramTo Target tower */
public static void move(int dish, String from, String temp, String to) {
if (dish == 1) {// If there is only one disk, move it from a to C
System.out.println("Turn the plate" + dish + "From the Tower" + from + "Move to target tower." + to);
}else {
move(dish-1,from,to,temp);// A is the initial tower, B is the target tower, and C is the intermediate tower
System.out.println("Turn the plate"+dish+"From the Tower"+from+"Move to target"+to);// Move the bottom plate above a to c
move(dish-1,temp,from,to);// B is the initial tower, C is the target tower, and A is the intermediate tower}}Copy the codeFifth, the application of recursion in actual projects
Java Recursive Implementation Permission tree (Menu tree)Click on the open
Java implementation of a simple recursive operation Java recursive solution to the “nine links” formula