Write a java program to output the Fibonacci series using loop or recursion.
Fibonacci series is the series which start from 0 as the first element and 1 as the second element and the rest of the nth term is equal to (n-1)th term + (n-1)th term.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …
So we in order to implement this, we need to do the following
- Take input ‘n‘ from the user which denotes the number of terms in Fibonacci series.
- Assign first element a=0 and second element b=1 and third element c = 0.
- Output the first two element and loop from 3 to n.
- Update c=a+b, a=b and b=c and output the value of c. Reapeat the same steps for each iteration.
Let’s print the Fibonacci series in java using the same steps mentioned above.
Fibonacci Seiries using Loop
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n,a=0, b=1, c=0; System.out.println("Enter the value of n"); n = in.nextInt(); //Output the first and second element System.out.print(a+" "+b+" "); for(int i=3; i<=n; i++){ //Always update c first, second a and last b c = a+b; a = b; b = c; System.out.print(c+" "); } } } |
Output
|
1 2 3 |
Enter the value of n 12 0 1 1 2 3 5 8 13 21 34 55 89 |
Fibonacci Seiries using Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.Scanner; class Main { static int nFibo[] = new int[100]; public static void main(String[] args) { Scanner in = new Scanner(System.in); nFibo[0] = 0; nFibo[1] = 1; int n; System.out.println("Enter the value of n"); n = in.nextInt(); for(int i=1; i<=n; i++){ //For ith term call recursive function System.out.print(fibonacci(i)+" "); } } //Recursive function to return the nth term of the Fibonacci series private static int fibonacci(int n){ if(n==1){ return 0; } else if(n == 2){ return 1; } else { return fibonacci(n-2)+fibonacci(n-1); } } } |
Output
|
1 2 3 |
Enter the value of n 10 0 1 1 2 3 5 8 13 21 34 |
In the above program, we are computing and returning the nth term of Fibonacci series from the recursive function. In each recursive call, we are doing the same calculation over again as done for the (n-1)th term. So recursive way of finding the Fibonacci term is not efficient.
To optimize it we can use dynamic programming for Fibonacci series.
If you have any suggestion or doubts then please comment below.