Fibonacci - Recursive and Iterative implementation in Java

Fibonacci.java

package megha.codingproblems.general;

/**
 * Fibonacci program - Both iterative and recursive versions
 * Fibonacci series - 1,1,2,3,5,8,13....
 * 
 * @author megha krishnamurthy
 *
 */
public class Fibonacci {
	
	/**
	 * Iterative implementation for nth fibonacci number
	 * Time complexity - O(n)
	 * Space complexity - O(1)
	 * 
	 * @param n
	 * @return
	 */
	public int fibonacciIterative(int n) {
		if(n <= 1) {
			return n;
		}
		int fib = 1;
		int prevFib = 1;
		
		for(int i=2; i<n; i++) {
			int temp = fib;
			fib+= prevFib;
			prevFib = temp;
		}
		return fib;
	}
	
	/**
	 * Recursive implementation for nth fibonacci number
	 * Time complexity - O(n)
	 * Space complexity - O(n)
	 * 
	 * @param n
	 * @return
	 */
	public int fibonacciRecursive(int n) {
		if(n <= 1) {
			return n;
		}
		return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
	}
	
	public static void main(String args[]) {
		Fibonacci fib = new Fibonacci();
		
		System.out.println("Iterative version:");
		System.out.println(fib.fibonacciIterative(5));
		System.out.println(fib.fibonacciIterative(10));
		System.out.println(fib.fibonacciIterative(20));
		System.out.println(fib.fibonacciIterative(30));
		
		System.out.println("Recursive version:");
		System.out.println(fib.fibonacciRecursive(5));
		System.out.println(fib.fibonacciRecursive(10));
		System.out.println(fib.fibonacciRecursive(20));
		System.out.println(fib.fibonacciRecursive(30));
	}
}

The time complexity for your recursive implementation is definitely not O(n). It's O(2^n). Try calling it for n=100 and you'll see how long it takes. (Landed here from a Google search.)

@kevindice I also landed here from a google search somehow lol. Anyway, you’re absolutely right!

Note to future readers: the recursive implementation can be improved to O(n) time complexity w/ memoization.

I also reached here from google search. You're all right! He needs to fixe
the comments inside his code. His recursive Fibonacci algorithm is the naive one
which is O(2^n).

I also ended up here with a google search. O(2^n) is defiantly the correct complexity for recursive Fibonacci

The recursive Fibonacci can be O(n) by adding a simple cache:

public int fibonacciRecursive(int n) {
    return fibonacciRecursiveCache(new int[n+1], n);	
}

public fibonacciRecursiveCache(int[] cache, int n) {
    if (n <= 1) {
	    return n;
    }
    if (cache[n] == 0) {
        cache[n] = fibonacciRecursiveCache(cache, n-1) + fibonacciRecursiveCache(cache, n-2);
    } 
    return cache[n];
}

The recursive Fibonacci can be O(n) by adding a simple cache:

public int fibonacciRecursive(int n) {
    return fibonacciRecursiveCache(new int[n+1], n);	
}

public fibonacciRecursiveCache(int[] cache, int n) {
    if (n <= 1) {
	    return n;
    }
    if (cache[n] == 0) {
        cache[n] = fibonacciRecursiveCache(cache, n-1) + fibonacciRecursiveCache(cache, n-2);
    } 
    return cache[n];
}

Actually, the Fibonacci version using memoization would look like this

public static void main(String[] args) {	

		int n = 3;	
		Integer [] memo = new Integer [n];
		
		int result = fibonacci(n, memo);
		
		System.out.println(result);
	}

	private static int fibonacci(int n, Integer[] memo) {
		// TODO Auto-generated method stub
		int result;
		if (memo[n-1]!= null ) {
			return memo[n-1];
		}else {
			
			if(n <= 2) {
				result = 1;
			}else {
				
				result = fibonacci(n-1, memo) + fibonacci(n-2, memo);
			}
			
			memo[n-1] = result;
		}
		return result;
	}

You gotta check if the memo already contains the result for a specific 'n', otherwise you need to compute it and store it in the memo array. This should avoid computing the same thing over and over again

The recursive implementation's time complexity is about O(1.6^n), to be somewhat more precise. Still exponential, still untenable.