Program for printing nth Fibonacci Number

Posted by on Mar 31, 2024

A number "n" is given, the task is to calculate and print nth Fibonacci Number using recursion.

Example: Print 8th Fibonacci Number

Input: 8
Output: 13


Solutions

Method 1: Recursion

In a Fibonacci series 1st number is 0, 2nd number is 1 and all other numbers are represented by below equation:

Fn = Fn-1 + Fn-2

First few numbers of a Fibonacci series are shown below:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ....

Here, F1 is 0, F2 is 1 and other numbers can be derived like:

F3 = F2 + F1 = 0 + 1 = 1
F4 = F3 + F2 = 1 + 1 = 2
...

We can solve this problem easily using recursion, all we need to do is to add return values of f(n-1) and f(n-2) recursively, while keeping the base condition like - return 0 for n==1 and return 1 for n==2.

package com.cb.recursion;

/*
 * 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
 * */
public class R5_NthFibonacciNumber {

    public static int nthFibonacciNumber(int n) {
        if (n == 1)
            return 0;
        if (n == 2)
            return 1;
        return nthFibonacciNumber(n - 1) + nthFibonacciNumber(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(nthFibonacciNumber(1));
        System.out.println(nthFibonacciNumber(2));
        System.out.println(nthFibonacciNumber(3));
        System.out.println(nthFibonacciNumber(8));
    }
}
0
1
1
13

Complexity
The time complexity of this solution is O(n) and space complexity is O(1).

Related


Program to solve "Tower of Hanoi" problem

Count ways to reach the nth stair

Print numbers from 0 to a given number

Print numbers from a given number to 0

Print spelling for a given number

Check if an integer array is sorted or not

Calculate factorial of a given number

Write a program to reverse a string

Sum of the digits of a given number

Calculate the Power of a Number (n^p)