CareerCup

Surprisingly no one wrote the test cases which is an important part of this question. Algorithm is commonly available everywhere.

Test cases:
n=-1
n=0
n=1
n=2
n=max int
Check for memory available and check if recursive solution is acceptable
What happens when the system runs out of memory
Check for performance on the designated device. Do we need dynamic programming because it is super slow?

We can avoid the repeated work done is the recursion by storing the Fibonacci numbers calculated so far.
This is a dynamic programming approach

#include<stdio.h>
 
int fib(int n)
{
  /* Declare an array to store fibonacci numbers. */
  int f[n+1];
  int i;
 
  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;
 
  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }
 
  return f[n];
}
 
int main ()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}

//Recursion

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

//Itterative code

public int fibo(int n)
{int a=1,b=1;
for(int i=2;i<=n;i++)
{
int c =a+b;
b=a;
a=c;
}
return c;
}

/**
     * Recursive O(n) method to calculate Fibonacci numbers
     * @pre n >= 1
     * @param fibCurrent The current Fibonacci number
     * @param fibPrevious The previous Fibonacci number
     * @param n The count of Fibonacci numbers left to calculate
     * @return The value of the Fibonacci number calculated so far
     */
    private static int fibo(int fibCurrent, int fibPrevious, int n) {
        if (n == 1) {
            return fibCurrent;
        } else {
            return fibo(fibCurrent + fibPrevious, fibCurrent, n - 1);
        }
    }
    /**
     * Wrapper method for calculating Fibonacci numbers
     * @pre n >= 1
     * @param n The position of the desired Fibonacci number
     * @return The value of the nth Fibonacci number
     */
    public static int fibonacciStart(int n) {
        if (n <= 0)
        {
            throw new IllegalArgumentException();
        }
        return fibo(1, 0, n);
    }
    public static int fibonacciIterative(int n)
    {
         int a = 1;
        int b = 1;
        int c = 0;
        for (int i = 2; i < n; i++) //i < n, not i <= n
        {
            c = a+b;
            b = a;
            a = c;
        }
        return c;
    }

Hi, what does WAP stand for? Thanks

cool

I think it would be better if you used dynamic programming for the recursive version. This kind of question is the kind of question where I believe they look at this optimization thingy, as the problem is otherwise quite simple:

int[] fib = new int[n];

	int fibonacci(int i){
		if(i==0) return 0;
		if(i==1) return 1;
		if(fib[i]!=0) return fib[i]; //you have to do this assuming you have all ints=0;
		//otherwise cache the result and replace the '0' with a fib value
		fib[i]= fibonacci(i-1) + fibonacci(i-2);
		return fib[i];
	}

First example how you will instantiate same variable in same method two times ..?