Exceeding stack space during recursion

Question

I am running a recursive function in MATLAB and gets this error message:

"Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N) to change the limit. Be aware that exceeding your available stack space can crash MATLAB and/or your computer."

I wonder, can it really happen that MATLAB and/or my computer can crash if I change the recursion limit and exceed my stack space? It seems strage to me. Why doesn't MATLAB just halt and quit automatically if the available stack space is exceeded?

And how do I know how big recursion limit I can choose without danger?

Answer 1

The computer isn't going to crash. Matlab might, that depends on their handling of the stack. The warning is there most likely because Matlab is multi-platform, and it can run on many different OSes and architectures, some of which might not be as safe as Windows or most POSIXes.

In practice, when working with a thread stack on a Windows machine, the "stack overflow" error is actually "access violation" - you try to access memory that doesn't belong to you not actually an access violation (instead, it's a special kind of page fault, basically), but the idea is similar - the OS notifies you first that you're reaching the ceiling of the stack, and if you exceed the last few "safety" pages, it will give you the actual stack overflow. This is very handy, since it's "free" - you don't have to check if you still have stack space every time you push, and it gives you some extra safety.

Depending on how Matlab handles that exception, it might gracefuly report an error and continue, or it might crash.

Of course, handling stack overflows can be quite tricky, but not for the OS. Windows can handle those errors just fine, it doesn't really care.

The recursion limit depends a lot on how much data Matlab actually has to store in each step of the recursion. The typical stack size of a Windows thread is about 256-1024 kiB (and it's configurable for threads you start on your own), which is actually quite a lot, unless you're passing a lot of big arguments. Consider that with a method that takes two integers and doesn't have any variables, you'd need about 20 000 call deep recursion to exceed even the 256 kiB stack space (on 32-bit).

However, stack overflows are usually a problem in code. You most often run into them by choosing the wrong recursion exit condition. That's part of the reason why the stack overflow is handled by an "exception", rather than allocating more memory for the stack - every trivial recursion error would start crashing all your applications and possibly even the OS. So, first make sure that you actually need a recursion that deep :)

Answer 2

Actually here is a very similar question presented by Mathworks.

Here is how they say you can produce a recursion problem, I think it had 32 bit in mind so you may need to increase the 5000:

create the following file:

function retVal = myrecursivefun(inVal, recursions)
recursions = recursions - 1;
inVal = inVal + 1;

if recursions > 0
retVal = myrecursivefun(inVal, recursions);
else
retVal = inVal;
end

Then run it as follows to crash MATLAB:

set(0,'RecursionLimit', 5000);
myrecursivefun(1, 5000);

---

Personal note: I think the default recursion limit of 500 makes sense. Matlab programmers won't often want to go beyond this and most of the time this limit is hit because of a mistake.

Also, I think matlab has a little more overhead for function calls than low level languages like C++, therefore you will usually want to avoid deep recursion in the first place.