Preface
I saw this content recently when I was reading a book and I felt quite rewarding. Iteration uses a loop (for, while, do...wile) or an iterator, which exits when the loop condition is not met. Recursion is generally a function recursion, which can be called by itself or non-directly, that is, method A calls method B, and method B calls method A in turn, and the condition for recursive exit is if and else statement, and exits when the condition meets the basis.
The above are the syntax characteristics of iteration and recursion. What are the differences between them in Java? Let’s learn more about this article below.
1. Recursion
When it comes to iteration, we have to mention a mathematical expression: n!=n*(n-1)*(n-2)*...*1
There are many ways to calculate factorials. Anyone with a certain mathematical foundation knows n!=n*(n-1)! Therefore, the code implementation can be written directly as:
Code 1
int factorial (int n) { if (n == 1) { return 1; } else { return n*factorial(n-1); }} When executing the above code, the machine actually needs to perform a series of multiplications: factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) . Therefore, it is necessary to keep track of (track the result of the last calculation) and call multiplication to perform calculations (build a multiplication chain). This type of operation that constantly calls itself is called recursion. Recursion can be further divided into linear recursion and numerical recursion. The amount of information increases linearly with the input of the algorithm. Recursion is called linear recursion. Calculate n! (factory) is linear recursion. Because as N increases, the time required for calculation increases linearly. Another type of information that grows exponentially with the increase of input is called tree recursion.
2. Iteration
Another way to calculate n! is: first calculate 1 multiply by 2, then multiply the result by 3, and then multiply the result by 4... and multiply until N. During the implementation of the program, a counter can be defined. Each time multiplication is performed, the counter is incremented once until the value of the counter is equal to N. The code is as follows:
Code Two
int factorial (int n) { int product = 1; for(int i=2; i<n; i++) { product *= i; } return product;}Compared with code one, code two does not build a multiplication chain. When performing each step of calculation, you only need to know the current result (product) and the values of i. This form of calculation is called iteration. There are several conditions for iteration: 1. There is a variable with an initial value. 2. A rule that explains how variable values are updated. 3. An end condition. (Three elements of the loop: loop variables, loop bodies and loop termination conditions). Same as recursion. The time requirement that becomes linear as the input grows linearly can be called linear iteration.
3. Iteration vs. Recursion
After comparing the two programs, we can find that they look almost the same, especially in terms of their mathematical functions. When calculating n!, their calculation steps are proportional to the value of n. However, if we take the program's perspective and consider how they run, then the two algorithms are very different.
(Note: The original text is a bit irrelevant about the difference, so I won't translate it here. The following is the author's own summary.)
First of all, analyze recursion. In fact, the biggest thing about recursion is to decompose a complex algorithm into several identical repeatable steps. Therefore, using recursion to implement a computational logic often requires only a very short code to solve, and such code is easier to understand. However, recursion means a large number of function calls. The reason why the local state of a function call is recorded using a stack. Therefore, this may waste a lot of space, and if the recursion is too deep, it may cause stack overflow.
Next, analyze iterations. In fact, recursion can be replaced by iteration. However, compared to the simplicity and comprehension of recursion, iteration is more rigid and difficult to understand. Especially when encountering a more complex scenario. However, the difficulty of understanding of the code also brings more obvious points. The efficiency of iteration is higher than recursion and is also relatively small in space consumption.
There must be iterations in recursion, but there may not be recursions in iterations, and most of them can be converted to each other.
If you can use iteration, don’t use recursion. Calling functions recursively not only wastes space, but also can easily cause stack overflow if the recursion is too deep.
4. Recursion of numbers
As mentioned earlier, the amount of information that the tree recursive increases exponentially with the increase of input. The Fibonacci sequence is a typical example:
In text description, the sum of the first two numbers in the Fibonacci sequence is equal to the third number: 0, 1, 1, 2, 3, 5, 8, 13, 21...
The recursive implementation code is as follows:
int fib (int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fib(n-1) + fib(n-2); }} During the calculation process, in order to calculate fib(5) , the program must first calculate fib(4) and fib(3) . In order to calculate fib(4) , the program also needs to calculate fib(3) and fib(2) . Fib(3) is calculated twice during this process.
From the calculation process analyzed above, we can draw a conclusion: there is redundant calculation for the Fibonacci sequence using recursion.
As mentioned above, recursive algorithms can generally be implemented by iteratively, and the same is true for Fibonacci sequence calculations.
int fib (int n) { int fib = 0; int a = 1; for(int i=0; i<n; i++) { int temp = fib; fib = fib + a; a = temp; } return fib;}Although there will be redundant calculations in the recursion method, it can be replaced by iteration. But this does not mean that recursion can be completely replaced. Because recursion has better readability.
Summarize
The above is the entire content of this article. I hope the content of this article will be helpful to everyone in learning or using Java. If you have any questions, you can leave a message to communicate.