Here's a neat test of programming language expressiveness: Can you write a function PrintXY taking an integer n>=0 that prints all strings of length n containing only the characters 'X' and 'Y'? Can you do it without recursion, and without assuming n<=64? Is it readable?

About two years into Apple BASIC programming, I was befuddled by this. I only knew loops and not recursion, so I wanted to write an outer loop that maintained a variable number of inner loops, but that wasn't supported:

Because BASIC supported GOSUB recursion only, without a parameter stack, I eventually abandoned it in frustration and wrote a compiler for a Pascal style language. The recursive solution is easy, but the question still stands: why are for-loops too weak to express this?

A Haskell programmer will use some higher-order library functions to build a list comprehension over a variable number of permutations, but that's tricky and just moves the recursion to a library function.

There's actually a deep answer to this: looping over just mutable loop variables isn't very powerful. A set of n simple nested loops of k iterations each can only explore k^n possibilities, and n must be static. We can't handle n being a variable.

This is another area where the functional logic language family is more powerful. There, we can loop over multi-valued choices (like little forks whose scope is limited to the enclosing loop) and gather all of their results in sequence through backtracking.

Here, let "a..b" represent the choice of all values in the range from a to b, and "for(a) do b" loop over all choices in a, producing an array containing the values of b. Then we can write a simple loop like:

New expressive power comes from our ability to nest choices inside of loops, where each iteration explores all choices. Then we can variably "exponentiate", and write PrintXY as:

Is this a quirky, special-case language feature? Definitely not; it has well-defined semantics and increases the expressive power of loops. And it's what 14-year-old me intuitively tried to do in Apple BASIC.

There are many interesting solutions in this thread. The C and JavaScript solutions seen akin to mechanical devices that crank out solutions. One is an astonishingly short Haskell composition of library functions: https://twitter.com/tikhonjelvis/status/1265453175219183616?s=20

There is generally a barrier to reading these solutions. In one case you have to run through the behavior of imperative code in your head to understand what it does. In another you have to understand the near magical incantation of pointfree function compositions.

The more a solution can resemble a simple recitation of the problem to be solved, and rely on the compiler to generate the code, the better for ease of reading and writing code.