What You Need to Know to Work For Me
If you are ever interviewed by me and I happen to ask you, say, to write a function that returns the nth element in the Fibonacci Series, you had better not give me the recursive solution.
It appears that about 90% of the people asked this give this solution straight away, without asking the examiner anything about efficiency. I find this appalling.
Even if efficiency is not always the number one criteria (or even in the top 5), in this instance the recursive solution is much worse (exponential VS linear complexity) than the non-recursive solution AND is not much simpler to code. The difference is about 3 lines of code.
I expect programmers to anticipate and consider such concerns, and even if not asked specifically to give an efficient solution, in such a case they should (unless of course they ask the examiner if efficiency is a concern and get a negative answer).
P.S.
There are some acceptable recursive solutions. For example, from Wikipedia:
public void run(int n)
{
if (n <= 0)
{
return;
}
run(n,1,0);
}
private void run(int n, int eax, int ebx)
{
n–;
if (n == 0)
{
System.out.println(eax+ebx);
return;
}
run(n,ebx,eax+ebx);
}
I don’t object to the actual recursion, just to the exponential inefficiency.
