mutating the list here is not thead-safe.

If it is short (n is small) just recurse and build from the tail to head.  If n is long, use a ListBuffer (not currently thread-safe either) or ArrayBuffer (slightly slower, but not as much as you might expect).  The same pattern multiple places here.

This would bring us closer to avoiding all mutation in List, which would bring other performance benefits.