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

This article introduces the relevant knowledge of "how to use java recursion to achieve the addition of 1 to 100". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

What is recursion?

The so-called recursion refers to the behavior that the program calls itself in the process of running.

This kind of behavior can not be carried out indefinitely, there must be an exit, called the boundary condition, so the recursion can be divided into three segments: the forward section, the boundary condition reached, and the return segment, in which we can all do some things. for example, the forward section reduces the scale of the problem, and the return section collates the results.

This may be abstract, let's look at a simple case:

How to add 1 to 100 with recursion?

Everyone can solve the loop by adding up from 1 to 100. 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) {return min;} / / reduce the size of the problem int sum = sumRecursive (min, max-1); / / add the current value sum + = max / / return return sum;}

Isn't it easy? It could be simpler:

Private static int sumRecursive2 (int min, int max) {return min > = max? Min: sumRecursive2 (min, max-1) + max;}

six hundred and eighty six?

Therefore, the most important thing to use recursion is to find the boundary conditions, and then let the scale 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.

In this way, it seems easy to use recursion, but does it have any disadvantages?

To understand the shortcomings, we have to start with the nature of recursion.

What is the nature of recursion?

We know that when JVM starts, there is a parameter called-Xss, which does not represent a XSS attack, it refers to the size of the thread stack that each thread can use.

So, what is a thread stack?

Stack we all understand, we have also learned in the previous chapter, the use of stack, you can achieve the function of calculator, very convenient.

The thread stack, as its name implies, refers to the stack used when the thread is running.

So why do threads use stacks when they are running?

We have to talk about the nature of method invocation.

Take 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;}

In this code, method a () calls method b (), and method b () calls method c (). In the actual operation, it is handled like this: when method a () is called, it is found that method b () needs to be called before it can be returned, so save method a () and its state to the stack, and then call method b (). Similarly, when method b () is called Find that you need to call method c () before you can return, then put method b () and its state into the stack, and then call method c (). When method c () is called, there is no need to call other methods. After the calculation is finished, the method b () and the state at that time are taken out from the top of the stack, and the method b () continues to run. Method b () finishes running and returns. Then take method a () and the state at that time from the stack, the calculation is finished, the method a () returns, and the program waits for the end.

Let's take the above picture:

Therefore, the essence of method calls is the use of stacks.

By the same token, a recursive call is a method call, so a recursive call is also the use of a stack, but the stack becomes very large, for example, 99 operations on and off the stack for the addition of 1 to 100.

Therefore, to sum up, recursion has the following two disadvantages:

The operation is time-consuming because a large number of in-and-out operations are involved.

It is possible to cause a thread stack overflow because recursive calls take up a lot of space on the thread stack.

So, should we not use recursion?

Of course not, the reason for using recursion is that it is very easy to use, can quickly solve our problems, and reasonably control the length of the recursive call chain is a good recursion.

Since the essence of recursive calls is the use of stacks, can we simulate a stack ourselves and change recursive calls to non-recursive ones?

Yes, of course.

Modify the routine of recursion to non-recursion

Still using the above example, now we need to change the recursion to be non-recursive and not in the form of a for loop. How do we do that?

First, we have to simulate a stack ourselves.

Then, find the boundary condition.

Finally, reduce the scale of the problem in the direction of the boundary conditions.

OK, code above:

Private static int sumNonRecursive (int min, int max) {int sum = 0; / / declare a stack Stack stack = new Stack (); stack.push (max); while (! stack.isEmpty ()) {if (max > min) {/ / to calculate max, first calculate max-1 stack.push (--max) } else {/ / the size of the problem is reduced to a certain extent, and the calculation returns sum + = stack.pop ();}} return sum;}

Well, is it very simple? in fact, it is the same as the routine of recursion, but it is changed to your own simulation stack to achieve.

This example may not be so obvious, let's take another example of binary tree traversal.

Public class BinaryTree {Node root; / / insert element void put (int value) {if (root = = null) {root = new Node (value);} else {Node parent = root; while (true) {if (value)

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.