preface
This article is from dwz.win/HjK. Click to unlock more data structures and algorithms.
Hello, I am tong elder brother, a daily climb 26 floors also do not forget to read the source code of the hardcore man.
In the last section, we used bitmap to introduce the implementation of 12306 ticket snatching algorithm. Students who have not received the push can click the album above to view it, or check it in the princess history message.
At the end of the last section, Tong Brother received the latest information that all recursion can be rewritten as non-recursion, is it true? How do you do that? Is there a formula?
Let’s go into today’s study with these questions in mind.
What is recursion?
Recursion refers to the behavior that the program calls itself in the process of running.
This behavior can’t go on indefinitely, there has to be an exit, called a boundary condition, so recursion can be divided into three segments: forward, reach the boundary condition, and return, and in all three segments we can do things, such as forward to reduce the size of the problem, return to sort out the results.
At the risk of being abstract, let’s look at a simple example:
How do I add 1 to 100 recursively?
Add 1 to 100 using a loop everyone can solve, the code is as follows:
public class Sum {
public static void main(String[] args) {
System.out.println(sumCircle(1.100));
}
private static int sumCircle(int min, int max) {
int sum = 0;
for (int i = min; i <= max; i++) {
sum += i;
}
returnsum; }}Copy the codeSo, how do you use recursion?
How to implement recursion quickly?
First of all, we need to find the boundary conditions for this problem, so if you add 1 to 100, the boundary conditions can be 1 or 100, if you start at 1, then the boundary conditions are 100, and vice versa.
So once we have the boundary conditions, we’re just going to reduce the size of the problem, so for this problem, we’re going to add 1 to 100, so can we add 1 to 99 and then add 100? It must be, and then the size of the problem gets smaller, until the size of the problem is reduced to the sum of 1 and 1.
OK, let’s look at the code implementation:
private static int sumRecursive(int min, int max) {
// Boundary conditions
if (min >= max) {
return min;
}
// The size of the problem shrinks
int sum = sumRecursive(min, max - 1);
// Add the current value
sum += max;
/ / return
return sum;
}
Copy the codeIsn’t that easy? It could be even simpler:
private static int sumRecursive2(int min, int max) {
return min >= max ? min : sumRecursive2(min, max - 1) + max;
}
Copy the code686?
So, the most important thing to do with recursion is to find the boundary conditions, and then let the size of the problem shrink in the direction of the boundary conditions, until the boundary conditions are reached, and then return in turn, which is also a fast way to achieve recursion.
Recursion seems simple enough, but what are the downsides?
To understand the downside, start with the nature of recursion.
What is the nature of recursion?
As we know, the JVM starts with a parameter called -xss, which is not an Xss attack, but the size of the thread stack that can be used by each thread.
So what is a thread stack?
Stack we all understand, we also learned in the previous chapter, using the stack, you can realize the function of the calculator, very convenient.
A thread stack, as the name suggests, is the stack that a thread uses during its execution.
So why would a thread use a stack when it runs?
This brings us to the nature of method calls.
Here’s a simple example:
private static int a(int num) {
int a = 1;
return a + b(num);
}
private static int b(int num) {
int b = 2;
return c(num) + b;
}
private static int c(int num) {
int c = 3;
return c + num;
}
Copy the codeIn this code, method A () calls method B () and method B () calls method c(). In the actual run, this is done: If you call method A () and find that you need to call method B () to return, you push method A () and its state onto the stack and call method B (). Similarly, if you call method B () and find that you need to call method C () to return, you push method B () and its state onto the stack and call method C (). When you call method C (), No need to call other methods, return after calculation, take method B () and the state at that time from the top of the stack, continue to run method B (), method B () is finished, return, take method A () and the state at that time from the stack, calculation is finished, method A () returns, the program waits.
Go ahead.
So, the essence of method calls is the use of stacks.
Similarly, a recursive call is a call to a method, so a recursive call is also a use of a stack, but the stack becomes very large, for example, for a sum of 1 to 100, there are 99 on and off the stack operations.
So, to sum up, recursion has the following two disadvantages:
- The operation is time-consuming because it involves a large number of operations on and off the stack;
- It is possible to cause a thread stack overflow because recursive calls take up a lot of space in the thread stack.
So, should we not use recursion?
Of course not. The reason we use recursion is because it’s very simple to use, it solves our problem quickly, and it’s a good recursion to control the length of the recursive call chain.
Since the essence of recursive calls is the use of stacks, can we simulate a stack ourselves and make recursive calls non-recursive?
B: Sure.
Modify recursion to a non-recursive routine
Using the example above, now we need to change the recursion to non-recursion instead of using the for loop. How do we do that?
First, we simulate a stack ourselves;
Then, find the boundary conditions;
Finally, the scale of the problem is reduced in the direction of boundary conditions.
OK, the code:
private static int sumNonRecursive(int min, int max) {
int sum = 0;
// Declare a stack
Stack<Integer> stack = new Stack<Integer>();
stack.push(max);
while(! stack.isEmpty()) {if (max > min) {
// To calculate Max, calculate Max -1
stack.push(--max);
} else {
// The problem shrinks to a certain size, and the calculation returnssum += stack.pop(); }}return sum;
}
Copy the codeOk, is not very simple, in fact, with the recursive routine is the same, but changed to simulate their stack to achieve.
This might not be obvious, but let’s do a binary tree traversal.
public class BinaryTree {
Node root;
// Insert elements
void put(int value) {
if (root == null) {
root = new Node(value);
} else {
Node parent = root;
while (true) {
if (value <= parent.value) {
if (parent.left == null) {
parent.left = new Node(value);
return;
} else{ parent = parent.left; }}else {
if (parent.right == null) {
parent.right = new Node(value);
return;
} else {
parent = parent.right;
}
}
}
}
}
// order traversal first
void preTraversal(Node x) {
if (x == null) return;
System.out.print(x.value + ",");
preTraversal(x.left);
preTraversal(x.right);
}
static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value; }}public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.put(3);
binaryTree.put(1);
binaryTree.put(2);
binaryTree.put(7);
binaryTree.put(8);
binaryTree.put(5);
binaryTree.put(4);
binaryTree.put(6);
binaryTree.put(9);
binaryTree.put(0); binaryTree.preTraversal(binaryTree.root); }}Copy the codeI wrote a binary tree here and implemented its sequential traversal. The binary tree in this test case looks like this:
So, the sequential traversal of the binary tree is 3,1,0,2,7,5,4,6,8,9.
As you can see, it’s very easy to traverse a binary tree using recursive preordering, and the code is clear and understandable, so how does it change to a non-recursive implementation?
First, we simulate a stack ourselves;
Then, the boundary condition is found, where the node is equal to null time;
And finally, to scale down the problem, we’re pushing the right subtree first, and then the left subtree, because we’re pushing left then right;
Ok, let’s look at the code implementation:
// Iterate through the non-recursive form first
void nonRecursivePreTraversal(Node x) {
// simulate a stack yourself
Stack<Node> stack = new Stack<Node>();
stack.push(x);
while(! stack.isEmpty()) { Node tmp = stack.pop();// Implicit boundary conditions
if(tmp ! =null) {
System.out.print(tmp.value + ",");
// Reduce the size of the problemstack.push(tmp.right); stack.push(tmp.left); }}}Copy the codeIt’s pretty easy to learn how to rewrite recursion as non-recursion, but it’s not as clear as recursion.
Okay, recursion to non-recursion and we’ll stop there, do you Get it? You can also try to find a recursion and rewrite it yourself.
Afterword.
In this section, we started with the concept of recursion, learned how to quickly implement recursion, and the nature of recursion, and finally, learned how to rewrite recursion into non-recursion.
In essence, this is a common use of data structures such as stacks.
Now that we’re talking about stacks, isn’t it a little overkill not to talk about queues?
So, the next section, traversing a variety of source tong brother will introduce how to achieve high performance queue, want to understand the routine? Don’t hurry up and pay attention to me!
Pay attention to the main public number “Tong Elder brother read source code”, unlock more source code, foundation, architecture knowledge.