Detect stack full for recursive routine

[david_navigator 12]

I have some inherited code that does some complex maths using a recursive function (i.e the function calls itself). Last night a customer had a situation where running the routine killed the app. My belief is that the app ran out of stack space due to this routine calling itself multiple times and thus died.

Is there anyway to detect this is likely to happen so that the code can be aborted with a message instead?

 

David 

[PeterBelow 218]

3 hours ago, david_navigator said:

I have some inherited code that does some complex maths using a recursive function (i.e the function calls itself). Last night a customer had a situation where running the routine killed the app. My belief is that the app ran out of stack space due to this routine calling itself multiple times and thus died.

Is there anyway to detect this is likely to happen so that the code can be aborted with a message instead?

 

David 

There is a EStackoverflow exception type defined in System.Sysutils but it has been deprecated for several Delphi versions. A stack overflow cannot be trapped reliably via try except and recovering from it is practically impossible. What you can do, however, is to increase the stack size used by the program (in the linker part of the program options). Of course that is a band aid that does not protect from future failures due to an even more pathological set of input data.

 

You can look into rewriting the algorithm to avoid recursion. Intead of relying on local variables to hold intermediate results (i.e. store them on the stack) you store this data into a record and manage a stack of these records yourself. This gives you much more control over the memory used, as well as removing the hard limit imposed by the default stack size.

[david_navigator 12]

Thanks. This is the first time it's fallen over in 20 years so not too concerned. I just wondered if there was a call like "is there enough stack space left for me to call this routine again" kind of thing.

[Brian Evans 83]

Raymond Chen blogged about this a few years ago: Determining approximately how much stack space is available, part 2 - The Old New Thing (microsoft.com)

Edited July 29, 2023 by Brian Evans

[Fr0sT.Brutal 897]

You can setup counter and check it. The catch is that you never know how much space is occupied on the stack by single call. First I'd add logging of enters and leaves to that function and see whether it is really the source of problems. Then you'd have to decide whether this consumption is acceptable by algo (like matrix reverse - big matrix means big nesting, that's not an issue in algo but in input) or it's a algo's flaw (endless/excess recursion). In the former case you can try to optimize the code. Remember any local variable eats stack - probably you can reduce their number by using heap or object fields. Function parameters, if there's many of them, also consume stack so you can unite them into a record (but store it in heap otherwise it eats stack of the caller).

Edited August 7, 2023 by Fr0sT.Brutal

[pmcgee 10]

@david_navigator no-one mentioned that 
a) if you can arrange for calculation by tail-calls, Delphi can eliminate runaway stack increases.
b) there are techniques to linearise some recursive functions by decomposing the single function into multiple functions with extra state.
c) it may be possible to memoise calculations that might be repeated.