Fibonacci Series In Java

Basic Java Program

Fibonacci Series

The Fibonacci series is a sequence of numbers in which each number (after the first two) is the sum of the two preceding ones, usually starting with 0 and 1. The sequence typically starts with 0 and 1. The Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … and so on.

Here’s how the series is generated:

• F(0) = 0
• F(1) = 1
• F(n) = F(n−1) + F(n−2) for n > 1

The series looks like this:

• 0 (first number)
• 1 (second number)
• 1 (0 + 1)
• 2 (1 + 1)
• 3 (1 + 2)
• 5 (2 + 3)
• and so on…

Fibonacci Series

Approaches for Fibonacci Series

1. Space Optimized Iterative Approach
2. Iterative Approach
3. Recursive Approach
4. Dynamic Programming Approach
5. Matrix Exponentiation Approach

Here are examples of each approach along with sample input and output.

1. Space Optimized Iterative Approach

Input: 10
Output: 0 1 1 2 3 5 8 13 21 34

import java.util.Scanner;

class FibonacciSpaceOptimized {
    public static void main(String[] args) {
         //for no custom input
         //int n = 10;     

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        if (n <= 1) {
            System.out.print(n);
            return;
        }
        int a = 0, b = 1;
        System.out.print(a + " " + b + " ");
        for (int i = 2; i < n; i++) {
            int c = a + b;
            System.out.print(c + " ");
            a = b;
            b = c;
        }
    }
}

/*     Input: 8  
       Output: 0 1 1 2 3 5 8 13     */

This program prints the first n numbers in the Fibonacci series. The number n is provided by the user as input.

Here is the detailed explanation of line by line code:

// This line imports the Scanner class, which is used to get input from the user.
import java.util.Scanner;               

// This line declares a class named "FibonacciSpaceOptimized".
class FibonacciSpaceOptimized {

/* This is the entry point of any Java application. 
The code inside this method runs when the program starts. */
    public static void main(String[] args) {

         //for no custom input
         //int n = 10; 
    
         // The below three lines are used to get input from the user.
   // Creates a Scanner object to read input from the user.
        Scanner scanner = new Scanner(System.in);
   // Reads an integer value from the user and stores it in the variable 'n'.
        int n = scanner.nextInt();
   // Closes the scanner to free up resources.
        scanner.close();


    /* The below block: If n is 0 or 1, the program simply prints n 
        because the Fibonacci series up to 1 is either 0 or 1.  */

        if (n <= 1) {
            System.out.print(n);
            return;
        }


     // Initializes the first two numbers of the Fibonacci series.
        int a = 0, b = 1;
     // Prints the first two numbers (0 and 1) of the series.
        System.out.print(a + " " + b + " ");



    /* The below for loop: The loop starts with i(index) set to 2. 
       This is because the first two numbers (0 and 1) are already handled
       before the loop starts. (int i = 2;) --> Initialization */

   /* The loop continues to execute as long as i is less than n. 
      This ensures the loop runs n - 2 times, generating the remaining 
      Fibonacci numbers after the first two.  (i < n;) --> Condition  */

   /*  After each iteration, i is incremented by 1.  (i++) --> Increment  */

        for (int i = 2; i < n; i++) {  

  /* Calculates the next Fibonacci number 
     by adding the last two numbers (a and b). */
            int c = a + b;

    // Prints the next Fibonacci number.
            System.out.print(c + " ");

  /*  Updates a and b for the next iteration. 
     a gets the value of b, and b gets the value of c  */
            a = b;
            b = c;
        }
    }
}



/*     Input: 8  
       Output: 0 1 1 2 3 5 8 13     */

How It Works in the Fibonacci Context

• Iteration Starts from 2: The loop starts at index 2 because the Fibonacci sequence already has its first two numbers (0 and 1) printed before the loop begins. So, the loop is responsible for computing and printing the numbers starting from the third position in the sequence.
• Loop Runs Until n: The loop continues running until i reaches n. This means if you want to print n Fibonacci numbers, the loop will handle generating and printing the last n - 2 numbers, as the first two numbers (0 and 1) are printed before the loop starts.

Example

Let’s say n = 8. Here's how the loop works:

• Before the Loop: Prints 0 and 1.

In the Loop:

• For i = 2: Calculate and print the 3rd Fibonacci number.
• For i = 3: Calculate and print the 4th Fibonacci number.
• For i = 4: Calculate and print the 5th Fibonacci number.
• Continue this until i = 7.

So, the loop effectively handles the calculation of the Fibonacci numbers starting from the 3rd position up to the nth position.

Space Optimized Iterative Approach is generally considered the best for practical purposes.

Time Complexity: O(n)

• The approach has a linear time complexity because it iterates through a loop to compute the Fibonacci sequence.

Space Complexity: O(1)

• It uses only a constant amount of extra space (a few variables) regardless of the input size.

2. Iterative Approach

In the iterative approach for computing Fibonacci numbers, dynamic programming principles are implicitly applied.

Dynamic programming (DP) is an optimization technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations.

In the context of the Fibonacci sequence, dynamic programming helps to compute Fibonacci numbers efficiently by storing previously computed values. Here’s how it works:

1. Subproblem Definition:

• The Fibonacci sequence is broken down into subproblems where each Fibonacci number depends on the two preceding numbers.
• Specifically, fib(n) depends on fib(n-1) and fib(n-2)
• Storing Results: We store the results of fib[i] in the fib array so we can reuse them in subsequent calculations. This avoids re-computation.
• Using Stored Results: In each iteration, we compute the next Fibonacci number using the previously computed and stored values.

