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)**.