For Fibonacci, recursion is not the best or most efficient way to approach the problem, but I like using it as a recursion problem (artificially constrain the candidate to using recursion) because Fibonacci is so simple that you get to spend most of your time talking about recursion itself rather than talking about Fibonacci as a problem.

At least for this part of the interview, I'm not worried about your problem solving skills I'm worried about your programming fundamentals. We'll test problem solving in a different session.