I concur. My two favorite languages nowadays (Elixir and Clojure) are far from being purely functional. They are functional enough that mutating state is awkward, but if you do need it it is there.
I also think having immutable data structures by default is a saner choice IMO.
> It leads to recursion where iteration is more natural, awkward choices of data structures or even plain impossibility of certain algorithms/data structures
Anecdotal, but I rarely use recursion/for loops, opting for defining auxiliary functions that works in one element and using map/reduce instead. Really, I don't remember the last time I needed recursion to solve a problem (for example, I know recur exists in Clojure, but I never saw it in the code that I work everyday).