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

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

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

fun(n) = fun(n-1)

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

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

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

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

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

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


c recursion stack-overflow
person houbysoft    schedule 25.01.2011    source источник
comment
Если вы пишете калькулятор, чтобы не делать рекурсивные вызовы на самом хосте - например. обрабатывать реализацию через стек самостоятельно, тогда ограничение является произвольным в зависимости от доступной памяти, которая может быть выделена/может быть выделена (и некоторая разумная глубина)   -  person    schedule 25.01.2011

Ответы (3)


arrow_upward
4
arrow_downward

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

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

person caf    schedule 25.01.2011
comment
+1 за развертывание рекурсии, но если вы это сделаете, вам не следует включать ограничение рекурсии; просто продолжайте пыхтеть, пока malloc не выйдет из строя (или вы не закончите, конечно). - person David X; 25.01.2011
comment
@David X: Можно было бы считать антисоциальным потратить 30 минут на заполнение всего доступного пространства подкачки и, наконец, умереть только потому, что пользователь дал вам неверный ввод. Ограничение рекурсии существует, чтобы поймать ошибочную бесконечную рекурсию (однако сделайте ее настраиваемой пользователем). - person caf; 25.01.2011
comment
правильно, я почему-то думал о жестко закодированном лимите. - person David X; 25.01.2011

arrow_upward
2
arrow_downward

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

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

person R.. GitHub STOP HELPING ICE    schedule 25.01.2011

arrow_upward
0
arrow_downward

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

person I GIVE CRAP ANSWERS    schedule 25.01.2011