Recursion has nothing to do with stack traces. Stack are one way to implement some version of recursion in functions.

Some other versions of recursion in functions can be implemented with loops.

And, of course, not only function can be recursive, but data structures as well. (And a few other things.) You can traverse these data structures any way you feel like.

> It's difficult to debug and follow the code around, or even to understand the code if someone else wrote it.

I have that problem with loops (and mutation) much more than with recursion. Different things make different people's heads hurt.

> Also recursive functions tend to spiral out of control and have ridiculous exponential run times.

Oh, that's an artifact of how you've been taught (or self-taught). Loops are a special case that only works well for simple tasks. Recursion is more general and can express the simple case in a simple way.

Of course, if you only reach for recursion in the complicated cases, all uses of recursion you see will be complicated. Simple observation bias.