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

Question

sanji · Accepted 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.

SlzP · 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

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas