If I was interviewing you (I've never interviewed anyone) and you gave that fibonacci algorithm, I would probably say, "Hmm, and how does that algorithm perform? Can you think of a better one?" If you said "its performance is crap, storing the previous two results and using iteration is better", I'd be happy. If you said "exponential" and "linear" instead of "crap" and "better" you'd get bonus points. Volunteering that information at the outset would get more bonus points because it shows that you really care and that you don't even feel comfortable writing down an exponential-time algorithm without loudly warning everybody they shouldn't use it.

The standard interview question is "write a function to solve this problem which has an elegant recursive solution", not "think of a recursive function". But if you do want to think of a recursive function, try factorial.

    int fctl(int n){ return ( (n = 1) ? n : n * fctl(n)); }

(Don't use that code in an interview. It's questionable style for C, and the ternary operator is scary to people.)

I was asked to write a fibonacci function once, and I actually said, "you can do this recursively but the performance is awful" and wrote an iterative solution.

The point of an interview is for you to show off. If you start going on and on and on and on about unnecessary details the interviewer might stop you, but if you launch into a talk about the space and time properties of recursion vs. iteration and show some judgment for how to use recursion and how not to use recursion, then I know how knowledgeable you are.

Dammit, I made a syntax error. The factorial function in C should be

    int fctl(int n){ return ( (n == 1) ? n : n * fctl(n)); }

(n-1) for the recursive call. God, I'm failing this interview.

Heh. Our actual interview question is similar but we ask them to add instead of multiply. We ask them to add up all positive whole numbers equal to or less than x. Good developers (who make it to the next round) bang out the answer in literally 30 seconds. Ok developers (who still make it to the next round) usually struggle for a while, maybe implementing it non-recursively first. The other 70% just type nonsense until I cut them off after 15 minutes.

If somebody makes a mistake I tell them and give them hints until they fix it. Well... it depends on the magnitude of the mistake I suppose. If they're not even in the right ballpark I keep my mouth shut.

Thanks for your considered and interesting reply. I agree that a discussion is much more informative (for both parties) than a rapid-reaction test, but with the rise of a speed-dating approach to business in recent years it's hard to know what people are looking for, sometimes.

Your better employers will thoughtfully talk with you though, and this is a good way for you to pick a good employer. That's an unseasonably optimistic attitude during this recession though.