1. You switch to a pragmatic language that gives you an escape hatch to mutate data.

2. You use a persistent data structure that lets it grow without needing to make millions of copies for millions of new entries.

3. You use a different constructor pattern to avoid the allocations.

For (3), a common way around this (with lists) would be to build it in reverse and then reverse it (assuming that the order actually mattered at all, if it doesn't you don't need to reverse it at the end). This is done in Erlang, for instance, as a common pattern:

  make_something_n_times(0, Acc) -> reverse(acc);
  make_something_n_times(N, Acc) -> make_something_n_times(N-1, [f(N) | Acc]).

You end up with two copies of the list, one in the constructed order and the reverse ordered version, but the constructed order one will be garbage collected in short order. Two copies, better than millions of copies.

You also see a pragmatic solution in Erlang with iolists. These are lists that contain items that you'd want to send to, well, IO functions. But instead of forcing you to allocate whole new strings for concatenation (a common thing to do with strings) like this:

  S1 ++ S2 %% results in allocating a new string and copying contents from at least S1

You can do this:

  Concatenated = [S1,S2]

Now it's a two-element list that references the two prior ones, you've allocated some new memory, but just enough for a new list. Now you have a third string you want to prepend?

  [S3,Concatenated]

Again, minimal amount of allocation and copying (there is no copying). You can use this pattern in other situations and only flatten when needed, or "flatten" it by recursing over the structure to access all the elements but never actually constructing a flattened version.