Write code for Fibonacci algorithm (iterative or recursive) and explain what's the performance.

Question

SlzP · Accepted Answer

When using recursive method, one way to improve performance is to store the computed values in a global array.
ex: To calculate Fib(5), we calculate Fib(4) + Fib(3) 
Now Fib(4) again calculates Fib(3) & Fib(2) which is repeating the calculations

For large values of n, this leads to too many recursive calls. So, as and when we calculate Fib(k) we can store the value in a global array and reuse it to improve performance.

leo · Answer

sanji · Answer

Recursive:
void fib(int k)
{
	if(k==0)
		return 0;
	if(k==1)
		return 1;
	return fib(k-1)+fib(k-2);
}

Iterative:
void fib(int k)
{
	if(k==0)
		return 0;
	if(k==1)
		return 1;
	int pre2Term =0;
	int preTerm =1;
	int retVal = 0;
	for(int i=2 ; i<=k;i++)
	{
		retVal += preTerm + pre2Term;
		pre2Term = preTerm;
		preTerm = retVal;
}
return retVal;
}

Test:
fibTest()
{
	int testInt = 3;
	print(fib(testInt));
}

Iterative version of course has better performance because it doesn't need multiple function calls and program stacks to save variables.

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois