# Fibonacci Series Using Recursive function

Fibonacci series implementation in java is frequently asked question in interview at fresher level. Moreover, it is a very famous example to show how to use recursive function in java.

## Recursive Approach

``````public class Fibonacci {

public static void main(String[] args) {
fibonacci(10);
}

/**
* print fibonacci series from 0 to n
* @param n
*/
private static void fibonacci(int n) {
for (int i = 0; i <= n; i++) {
System.out.print(fib(i) + ", ");
}
}

/**
* Recursive approach f(n) = f(n-1) + f(n-2)
* @param n
* @return
*/
public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
``````
``````Output
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
``````

Recursive approach time complexity is approx `𝘖(2ⁿ)`

## Dynamic Approach

We can use dynamic approach for linear time complexity i.e. `𝘖(n)`

``````public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
``````