Fibonacci Series Using Recursive function 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];
}