JAVA recursive and non recursive Fibonacci sequences are implemented

The Fibonacci sequence (Fibonacci sequence), also known as the golden section sequence, is introduced by the mathematician Leonardo Fibonacci (Leonardoda Fibonacci[1]) with the breeding of rabbits as an example, so it is also known as the "rabbit sequence", which refers to a sequence of 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... In mathematics, the Fibonacci sequence is defined recursively as follows: F (0) = 0, F (1) = 1, F (n) = F (n - 1) + F (n - 2), (n 2 or higher, n ∈ N *) in the modern physics, quasi crystal structure, chemical and other fields, the Fibonacci sequence has an immediate application, therefore, the American mathematical society published since 1963 by the name of the Fibonacci sequence quarterly 1 mathematics magazine, used to devoted to the research results.

Here I use JAVA to implement recursive and non-recursive methods differently:

public class Feibonacii {
  // Use recursive methods to implement the Fibonacci sequence 
  public static int feibonaci1(int n){
    if(n==0){return 0;}
    if(n==1){return 1;}
    return feibonaci1(n-1)+feibonaci1(n-2);
  }
  // The Fibonacci sequence is implemented using a non-recursive method 
  public static int feibonaci2(int n){
    int arr[] = new int[n+1];
    arr[0]=0;
    arr[1]=1;
    for(int i=2;i<=n;i++){
      arr[i] = arr[i-1]+arr[i-2];
    }
    return arr[n];
  }

  public static void main(String[] args) {
    for(int i=40;i<=45;i++){
      System.out.println("feibonaci1 i="+i+",vaule="+feibonaci1(i));
    }
    for(int i=40;i<=45;i++){
      System.out.println("feibonaci2 i="+i+",vaule="+feibonaci2(i));
    }
  }
}

It is obvious that the recursive method 43 is relatively slow after execution, and the non-recursive method is quite fast.

Analysis:

(1) Java uses the method to recursively implement the Fibonacci sequence, feibonaci1 (45) executes once, Java executes the method feibonaci1 has 2^44+2^43+... +2^1+1 times, while feibonaci2(45) only executes the method once, but the number of computations is the same as feibonaci11.

Conclusion: JAVA describes Fibonacci sequence, which is more suitable for non-recursive calculation.