I was rejected, by my own best friend, a man I would call “brother” (if we were related), for a job today.
Here’s the interview question posed:
1) The Fibonacci sequence is a well-known sequence of numbers which occurs frequently in natural processes. It is defined thus;
Fib = 1
Fib = 1
when n>2, Fib[n] = Fib[n-1]+Fib[n-2]
i.e., each term in the sequence is the sum of the previous two terms; and so the sequence starts 1, 1, 2, 3, 5, 8, 13, 21…
a) On the whiteboard, in whatever language you like (or pseudo code), write a recursive function to return the nth term in the sequence.
b) Write an iterative function to return the nth term in the sequence.
Can you say anything about the comparative speed / memory usage of each version?
I’d just like to say that the recursive code I’d write would be tremendously slow when compared with the iterative version. But this is expected and whilst the code would look nicer, we should not, even in these days of incredible computing power, reject the more efficient iterative code simply because we like a tidy bush.
So do I get the job?
Purely for the use of the phrase “tidy bush”? Err, no, ‘fraid not.