At 1,000,000 items you have 20 (in the best case, at least) levels of recursion. I can assure you, your stack space is more than sufficient for that.

Also, you only have to push a handful of pointers to the stack, which doesn't seem to be expensive to me.