CareerCup

// Recursive approach. Not efficient

public int fibonacci( int num ) {
return (num <= 1) ? num : fibonacci(num - 1) + fibonacci(num - 2);
}

// More efficient iterative approach
public int fibonacci( int num ) {
if( num == 0 ) return 0;
long[] fib = new long[num + 1];
fib[0] = 0;
fib[1] = 1;
for( int i = 2; i <= num; i++ ) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[num];
}

Jimmy Jose, your method are not efficient at all.
Equation F(n) = F(n - 1) + F(n - 2) - looks pretty much like recursion, but in this case you shouldn't use recursion. That's the whole point.

int fibonacci(int N) 
{
	int first = 0;
	int second = 1;
	
	if(N <= 1) { return first; }
	
	int i = 1;
	int current = second;
	while(++i < N) {
		current = first + second;
		first = second;
		second = current;
	}
	return current;
}

To find the nth Fibonacci number, use the following recursive definition :

* F0 = 0
* F1 = 1
* When n is an even number :
Fn = Fn / 2(Fn / 2 + 2 F(n－2) / 2)
* When n, modulo 4, is 1 :
Fn = (2 F(n－1) / 2 + F(n－3) / 2)(2 F(n－1) / 2 － F(n－3) / 2) + 2
* When n, modulo 4, is 3 :
Fn = (2 F(n－1) / 2 + F(n－3) / 2)(2 F(n－1) / 2 － F(n－3) / 2) － 2

Thanks
Ankush

Public int fib(int n)
{
	If(n<=2)
	{
		Return 1;
	}
	Else
	{
		Return fib(n-1) + fib(n-2);
	}
}