Saying "use immutable data structures" here assumes garbage collection though.

If you didn't have garbage collection, when would you release the memory for these structures? That would bring you back to refcounting.