Post #4275918

2026-07-31 10:50 UTC

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.

Replies (2)

@barubary@infosec.exchange 2026-07-31 10:55

@simontatham@hachyderm.io I've had similar thoughts. I think recursive algorithms come most naturally when you have a recursive problem/data structure, like a tree. So I think good introductory examples would be recursively searching a directory for all .png files or eval'ing an expression tree in a calculator.

Open ##4275915
@simontatham@hachyderm.io 2026-07-31 10:50

The best example I've ever managed to come up with is the search problem in the game of Boggle: find a path through a grid of letters, never revisiting a square, that spells out a word. You can simplify the problem by giving a _specific_ word as input rather than a whole dictionary: "is there any path in this grid that spells BANANA?" It's a bit awkward because "never revisit a square" means you have to maintain a set of disallowed squares, either passing a modified copy to each recursive call or modifying a single copy in place. But unfortunately that property is also what makes the problem need recursion in the first place: if you take away that rule, it becomes a much simpler BFS problem – in particular, polynomial time, whereas the proper Boggle search problem is NP-complete. Boggle is in my second category: it's not _impossible_ to solve it non-recursively, but the most obvious alternative technique is breadth-first search, and the "never revisit a square" rule means each entry in the BFS queue has to contain a set of squares, so that lots of queue entries can share the same (grid square, position in word) values and still need to be kept separate. So you can see that there's a memory-use disadvantage: the recursive solution considers all the same cases, but keeps far fewer of them in memory at a time.

Open ##4332492