It started, as these things do, at a kitchen table. My mother asked what I actually do all day, and I made the classic engineering mistake of answering honestly.
Recursion is a function that calls itself until it reaches a case simple enough to answer directly. That is the whole idea. The trouble is that every metaphor for it sounds like a symptom: a mirror facing a mirror, a dream inside a dream, a person who explains a thing by explaining the same thing slightly smaller.
What finally worked was food. Imagine a tray of pastel de feira. To count them, you take one off the tray and then count what is left. Eventually the tray is empty and you stop. That base case – the empty tray – is the part beginners forget, and it is exactly why their programs run forever.
She understood it in about forty seconds. Then she asked why anyone would write code that way instead of just counting the pastéis. Reader, I did not have a good answer.