Possible recursion problem

Larry C. · 2018-03-10 17:24

I'm outlining a SPIN application and I'm concerned about setting up a recursive situation that will overflow the call stack.

Briefly, I want to do this:

repeat
Call Method A

Call Method B

Call Method C
IF an anomaly occurs here, handle it
Call Method A
Call Method D

Call Method E

This will run every ten minutes indefinitely. Method C could see some anomalous data once every 3-4 days. What I'm worried about it is the call stack overflowing after many months and crashing the program.

I would appreciate anyone's thoughts on this. Do I need to be concerned? How can I prevent this problem? Seems to me an ABORT with an abort trap could be used to clear out the stack, but I'm not sure about this.

Thanks,

Phil Pilgrim (PhiPi) · 2018-03-10 17:32

I don't see a recursive structure there, unless your methods also call each other. When your methods return, the only thing left on their local stacks are the return values. And those get cleared by the calling routine.

Maybe if you post your actual code, something else will manifest that your outline obscures.

-Phil

Larry C. · 2018-03-10 18:06

My example was misleading! Yes, I intend the methods to call each other. Method A calls Method B, which calls C, etc. Hence my concern about recursion.

I haven't written the code yet, so I can't post anything. Just want to know if this is a viable approach, or will this come back to bite me down the line?

- Larry -

Phil Pilgrim (PhiPi) · 2018-03-10 18:40

Recursion would occur if A calls B, which calls C, which calls A. I don't see that in your statement. And, yes, you can use an abort in method C to return. Or you could just return a unique value indicating the anomalous data reception.

-Phil

Larry C. · 2018-03-10 21:23

Yup. The scenario you lay out is what I had in mind: A calls B, B calls C and C calls A if it sees an anomaly, otherwise C proceeds normally and calls D, which calls E and returns to the start of the repeat loop.

You're suggesting I could use an ABORT to handle the anomaly. I assume this would require an abort trap in Method A. Am I right on this? And is this the approved means of dealing with this recursion so it doesn't endlessly add to the call stack?

-Larry-

Heater. · 2018-03-10 21:48

You don't need any ABORT. Just make sure your stack is big enough.

There is nothing special about recursion, over regular nested calls.

Just be sure your base case is reached before the stack runs out.

Phil Pilgrim (PhiPi) · 2018-03-10 22:33

Yes, you do need the abort if you can't unwind the stack by a sequence of returns. Recursion only works when the stack doesn't increase ad infinitum.

-Phil

Heater. · 2018-03-11 05:55

Exactly my point.

There can be no ad infinitum in a finite machine. So don't write code as if there is an infinite stack. If your recursion runs out of stack before reaching the base case then it's a bug. Fix it.

Philosophically I think think things like exceptions (C++) and ABORTs (Spin) should only be used for, well, exceptional circumstances that are unexpected and out of the programmers control. Like hardware errors. Running off the end of a tiny stack when recursing is not exceptional or unexpected or out of the programmers control.

The common advice is: Exceptions should not be used for normal control flow.

Larry C. · 2018-03-11 20:41

Heater, thanks for chiming in. I have done some SPIN programming, but this is an area where I'm lost, so I appreciate seeing your views. I'll try to find an alternative approach to using ABORT.

But now I'm curious. What's your objection to the ABORT function? Since it's been built in to the Propeller system and if it's suited to fixing the problem (as it seems to be, in my case), why not just use it?
- Larry -

Phil Pilgrim (PhiPi) · 2018-03-11 21:46

heater wrote:

Philosophically I think think things like exceptions (C++) and ABORTs (Spin) should only be used for, well, exceptional circumstances that are unexpected and out of the programmers control. Like hardware errors. Running off the end of a tiny stack when recursing is not exceptional or unexpected or out of the programmers control.

The OP's exceptional condition is bad data from an external device, not a stack overflow.

There's no reason not to use an abort, Larry. It seems perfect for your application.

-Phil

Heater. · 2018-03-11 22:10

I don't have particularly strong objections to using ABORT in this case.

What do we actually need here?

Whilst someFunc() is calling someFunc() is calling someFunc() .... either directly or indirectly you need to either:

a) Be sure that the base case will always be reached before the stack runs out.

or

