Journal: Multithreading and recursion cannot be mixed in C?!

I just learned that you cannot safely mix recursion and multithreading when writing C programs. Here's why:

Most decent C compilers will attempt to do tail recursion elimination, although it is not required the way it is in Scheme. However, there are plenty of recursive algorithms, especially those which deal with trees, which are not tail recursive, and therefore will require the use of the stack.

Due to performance considerations, the C stack must be contiguous; it cannot be broken up into dynamically allocated chunks. If this was not the case, every non-local variable access, not to mention every call and every return, would require extra comparisons. Thus standard compilers keep it contiguous.

Now in the old, single-threaded world, you have only one stack per process. It starts at one end of the total virtual address space, the heap starts at the other end, and they grow towards one another. When they meet, which does not necessarily have to be in the exact middle, you've run out of memory, and no amount of paging will help (after all, this is the virtual address space we're talking about, not the physical one); refine your algorithm, or go out and buy a 64-bit machine.

In the new, multithreaded world, each thread needs to have its own stack. Because each one must be contiguous, and there are only two total "ends" of the linear virtual address space, there is no way to lay it out such that the stacks grow freely until the virtual address space is exhausted. Instead, at thread-creation time, you pre-allocate a certain size stack, and that's all you get for it, even if much of the address space is still free. Thus, because recursive algorithms make heavy use of the stack, they cannot be used on the tiny, artificially limited stacks of the multithreaded world.

What I wonder is if anybody has ever tried to write a preprocessor for C in which you could mark certain functions as recursive (or auto-detect it if you're feeling clever), and replace the use of the real stack with a heap-based, dynamically grown stack. You wouldn't want to do this for all functions, since it would inherently be less efficient, but it would remove the necessity of contiguous stacks and therefore solve the problem. I don't know if I have the patience to write this myself; one side of me appreciates the challenge, but another side says that there are lots of nice languages, Scheme and Java prominent among them, which don't require contiguous stacks, and are very happy mixing recursion and multithreading.