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.

Around 2002, at work, I was involved in implementing support for Japanese character sets in an embedded library. A colleague from our Japanese office visited, and we worked together on it for about a week.

Before she left, she gave me a small present in thanks, labelled "Japanese Luck Bringer".

Two years later, it fell off a high shelf on to my head.

Bah, why isn't the 🔍 emoji at U+221B?

Sometimes the only hint you need to solve a puzzle is that it can be solved without a hint.

Last week a colleague and I were staring in puzzlement at something weird in a terminal window. After 30 seconds I said "Oh! I've worked out why that happens!". Five seconds later, she got it too, because _now_ she knew that it was possible to get the answer without going off to do an hour of research, and that narrowed the search space of what the answer could possibly be.

And this week, I was puzzled by a compiler error message referring to a particular C++ header, so I went and looked in (one implementation of) that header to see what it did. I found it did nothing interesting, or magic, or tied in to the internals of the compiler, at all. And that was enough to make me figure out what was going on with the error message – again, because there just weren't that many options left.

When it happens, it feels like one of those deliberate puzzles in which Paul says "Ah, now I know what the numbers are!" and Sophie replies "Ah, in that case, so do I!" Only somehow reality managed to create the same effect by accident.

If you think about it, heat is really *weird*.

Instead of regarding it as a first-class concept of physics, see it for what it is – a statistical aggregate of individual particle motions. And then consider the requirements of a life form:

You need raw materials of various kinds, to make more of yourself, and repair damage. You need to get rid of garbage from that construction. You need energy to power the work, and for auxiliary activities like moving around. You need an absence of various harmful substances and phenomena. All logical enough, from first principles.

But you also, for some reason, need constant gentle massaging by all the particles of whatever substances surround you. Not only that, but the vigour of the massage has to remain constantly within a narrow range. Too much, *or* too little, and the organism dies.

What?!