Back in the days when discussing the FizzBuzz problem of interviewing programmer job candidates, Dan Kegel had this to say:
Speaking on behalf of software engineers who have to interview prospective new hires, I can safely say that we're tired of talking to candidates who can't program their way out of a paper bag. If you can successfully write a loop that goes from 1 to 10 in every language on your resume, can do simple arithmetic without a calculator, and can use recursion to solve a real problem, you're already ahead of the pack!
My question is simple: What counts as "a real problem" one can solve with recursion that would be small enough to be a quick job interview question (like the FizzBuzz question)? I don't seem to run afoul of problems that call for recursion very often. When I do, it seems like it's always a "toy" problem like a Fibonacci number generator or factorial calculator.
I'm pretty sure I could solve a "real problem" using recursion, at that level of complexity at least, if I ever ran across one.