2

I wrote a user-programmable calculator, and now I'm hitting the following problem.

Let's say a user writes the following in it:

fun(n) = fun(n-1)

and then tries to call fun(42) (or whatever number). Now obviously, the user's code will cause infinite recursion, which in turn causes the whole calculator to crash with a stack overflow.

How could I make the calculator quit the calculation gracefully?

I have looked at how Mathematica handles similar situations, and it just bails out saying

$IterationLimit::itlim: Iteration limit of 4096 exceeded.

I have tried a similar approach, but then, as the stack size is OS-dependent, how do I know what number to use as the iteration limit (yes, I found a number that "seems to work" by experimentation, but that doesn't feel right)?

Thanks for your time. The core of the calculator is written in C.

Improve this question
1
  • 1
    If you write the calculator to not make recursive calls in the host itself -- e.g. handle the implementation via a stack yourself, then the limit is arbitrary based upon available memory that is/can be allocated (and some "sane depth") Commented Jan 25, 2011 at 0:12

3 Answers 3

Reset to default
4

This is simply one of the ugly little corners of C - there's just no portable way to know how much stack you can safely use. Technically, there doesn't even have to be enough stack to call a single function from main() - it's considered a quality-of-implementation issue.

The safest approach is to unroll your recursion so that it uses its own expression stack that you allocate with malloc(), rather than unbounded genuine recursion. That way you can bail out if malloc() returns NULL before you reach your application-defined recursion limit.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

+1 for unrolling the recursion, but if you do so, you should not include a recursion limit; just keep chugging along till malloc fails (or you finish, of course).
@David X: It might be considered antisocial to spend 30 minutes filling up all the available swap space and finally dying, just because the user gave you some bad input. The recursion limit is there to catch mistaken infinite recursion (do make it user-tweakable, though).
right you are, I was thinking hard-coded limit for some reason.
2

Instead of implementing user-level math function calls as C function calls, implement your own heap-based stack with malloc. This will give you a lot more levels of recursion and a way to tell reliably for failure.

Alternatively you could just put a reasonably small limit on levels of recursion.

Improve this answer

Comments

0

A quick hack is to just keep track of the recursion depth and exit if it is exceeded. A counter will suffice. You may need to reset the counter between each evaluation of course - but it is not as robust as running your own stack.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.