Why stackoverflow caused by recursion cannot be solved?

Question

Any recursion can be modified to be a iterative function with stack structure, then why do I ever want to do that? If the answer is to avoid stackoverflow, then how come computer can overflow by recursion at all? why not compiler automatically put a recursion function on a stack in heap by default or with an additional keyword? I understand heap is also limited, but it is much bigger than stack allocated to a program.

[Tail-recursive functions](http://stackoverflow.com/questions/33923/what-is-tail-recursion/33928#33928) can be re-written as iterative functions but many recursive functions are not tail-recursive. — Simon, Oct 23 '13 at 04:35
Every process has got 4GB of virtual memory on a 32 bit computer out of which 2GB is assigned to Operating System data structures. Hence the stack is limited in size and can overflow. — Tushar Jadhav, Oct 23 '13 at 04:39

score 0 · Answer 1 · answered Oct 23 '13 at 05:13

Activation records can indeed be heap allocated, but this is usually considered too expensive. Despite that there are a few implementations which take this approach: Stackless Python and SML/NJ, for instance.

In those cases the motivation is probably aiding the implementation of continuations, not "fixing" stack overflow.

score 0 · Answer 2 · edited May 23 '17 at 12:05

According to C/C++ maximum stack size of program and MSDN, the maximum stack size on Windows is 1 MiB. Your question is interesting. A keyword would certainly be possible and the compiler could do it. You need to ask compiler makers about it, but I guess it is not a very interesting feature.

Caching would be difficult because of other local variables lying on the stack and recursion book-keeping variables on the heap. Information is scattered around in memory.

Some recursive algorithms can be turned into truly iterative ones (like the calculation of the Factorial) or even into a closed-form expression (see for example the Fibonacci numbers). Then, there is no need for book-keeping of recursive calls.

The DEFAULT maximum stack is 1. (and VS!=windows) – Marco van de Voort Oct 23 '13 at 12:22 — Marco van de Voort, Oct 23 '13 at 12:22

score 0 · Answer 3 · answered Oct 23 '13 at 12:20

In an iterative process you keep track of recursion state yourself.

It is possible that you can do this more efficient then the compiler can with the very general procedural mechanism (whose efficiency can be hampered by all kinds of ABI concerns).

Stack checking is possible, but not easy on all systems, since not all systems employ a fixed stack or linear address space. It also has an overhead of course, since the check is added to each recursion.

Why stackoverflow caused by recursion cannot be solved?

3 Answers3