What will happen if function goes out of stack space during infinite recursion?

Question

There is a function that calls itself recursively infinitely.

This function has some arguments too.

For every function call the arguments and return address are pushed on the stack .

For each process there is fixed size of stack space that cannot grow dynamically like heap. And I guess each thread also has its own stack.

Now if a function is called recursively infinitely and process runs out of stack space , what will happen?

Will program crash? Will OS handle the situation? There is 4GB of address space so why cannot OS do something to increase stack size.

Answer 1

The program will crash. Usually stack is limited by operating systems in order to trap bugs like this before they consume ALL available memory. On Linux at least the stack size can be changed by the user by issuing the limit command in shell.

Answer 2

For C++ at least, you will be in the realms of "undefined behaviour" - a bit like the Twilight Zone, anything could happen.

And if the recursion is infinite, what good will increasing the stack size do? Better to fail early than later.

Answer 3

stack overflow.

In UNIX and compatible the process will get terminated throwing SIGSEGV or SIGSTKFLT signal.

In Windows the process will get terminated throwing exception STATUS_STACK_OVERFLOW.

Answer 4

A typical Unix result will be a segmentation fault. Don't know about Windows.

Answer 5

What will happen?

Nothing that you should ever rely on.

Make sure your algorithms terminate. That's the only portable piece of advice here.

Answer 6

Depending on the language you will either get an exception (e.g. in Java) or the program will crash (in C, C++).

Typically the stack is relatively small, because that suffices, and a stack overflow signals an error. In Java you can increase the stack space with a command line option if you must.

Also note that functional languages typically compile tail recursion into a loop, and no stack space is used in that case.

Answer 7

Yes, your program will crash. There is no way for the OS to "handle the situation", other than preventing your buggy code from damaging other processes (which it is already doing). The OS has no way of knowing what it was you really wanted your program to do, rather than what you told it to do.

Answer 8

This isn't language-agnostic - it very much depends on the language/platform.

In C# (or any .NET language) you'll get a StackOverflowException, which as of .NET 2.0 cannot be caught and will bring down the process.

In Java (or any JVM language) you'll get a StackOverflowError (as specified here).

I'll leave it to other answers to deal with other languages and platforms :)

Answer 9

There are plenty of answers what will happen, but I want to mention the extremely easy solution:

Just by a turing machine and let your code run on that. It will have plenty of space.

Answer 10

Honestly, I don't know either. Let's find it out together, okay? I do it on my PC, you do it on yours. On three. So, one, two, three.... What have you got?