ISC Practicals and Theory - Fibonacci Series

The Fibonacci series is a sequence of numbers in which every term, after the first two, is the sum of the two terms before it. This note prints the first $n$ terms using a method that calls itself.

Definition

The Fibonacci series starts with $0$ and $1$. Each next term is the sum of the previous two terms:

$F_1 = 0,\ F_2 = 1,\ F_t = F_{t-1} + F_{t-2}$ for $t > 2$

For example, the first 8 terms are $0, 1, 1, 2, 3, 5, 8, 13$, because $1 + 1 = 2$, $1 + 2 = 3$, $2 + 3 = 5$ and so on.

A method is recursive when it calls itself with a smaller value until it reaches a case it can answer directly (the base case). Here the definition of $F_t$ is already recursive, so the method follows it exactly.

Algorithm

1. Start. In main, create an object ob of class Fibonacci.
2. Call accept(): read the number of terms into n.
3. Call display():
   • If n is $0$ or negative, print an error message and stop.
   • Otherwise run a loop with i from $1$ to n.
   • In each pass print fib(i) followed by a space.
4. The method fib(int t) works as follows:
   • If t is $1$, return $0$ (base case).
   • If t is $2$, return $1$ (base case).
   • Otherwise return fib(t - 1) + fib(t - 2), which is the recursive call.
5. Stop.

Program

The constructor sets n to $0$, accept() reads the input, fib() finds one term recursively and display() prints the series.

import java.util.Scanner;

public class Fibonacci
{
    int n;

    Fibonacci()
    {
        n = 0;
    }

    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of terms: ");
        n = sc.nextInt();
    }

    int fib(int t)
    {
        if (t == 1)
            return 0;
        if (t == 2)
            return 1;
        return fib(t - 1) + fib(t - 2);
    }

    void display()
    {
        if (n <= 0)
        {
            System.out.println("Invalid input. Number of terms must be positive.");
            return;
        }
        System.out.print("Fibonacci series: ");
        for (int i = 1; i <= n; i++)
            System.out.print(fib(i) + " ");
        System.out.println();
    }

    public static void main(String args[])
    {
        Fibonacci ob = new Fibonacci();
        ob.accept();
        ob.display();
    }
}

Variable description table

Sample input and output

Enter the number of terms: 8
Fibonacci series: 0 1 1 2 3 5 8 13 

Enter the number of terms: 1
Fibonacci series: 0 

Enter the number of terms: 0
Invalid input. Number of terms must be positive.

Enter the number of terms: -3
Invalid input. Number of terms must be positive.

Dry run

Take $n = 8$. The loop calls fib(i) for i = 1 to 8.

The loop ends when i becomes 9. The output is 0 1 1 2 3 5 8 13, the same as the real run above.

Variations

1. Loop version - "Write a program to display the first n terms of the Fibonacci series using a loop."
2. Sum of terms - "Write a program to find the sum of the first n terms of the Fibonacci series using recursive technique."
3. Range - "Write a program to display the Fibonacci terms that lie between m and n."
4. Check a term - "Write a program to accept a number and check whether it is a term of the Fibonacci series."