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.