What's a _good_ example, for teaching recursion to a novice programmer?

I think a common mistake is to use a too-easy introductory problem, which you can solve easily without recursion. Like calculating a factorial, or a Fibonacci number. The student already knows a way to do that, and the recursive implementation is more confusing than the code they already had. So they get the impression that recursion is a way to make your life unnecessarily extra difficult.

To _motivate_ recursion – to convince the student that it's important and worth learning – you want an example where the problem really _needs_ recursion.

(That's never _literally_ true, because you can always write things another way _somehow_; but if the other way involves an explicit stack simulating the same recursion, and a loop in which each iteration might either increment or decrement the stack pointer, the student probably won't see it as more natural or more readable!)

Or, if there _is_ a solution that has nothing to do with recursion, it should have an obvious disadvantage of some kind, so that the student can easily see why you wouldn't want to do it that way. Like using a huge amount more memory.