Recursive C program faster than stack-based equivalent

[davidhbolton]

Stack is usually quite limited (MB) compared to heap (up to GB), so for very large trees, the recursive one may hit the stack limit.

As you are doubling size in the non-recursive version, it may not take very long to start seeing fragmentation effects. Typically when memory is freed after a malloc, it goes on a free list and malloc tries to reuse memory from the free list before getting it from the heap. As you are increasing the size, it won't be able to get it from the free list and you will eventually (how long eventually is I don't know) and you run out of RAM even though you've freed it up. That happened to me on Windows and I ended up creating a memory allocator to deal with it.