Interview Coding Question - Fibonacci

Fibonacci number

Recursive solution

int fib(int n)

{

  if (n < 2)

    return n;

  else

    return fib(n-1) + fib(n-2);

}

Iterative solution 1

int fib(int n)

{

int fibArray [MAXINT], i;

fibArray [0] = 0; fibArray [1] = 1;

for (i = 2; i <= n; i++)

    fibArray [i] = fibArray [i-1] + fibArray [i-2];

return fibArray [n];

}

Iterative solution 2

int fib(int n)

{

  int first = 0, second = 1;

  int i, tempSum;

  for(i = 2; i <= n; i++)

  {

    tempSum = first + second;

    first = second;

    second = tempSum;

  }

  return second;

}