Nth Fibonacci number

Write a method to generate the nth Fibonacci number.

My initial thoughts:

  • Base case: F(0) = 0, F(1) = 1.
  • Recursion: F(n) = F(n-1) + F(n-2)

My initial codes:

	public static int Fibonacci(int n) {
		if (n < 0)
			return -1;
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}

Solution:

  1. Recursive solution:
    	public static int fibo(int n) {
    		if (n == 0) {
    			return 0; // f(0) = 0
    		} else if (n == 1) {
    			return 1; // f(1) = 1
    		} else if (n > 1) {
    			return fibo(n - 1) + fibo(n - 2); // f(n) = f(n—1) + f(n-2)
    		} else {
    			return -1; // Error condition
    		}
    	}
    

    Comments:

    1. Handles more error conditions than mine.
    2. Time complexity: O(2^{n}); Space complexity O(n) considering the function call stack.
  2. Iterative Solution:
    	public static int IterativeFibo(int n) {
    		if (n < 0)
    			return -1; // Error condition.
    		if (n == 0)
    			return 0;
    		int a = 1, b = 1;
    		for (int i = 3; i <= n; i++) {
    			int c = a + b;
    			a = b;
    			b = c;
    		}
    		return b;
    	}
    

    Comments:
    Time complexity: O(n); Space complexity O(1).

    Advertisements

1 Comment (+add yours?)

  1. AndroidResearch
    Mar 25, 2012 @ 13:06:03

    One of those question you might get on an interview.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: