All recursion is iteration. Sometimes you have a stack to help you, and other times you get tail recursion optimization, but it's always a loop.

What makes you think so?

Please have a look at the formal definition of regular expressions at https://en.wikipedia.org/wiki/Regular_expression#Formal_defi... on Wikipedia, and let me know where the stack and the iterations are. I can't find them.

https://en.wikipedia.org/wiki/Recursive_definition#Well_form... is also a good example.

Regular expressions are a particularly interesting example because you brought up 'loops', so I'm assuming you are interested in how you can implement some of these recursive definitions on a computer.

So for regular expressions a common technique is to compile them to a finite state machine. You can model that in your computer as one block of eg assembly instruction per machine state. To move to a different state, you just 'jmp' to the corresponding code's address.

That's pretty fun to work out, but I still don't see anything I would describe as a 'loop' here; but the recursive analysis still makes perfect sense.

Yes, some programming languages have special purpose looping constructs. But they are of limited usefulness, and not particularly fundamental: they usually get compiled away.

all iterations are recursion but not the other way around.

When you add an explicit stack to help you keep state then you can have recursion be the same as iteration. Normally the stack you get in recursion is implicit rather than explicit.

A stack is one way to implement a specific kind of recursion on a computer.

But see https://news.ycombinator.com/item?id=42234121 for other examples of recursion.