It's a bunch of trees. You end up only copying the spine (from modified leaf to root). containers & unordered-containers are the popular packages.

It's also pretty common to still use mutability (the vector package in Haskell is hugely popular) but it tends to be principled and/or abstracted out because its use is explicitly tagged in type signatures. And those APIs can get even better once LinearTypes land.

In gamedev, both can be useful. Vector is useful for performance and GC relief (when Storable/Unboxed). Immutable structures are still useful when backtracking is needed since they make it trivial and performant in that setting. A useful property for debugging, "training mode", replays, netcode etc.

Recursion is used but not necessarily self tail recursion thanks to general TCE.