> Isn't mutable variables the most obvious way to solve these problems?

Yes, but the mutation can be entirely limited to the reference. The data structures do not have to be mutable. It's a trade-off, of course, because you can't pass somebody just part of a data structure (like a sub-map) and have them mutate it there, but I think Clojure has shown that in practice this isn't really much of a loss.