In a real functional programming language, we would instead create a new stack at every step,
This is only partially correct. Most functional languages use so-called "persistent" data structures that allow you to create a new data structure that reuses as much as it can of the prior data structure (the most common practical example is called "HAMTs" or "hash array-mapped tries").
A stack is an easy example to visualize. To push onto the stack, you'd create a new node (that's your current head), put your new value in that, and then say "the rest of the stack is..." pointing to the previous version of the stack. Popping off the stack simply discards these nodes.
Analogues exist for every major data structure.
That's true! It would be extremely space inefficient to create a copy of the entire data structure on every update. Unfortunately, that's exactly what I'm doing here :)