Post #4332493

2026-08-01 09:41 UTC

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).

Replies (3)

@ireneista@adhd.irenes.space 2026-08-01 09:46

@simontatham@hachyderm.io the situation where we use recursion the most personally is traversing an AST. maybe that could work as an example?

Open ##4332495
@slava@mathstodon.xyz 2026-08-01 09:56

@simontatham@hachyderm.io “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.” An n-tuple with elements drawn from a finite set of k elements is just a base-k integer with n digits, isn’t it? So an easy way to generate all such n-tuples is to start with the first such tuple and repeatedly increment it by one until you carry the last digit. Seems a bit simpler than recursion

Open ##4332498
@darkling@mstdn.social 2026-08-01 10:19

@simontatham@hachyderm.io You can do this simply and non-recursively with something like: result = values[0] for v in values[1:]: result = cross_product(result, v) def cross_product(xs, ys): result=[] for x in xs: for y in ys: result.append(x+[y]) return result But the recursive version is probably a bit more obvious.

Open ##4332499