Detailed explanation of iteration and recursion examples in Java

This article mainly introduces you to iteration and recursion in Java. The article shows that introduces iteration and recursion in Java respectively, and then introduces iteration and recursion. The difference between and the related content of number-shape recursion are introduced in detail in the article. I believe it will be of certain reference value for everyone's study. Friends in need can refer to it.

Preface

I recently saw this content when I was reading a book, and I felt it was quite rewarding. Iteration uses loops (for, while, do...wile) or iterators, and exits when the loop conditions are not met. Recursion, generally function recursion, can call itself, or it can be an indirect call, that is, method A calls method B, and method B in turn calls method A. The conditions for recursive exit are if, else statement , exit when the condition meets the base.

The above are the grammatical features of iteration and recursion. What are their differences in Java? Learn more about it through this article below.

1. Recursion

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

There are many ways to calculate factorial. Anyone with a certain mathematical foundation knows that n!=n*(n-1)! Therefore, the implementation of the code can be written directly:

Code 1

int factorial (int n) {
 if (n == 1) {
  return 1;
 } else {
  return n*factorial(n-1);
 }
}

In When executing the above code, the machine actually has to perform a series of multiplications: factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) . Therefore, it is necessary to continuously track (track the result of the last calculation) and call multiplication for calculation (build a multiplication chain). This type of operation that continuously calls itself is called recursion. Recursion can be further divided into linear recursion and numerical recursion. Recursion in which the amount of information increases linearly with the input of the algorithm is called linear recursion. Computing n! (factorial) is linear recursion. Because as N increases, the time required for calculation increases linearly. Another type of information that increases exponentially as the input increases is called tree recursion.

2. Iteration

Another way to calculate n! is: first multiply 1 times 2, and then multiply the result by 3. Multiply the obtained result by 4... and multiply until N. When implementing the program, you can define a counter. Each time a multiplication is performed, the counter will increment until the counter value is equal to N. The code is as follows:

Code 2

int factorial (int n) {
 int product = 1;
 for(int i=2; i<n; i++) {
  product *= i;
 }
 return product;
}

Compared with code 1, code 2 does not build a multiplication chain. When performing each calculation step, you only need to know the current result (product) and the value 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 describes how variable values ​​are updated. 3. An ending condition. (Three elements of a loop: loop variables, loop body and loop termination condition). Same as recursion. Time requirements that grow linearly with input can be called linear iterations.

3. Iteration VS Recursion

Comparing the two programs, we can find that they look almost the same, especially their mathematical functions aspect. When calculating n!, their number of calculation steps is proportional to the value of n. However, if we consider how they operate from the perspective of the program, then the two algorithms are very different.

(Note: The original article is a bit silly about the difference, so I won’t translate it here. The following is the author’s own summary.)

First analyze recursion. In fact, the biggest advantage of recursion is that A complex algorithm is broken down into a number of identical repeatable steps. Therefore, using recursion to implement a calculation logic often requires only a short code to solve, and such code is relatively easy to understand. However, recursion means a lot of function calls. The reason why the local state of function calls is recorded using the stack. Therefore, this may waste a lot of space, and may cause stack overflow if the recursion is too deep.

Next analyze the iteration. In fact, recursion can be replaced by iteration. But compared to recursion, which is simple and easy to understand, iteration is more blunt and difficult to understand. Especially when encountering a more complex scene. However, the disadvantages brought by the difficulty of understanding the code are also obvious. Iteration is more efficient than recursion and consumes less space.

        There must be iteration in recursion, but there is not necessarily recursion in iteration, and most of them can be converted into each other.

    Don’t use recursion if you can use iteration. Recursive calling functions not only waste space, but also easily cause stack overflow if the recursion is too deep.

4. Number shape recursion

前面介绍过，树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列：

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字：0,1,1,2,3,5,8,13,21……

递归实现代码如下：

int fib (int n) {
 if (n == 0) {
  return 0;
 } else if (n == 1) {
  return 1;
 } else {
  return fib(n-1) + fib(n-2);
 }
}

计算过程中，为了计算fib(5) ，程序要先计算fib(4) 和 fib(3) ，要想计算fib(4) ，程序同样需要先计算 fib(3) 和 fib(2) 。在这个过程中计算了两次fib(3)。

从上面分析的计算过程可以得出一个结论：使用递归实现斐波那契数列存在冗余计算。

就像上面提到的，可以用递归的算法一般都能用迭代实现，斐波那契数列的计算也一样。

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

虽然使用递归的方式会有冗余计算，可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。

The above is the detailed content of Detailed explanation of iteration and recursion examples in Java. For more information, please follow other related articles on the PHP Chinese website!