Предотвращение переполнения стека / бесконечной рекурсии в программируемом пользователем калькуляторе

Question

Я написал программируемый пользователем калькулятор и теперь сталкиваюсь со следующей проблемой.

Допустим, пользователь пишет в нем следующее:

fun(n) = fun(n-1)

, а затем пытается позвонить fun(42) (или любой другой номер). Теперь очевидно, что код пользователя вызовет бесконечную рекурсию, что, в свою очередь, приведет к краху всего калькулятора с переполнением стека.

Как я могу заставить калькулятор корректно выйти из расчета?

Я смотрел на то, как Mathematica справляется с подобными ситуациями, и он просто спасается, сказав

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

Я попробовал подобный подход, но затем, поскольку размер стека зависит от ОС, как узнать, какое число использовать в качестве предела итерации (да, я нашел число, которое «кажется, работает» экспериментально но это не правильно)?

Спасибо за ваше время. Ядро калькулятора написано на C.

Answer 1

Это просто один из уродливых маленьких уголков C - просто нет портативного способа узнать, сколько стеков вы можете безопасно использовать.Технически, даже не должно быть достаточно стека для вызова одной функции из main() - это считается качеством реализации .

Самый безопасный подход - это развернутьваша рекурсия, чтобы он использовал свой собственный стек выражений, который вы выделяете с помощью malloc(), а не неограниченную подлинную рекурсию.Таким образом, вы можете спасти, если malloc() вернет NULL до того, как вы достигнете предела рекурсии, определенного в приложении.

Answer 2

Вместо реализации вызовов математических функций на уровне пользователя как вызовов функций C, реализуйте свой собственный стек на основе кучи с помощью malloc. Это даст вам гораздо больше уровней рекурсии и даст возможность надежно определить неудачу.

В качестве альтернативы вы можете просто установить достаточно небольшой предел для уровней рекурсии.

Answer 3

Быстрый взлом - просто отслеживать глубину рекурсии и выходить, если она превышена.Счетчик будет достаточно.Вам может потребоваться сбросить счетчик между каждой оценкой, но он не такой надежный, как запуск собственного стека.