# Java recursively implements the Fibonacci sequence

- 2021-01-25 07:32:36
- OfStack

The programming technique in which a program calls itself is called recursion (recursion). Recursion is widely used in programming languages as a kind of algorithm. A procedure or function in the introduction to the definition or calls itself, directly or indirectly, with one kind of method, it is usually the problem of a large complex layers into a similar to the original problem of smaller problems to solve, the recursion strategy only a small number of procedures can be required to describe the problem solving process of repeatedly calculation, greatly reduces the amount of program code. The power of recursion is to define an infinite set of objects with a finite number of statements. In general, recursion requires a boundary condition, a recursive forward segment and a recursive return segment. When the boundary conditions are not satisfied, recursive progress is made. When the boundary conditions are met, the recursion returns. This is said by Baidu Baike.

Basically, it's an operation that the recursive method calls itself, and let's take an example of one of the famous Fibonacci sequences.

0, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610, 987, 1597, 2584, 4181, 6765, 10946,1771, 28657,46368...

You can see that the third number is the sum of the first two numbers.

It would look like this if we used a normal loop:

```
public class FeiBo{
public static void main(String[] args) {
int num1=0;
int num2=1;
int numn=1;
int n=10;
for (int i = 3; i <=n; i++) {
numn=num1+num2;
num1=num2;
num2=numn;
}
System.err.println(n+" The result of the number is: "+numn);
}
}
```

The running results are as follows:

The result of 10 numbers is 34

This is done using the normal loop method, if you use recursion it would be one like this:

```
public static int Recursion(int n){
if(n==1){
return 0;
}
if(n==2){
return 1;
}
return Recursion(n-1)+Recursion(n-2);
}
```

Recursion requires an end condition, in which case the recursion doesn't need to continue calling, end the recursion. The above case ending condition is that when n=1 or 2, it returns 0 or 1, rather than calling the recursive method itself.

The two main conditions for recursion are the conditions for ending the recursion by calling itself.

Because recursion calls itself, it wastes a lot of resources, takes a lot longer to run than loops, runs slower, and is less efficient.