Functional programming doesn't have to mean deep recursion-- it's not like you can't use functions and loops in the same code.
It's like with lazy evaluation. It allows you to write novel kinds of algorithms and data structures, and you can emulate it with helper objects or structures, but it's tedious, muddles the essence of the code, and the implementation without them (the helper structures) would be simpler if the language provided you with lazy expressions.
In other words, repeat with me: loops don't compose. They're not first-class, they're not extensible, they're a syntactic construct.
Iterators do, though. Most of the languages that don't do TCO instead lean on those instead: C++, C#, Python, and eventually JavaScript.