Post #4332492

2026-07-31 10:50 UTC

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.

Replies (1)

@simontatham@hachyderm.io 2026-08-01 09:41

I wonder, actually, if the _very simplest_ problem that demands recursion is just generating a Cartesian product of variable arity. If I have a function taking 3 arguments, each taken from a finite set, and I want to call it with all possible combinations of arguments, then I can write three nested for loops: for a in values: for b in values: for c in values: f(a, b, c) But this only works if the number of arguments is known at the time I write the code. If f takes a single list argument instead of three separate values, and I need to specify the length of the list at run time, then the only sensible thing to do is write a recursive function, containing _one_ of those for loops; give it a parameter to control the recursion depth, and at the deepest level it calls f with the list it built up. Of course you _can_ write some fiddly loop that iterates on a partial list, sometimes appending a new item and sometimes deleting the last one, calling f whenever the list gets full and terminating when it becomes empty. But that's in the category of "simulate recursion in a way that's less obvious than just doing the recursion". And you _could_ do breadth-first search, keeping a queue of partial lists. But then your memory usage becomes Θ(2^n) instead of Θ(n).

Open ##4332493