Finbonacci Series

The following sequence of numbers is known as Fibonacci numbers or sequence or series.

0, 1, 1, 2, 3, 5, 8, 13, 21 ….

To obtain the sequence, we start with 0 and 1 after which every number is the sum of the previous two numbers.

For example, the first two numbers will be 0 and 1

0, 1

To obtain the next number, we add the previous two numbers – 0 and 1 which gives one.

0, 1, 1

The next number would be 1 + 1 = 2

0, 1, 1, 2

Now, the next number would be 1 + 2 = 3

0, 1, 1, 2, 3

Continuing in this way gives the Fibonacci series. A particular term in the series is represented as F_n where n is the position of that number from the beginning. For example, F₀ = 0, F₁ = 1, F₂ = 1, F₃=2, F₄ = 3, F₅ = 5 and so on…

The Fibonacci series can be expressed as a recurrence relation as shown below:

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2 ; n>=2

Printing the Fibonacci Series using Iteration

We will see how recursion can be used to print the Fibonacci Series. We will write a program which takes an input n and prints the first (n+1) terms of the Fibonacci series. n = 0 and n = 1 will be considered as special cases and the series for these input values of n will be printed directly. We will use two variables a and b which will hold the last two terms of the Fibonacci series that has already been printed. For example, after printing the first five terms of the sequence, i.e. 0, 1, 1, 2, 3; the value of a will be 2 and b will be 3. The next term in the sequence will be the sum of a and b. Now, the values of a and b should be updated so that they will again hold the last two terms that were printed. To do so, we copy b to a, and the sum of the previous values of a and b to b. The loop will be repeated n-1 times.

The program is given below.

Import java.util.Scanner;

public class FibonacciSeries {

   public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
       System.out.print(“Enter the value of n: “);
       int n = s.nextInt();
       fibonacci(n);
   }

   public static void fibonacci(int n) {
       if (n == 0) {
           System.out.println(“0”);
       } else if (n == 1) {
           System.out.println(“0 1”);
       } else {
           System.out.print(“0 1 “);
           int a = 0;
           int b = 1;
           for (int i = 1; i < n; i++) {
               int nextNumber = a + b;
               System.out.print(nextNumber + ” “);
               a = b;
               b = nextNumber;
           }
       }
   }
}

Here is a sample execution

Enter the value of n: 7
0 1 1 2 3 5 8 13

Fibonacci Series using Recursion

The recursive definition of Fibonacci Series has already been stated at the start of this article. The Java program is given below.

Import java.util.Scanner;

public class FibonacciSeries {

   public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
       System.out.print(“Enter the value of n: “);
       int n = s.nextInt();
       for (int i = 0; i <= n; i++) {
           System.out.print(fibonacci(i) + ” “);
       }
   }

   public static int fibonacci(int n) {
       if (n == 0) {
           return 0;
       } else if (n == 1) {
           return 1;
       } else {
           return fibonacci(n – 1) + fibonacci(n – 2);
       }
   }
}