Интуитивный ответ заключается в том, что если у вас нет неограниченных циклов и у вас нет рекурсии, и у вас нет goto, ваши программы завершаются. Это не совсем верно, есть и другие способы проникновения без завершения, но этого достаточно для большинства практических случаев. Конечно, обратное неверно, есть языки с этими конструкциями, которые не допускают бесконечные программы, но они используют другие виды ограничений, такие как сложные системы типов.
Рекурсия
Общим ограничением в языках сценариев является динамическое предотвращение рекурсии: если A вызывает B, вызывает C, вызывает ... вызывает A, то интерпретатор (или проверка, в вашем случае) сдается или сигнализирует об ошибке, даже если рекурсия может фактически завершиться. Два конкретных примера:
Препроцессор C оставляет макрос без изменений, пока расширяет этот макрос. Чаще всего используется для определения оболочки вокруг функции:
#define f(x) (printf("calling f(%d)\n", (x)), f(x))
f(3);
Это расширяется до
(printf("calling f(%d)\n", (3)), f(3))
Взаимная рекурсия также обрабатывается. Следствием этого является то, что препроцессор C всегда завершает работу, хотя можно создавать макросы с высокой сложностью во время выполнения.
#define f0(x) x(x)x(x)
#define f1(x) f0(f0(x))
#define f2(x) f1(f1(x))
#define f3(x) f2(f2(x))
f3(x)
Оболочки Unix рекурсивно расширяют псевдонимы, но только до тех пор, пока не встретятся псевдонимы, которые уже расширяются. Опять же, основная цель состоит в том, чтобы определить псевдоним для команды с аналогичным именем.
alias ls='ls --color'
alias ll='ls -l'
NN
Существуют более общие методы, чтобы доказать, что рекурсивные вызовы завершаются, например, найти некоторое положительное целое число, которое всегда уменьшается от одного рекурсивного вызова к следующему, но их значительно сложнее обнаружить. Их часто трудно проверить, не говоря уже о том, чтобы сделать вывод.
Loops
for
мN
В частности, с помощью циклов for (плюс разумные языковые конструкции, такие как условные выражения) вы можете написать все примитивные рекурсивные функции и наоборот. Вы можете распознать примитивно-рекурсивные функции синтаксически (если они написаны беспристрастно), потому что они не используют цикл while, goto, recursion или другой трюк. Примитивно-рекурсивные функции гарантированно завершаются, и большинство практических задач не выходят за рамки примитивной рекурсии.
Жиль "ТАК - перестань быть злым"
источник