I got into an argument with someone regarding an interview question. The question is “write a function to print out the fibonacci sequence”, and then the person went on a rant about someone they interviewed who solved the problem but didn’t use recursion. His argument is that using recursion showed a bit more “programming prowess”, but the problem I see is that with a recursive solution you end up recomputing terms you have already computed (This iteration’s (n-1) is the prior iterations (n-2). In addition, with a recursive solution you have to give an upper bound to the series.
In my mind, a simpler solution would go something like this:
int main() {
unsigned int current = 0;
unsigned int previous = 1;
while(1) {
unsigned int new = current + previous;
printf("%i ", current);
previous = current;
current = new;
}
}
Voila, problem solved without inane stack growth. There are possibly other (even “better”) non-recursive solutions to this problem, but in my opinion, this would be a “good enough” answer if I was interviewing someone. Of course, I rarely am interested in making people write code on whiteboards in interviews, so I probably wouldn’t ask it in the first place, but that’s a different story. This argument reminds me of one awhile back where someone was arguing that you don’t always need to use the bounded string functions in C because sometimes you “know how much space you need”.
P.S. I do realize that without a ceiling on the calculation I will eventually roll the int over, but that’s tangential
P.P.S. Of course using new
as a variable name was a bad choice (since it is also a C++ keyword), but again, that is tangential, so stop whining at me about it.