Program for printing nth Fibonacci Number

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));
    }
}