Iteration and recursion in Java

preface

Recently, I saw this content when I was reading a book. I felt quite fruitful. Iteration uses a loop (for, while, do... Will) or iterator. When the loop conditions are not met, it exits. Recursion is generally function recursion, which can call itself or indirectly, that is, method a calls method B, and method B calls method a in turn. The conditions for recursive exit are if and else statements. When the conditions meet the base, it exits.

Above are the syntax features of iteration and recursion. How are they different in Java? Let's learn more through this article.

1、 Recursion

When it comes to iteration, I have to mention a mathematical expression: n= n*(n-1)*(n-2)*...* one

There are many ways to calculate factorials. People with a certain mathematical foundation know n= n*(n-1)! Therefore, the implementation of the code can be directly written as:

Code one

When executing the above code, the machine actually performs a series of multiplication: factorial (n) → factorial (n-1) → factorial (n-2) →... → factorial (1). So, It is necessary to continuously track (track the result of the last calculation) and call multiplication for calculation (build a multiplication chain). This kind of operation form that continuously calls itself is called recursion. Recursion can be further divided into linear recursion and number shape recursion. Recursion with linear growth of information with the input of the algorithm is called linear recursion. Calculation n! (factorial) is linear recursion. Because the time required for calculation increases linearly with the increase of N. another kind of information that increases exponentially with the increase of input is called tree recursion.

2、 Iteration

Another calculation n! The method is: first calculate 1 times 2, then multiply the result by 3, and then multiply the result by 4 Multiply to n. In the program implementation, a counter can be defined. Each multiplication, the counter will increase once until the value of the counter is equal to n. The code is as follows:

Code two

Compared with code one, code two does not build a multiplication chain. During each calculation, You only need to know the values of the current result (product) and I. This form of calculation is called iteration. Iteration has several conditions: 1. There is a variable with initial value. 2. A rule describing how the variable value is updated. 3. An end condition. (loop three elements: loop variable, loop body and loop termination condition). The same as recursion. The time requirement is linear with the increase of input, which can be called linear iteration.

3、 Iteration vs recursion

Comparing the two programs, we can find that they look almost the same, especially in terms of their mathematical functions. Calculating n! Their calculation steps are proportional to the value of n. However, if we consider how they work from the perspective of programs, the two algorithms are very different.

(Note: the original text is a little lame about its differences, so it will not be translated here. The following is the author's own summary.)