public class FibonacciIterative {
    public static void main(String[] args) {
        int n = 10; // example input

        // Create an array to store the Fibonacci sequence
        int[] fib = new int[n];

        // Initialize the first two Fibonacci numbers
        // These are the starting points of the Fibonacci sequence.
        fib[0] = 0;    // base case: fib(0) = 0
        fib[1] = 1;    // base case: fib(1) = 1

        // Calculate the rest of the Fibonacci sequence using dynamic programming
        // This loop starts at i = 2 and continues until i < n.
        for (int i = 2; i < n; i++) {
            fib[i] = fib[i-1] + fib[i-2];  //(formula) use previously stored results
        }

        // Print the Fibonacci sequence
        // This loop prints out each element in the fib array.
        for (int i = 0; i < n; i++) {
            System.out.print(fib[i] + " ");
        }
    }
}

// Output: 0 1 1 2 3 5 8 13 21 34 

// Explanation

// In the first for loop
fib[i] = fib[i-1] + fib[i-2];   --> formula

Initial values:
fib[0] = 0;
fib[1] = 1;

when n=5

when i=2
fib[2]= fib[2-1] + fib[2-2]
      = fib[1] + fib[0]     // WKT, from intial values fib[0]= 0, fib[1]= 1
      = 1 + 0 
fib[2]= 1

when i=3
fib[2]= fib[3-1] + fib[3-2]
      = fib[2] + fib[1]     // WKT, from fib[2]= 1, fib[1]= 1
      = 1 + 1
fib[2]= 2

similarly, for i=4, i=5 upto n numbers.

This example uses an array to store all computed values. However, to further optimise space, only the last two computed values need to be stored at any time; therefore, it is implemented in the space-optimised iterative approach.

Time Complexity: The time complexity is determined by how many operations the algorithm performs relative to the input size n.

The total time complexity is O(1) + O(n−1), which simplifies to O(n).

Space Complexity: The space complexity is determined by how much additional space (memory) the algorithm uses relative to the input size n.

The total space complexity is dominated by the array, which is O(n).

3. Recursive Approach

What is Recursion?

Recursion is a process where a function calls itself directly or indirectly to solve a problem. A recursive function typically has two parts:

1. Base Case: The condition under which the function stops calling itself. This prevents infinite recursion and eventually provides a solution.
2. Recursive Case: The part of the function that reduces the problem into smaller subproblems and calls itself with these subproblems.

Recursive Approach in Fibonacci Series

In the recursive approach, we use the mathematical definition to create a function that calls itself to compute the Fibonacci numbers.

Recursive Function

Here is the recursive function for calculating the nth Fibonacci number:

Program Code

import java.util.Scanner;

public class FibonacciRecursion {

    // Method to calculate Fibonacci number
    public static int fibonacci(int n) {

        // If n is 0 or 1, return n (base cases)
        if (n <= 1) {
            return n;
        }

         // // Recursive case
        // For any other number, return the sum of the two preceding numbers
        return fibonacci(n - 1) + fibonacci(n - 2);
    }


    public static void main(String[] args) {

       // int count = 10; //Example input


        // Create a Scanner object for user input        
        Scanner sc = new Scanner(System.in);  

        // Prompt the user to enter the number of Fibonacci terms to print
           System.out.println("Enter the count of fibonacci series:");
           int n = sc.nextInt();
        
        // Loop to print each Fibonacci number up to the 10th term
        for (int i = 0; i < n; i++) {
          // Call the fibonacci method for the current value of i and print the result
            System.out.print(fibonacci(i) + " ");
        }
    }
}

for (int i = 0; i < n; i++) This is a for loop that starts with i equal to 0 and runs as long as i is less than n. After each iteration, i is incremented by 1.

• Initialization: int i = 0; initializes the loop variable i to 0.
• Condition: i < n; checks if i is less than n. If true, the loop continues; otherwise, it stops.
• Increment: i++ increments i by 1 after each iteration of the loop.

If the user enters 5 as the value for n, the loop will execute 5 times, with i taking values from 0 to 4:

Iteration 1 (i = 0):

• fibonacci(0) returns 0.
• System.out.print(fibonacci(0) + " "); prints 0 .

Iteration 2 (i = 1):

• fibonacci(1) returns 1.
• System.out.print(fibonacci(1) + " "); prints 1 .

Iteration 3 (i = 2):

• fibonacci(2) returns fibonacci(1) + fibonacci(0) which is 1 + 0 = 1.
• System.out.print(fibonacci(2) + " "); prints 1 .

Iteration 4 (i = 3):

• fibonacci(3) returns fibonacci(2) + fibonacci(1) which is 1 + 1 = 2.
• System.out.print(fibonacci(3) + " "); prints 2 .

Iteration 5 (i = 4):

• fibonacci(4) returns fibonacci(3) + fibonacci(2) which is 2 + 1 = 3.
• System.out.print(fibonacci(4) + " "); prints 3 .

So the output will be:

0 1 1 2 3

The loop in the main method:

• Repeats n times (where n is the user input).
• In each iteration, it calculates the Fibonacci number for the current value of i using the fibonacci method.
• Prints each Fibonacci number followed by a space, resulting in a sequence of Fibonacci numbers up to the nth term.

Space Complexity

The space complexity of the recursive Fibonacci function is O(n). This is because the maximum depth of the recursion tree is n, which means the call stack can hold up to n function calls at a time.

Time Complexity

The time complexity of the naive recursive Fibonacci algorithm is exponential, specifically O(2^n). This happens because the function recalculates the same Fibonacci numbers multiple times.

The naive recursive approach to computing Fibonacci numbers has a time complexity of O(2^n) and a space complexity of O(n). This is highly inefficient for large values of n. More efficient methods such as memorization and iterative approaches can significantly reduce both time and space complexity, making them more suitable for practical use.