Walh Hara posted:

Ha, fair point, my example is wrong (but my claim that there are ways to calculate fibonacci in linear time is not). Either way I was just pointing out that when people say "solve fibo with recursion" you do not necessarily have to answer with fibo(n) = fibo(n-1) + fibo(n-2). Whether you use recursion or iteration shouldn't really change the time complexity (big O) of the optimal solution of any problem if you know what you're doing.

That said, if I went to a job interview and somebody asked me the fibonacci question I'd be quite offended so I agree it's a silly interview problem.