I was writing code to solve a problem and it worked with a small input, however when increasing to a larger input I got a stack overflow exception:
Stack overflow.
Repeat 3239 times:
--------------------------------
at Program+<>c__DisplayClass0_0.<<Main>$>g__Traverse|3(Point, Direction)
--------------------------------
at Program.<<Main>$>g__Do|0_0()
I also noticed that the number of times it claims to repeat varies between executions, sometimes I'd get ~2300 repeats or ~2800 repeats too.
After a while of debugging I could not find anything wrong with my code so I manually set the stack size of the thread to Int32.MaxValue and the code worked and produced the correct answer.
I am curious if anyone knows how C# goes about detecting a stack overflow? In this case, it seems to me that C# was prematurely predicting a stack overflow even though the program does terminate given the chance to.
Additionally, why would C# give a stack overflow error saying a call was repeated x times where x seems to vary each execution?
Any insights or information is appreciated!
The stack is a contiguous chunk of memory† (of a defined and finite size) that is consumed (and usually released again promptly) by various operations including allocation of locals and transients, "stackalloc" buffers, etc. Recursive calls usually leave everything existing in place and allocate more data in the next space down, hence deeply recursive operations are prone to using large amounts of stack space.
There is no "prediction" going on here; you simply hit the end of the chunk of memory. This is not meant to happen, and means that your approach is doomed - usually: too recursive. It isn't usually important to guarantee that the stack will bottom out at exactly the same place every time, since you're already in a doomed scenario. That's like saying that an engine should blow up at exactly 87432rpm each time. A few minor variations might impact the exact space available or the exact space used in individual stack-frames, but overall: that doesn't matter, you've still used the wrong approach.
It might be nice if C# was better at tail-call recursion (which eliminates need to keep old frames), but without code we can't even see if your code is a candidate for tail-call.
If you have a deeply recursive scenario, you can usually work around the limits of the stack by moving the recursion off the stack. Usually this means using a Queue<T> or Stack<T> to hold your logical state, add the seed value to it, and then a simple while loop (while not empty) that takes the next value, does some thinking, and optionally adds some value or values back to be processed.
† virtual memory; chunks of which may or may not yet be mapped to real memory, but that doesn't matter