[jarcane]

Yes. Fundamentally, the problem is cultural, not mathematical. A modern language like Racket with proper recursion optimizations will compile and optimize a recursive solution that is as fast or nearly (and even sometimes faster) than a mutable imperative one.

The problem is that the idea of recursion as slow or resource hungry has become a kind of circular just-so story among imperative programmers and compiler developers who don't want to write recursion optimizations (or don't even know how).

The argument goes that recursion is slow, so don't use recursion, and if you raise the idea of optimizing recursion, the compiler dev dismisses it, because why would you write recursion support, recursion is slow.

Now it's fair to say in an earlier era, this was somewhat justifiable, but the logic has been passed down far longer than it's actually been true of the technology available. I remember reading "recursion bad" in C books in the 90s, and it's still so pervasive that even though TCO has been in the JS standard since ES6 years ago, most browsers still can't be bothered to support it.