b) Add some code to someFunc() check for stack usage before calling someFunc() again. Then:

1) Return some kind of error indication if there is not enough stack left.

or

2) ABORT.

You are going to need to do a) or b) whatever.

So it's a toss up between returning some error indication or using ABORT.

My slight philosophical objection to using ABORT is that you know how much stack you have, you know what recursion could be going on, and therefore running out of stack is not an unexpected, exceptional circumstance. It's likely normal program behavior. As such it does not feel right to be using a mechanism designed for exceptions.

Up to you to judge.

Larry C. · 2018-03-11 23:08

My slight philosophical objection to using ABORT is that you know how much stack you have, you know what recursion could be going on, and therefore running out of stack is not an unexpected, exceptional circumstance. It's likely normal program behavior. As such it does not feel right to be using a mechanism designed for exceptions.

I'm really missing something, here. How can I know how much space is available for the call stack?

Phil Pilgrim (PhiPi) · 2018-03-11 23:19

Or 3) avoid recursion and the need to check stack usage altogether. Just back out of C all that way back to A instead of calling A from C. That's what the abort will do for you.

-Phil

localroger · 2018-03-12 00:08

You can use a global variable, say c_depth, to keep track of recursion depth. Set to zero on initial call and increment and check value when the recursive routine is called. If c_depth gets too high use abort or some other mechanism to back out. Sometimes, particularly when things are driven by unpredictable user inputs, this is the only way to reliably prevent a crash.

Phil Pilgrim (PhiPi) · 2018-03-12 03:00

Seriously, guys, this app does not call for recursion, and it would be a mistake to structure the program that way.

-Phil

Heater. · 2018-03-12 07:08

@Larry C.

I'm really missing something, here. How can I know how much space is available for the call stack?

You don't. There is nothing in the language to tell you that easily.

When a method is called we can gustimate stack usage. The return address will need to be saved on the stack (1 LONG), all the parameters will need to pushed to the stack for use by the callee (Say 1 LONG each), any local variables in the callee will be on the stack (say 1 LONG each). Add all this up for every method called along the "call chain" and you can estimate the stack usage.

There are more accurate ways to determine stack usage. I won't go into them here.

@Phil,

Seriously, guys, this app does not call for recursion, and it would be a mistake to structure the program that way.

That is almost certainly true. We don't know for sure as Larry C. as has not said exactly what he is wanting to do.

So...

@Larry C.

What are you actually building there? Does it really need recursive calls at all?

idbruce · 2018-03-12 17:26

The common advice is: Exceptions should not be used for normal control flow.

Exceptions should only be used for abnormal flow control. If the pipe is clogged, use a plunger.

EDIT: Seriously... Slightly interesting discussion

idbruce · 2018-03-12 17:38

After reviewing this thread...

Heater offered some good advice....

There can be no ad infinitum in a finite machine. So don't write code as if there is an infinite stack. If your recursion runs out of stack before reaching the base case then it's a bug. Fix it.

EDIT: An ABORT might be a simple solution to exit.

Larry C. · 2018-03-12 18:27

@Heater
@Phil
et. al.

The project is intended to measure several wavelengths of solar ultraviolet radiation, weight the readings as required, subtract white light intensity, compute the ultraviolet index (UVI) and display a moving 24 hour chunk of data.

Someone else is supplying the sensor package, which is still kinda flaky and occasionally (every few days) spits out bad data. I could develop my portion until a better sensor design comes along by ignoring faulty data samples, and it seemed to me that ABORTing my way out of it was the easiest approach. But, I'm sure there are other approaches -- involving flagging bad samples and post-processing, for instance. As I said earlier, I'm just in the block-diagramming stage right now, and trying to anticipate problems, so I can't be more specific.

I enjoyed being in on this discussion and I have learned a bit here, so ..... thank you, all.

Cheers,

- Larry -

Heater. · 2018-03-12 18:45

Larry C,

Sounds like an interesting project.

From the way you describe it I might agree that ABORT is the best thing to do.

Those bad samples are something you can no longer process as they are meaningless. And they are not under your programs control.

They are exactly the kind of case I suggested ABORT, or exceptions in general, are suitable for.

Given input that makes no sense why not just use ABORT to bail out of everything and start afresh?

Possible recursion problem

Comments