Программы в функциональных языках более вероятно, чтобы иметь переполнения стека?
Это - потому что size_t может быть чем-либо кроме интервала (возможно, структура). Идея состоит в том, что это разъединяется, это - задание от базового типа.
5 ответов
Все (достойные реализации ;-) функциональных языков оптимизируют хвостовую рекурсию, но это не то, что вы здесь делаете , так как рекурсивный вызов не является ПОСЛЕДНЕЙ операцией (за ней должно следовать добавление).
Таким образом, вскоре можно научиться использовать вспомогательную функцию, которая является хвостовой рекурсивной (и принимает текущую сумму, накапливаемую в качестве аргумента), так что оптимизатор может выполнять свою работу, т. Е. Без возможного синтаксиса O'Caml, в котором I ' m rusty:
let sum x =
aux(x)(0);;
let rec aux x accum =
if x > 1 then aux(x - 1)(accum + x)
else (accum + x);;
Здесь сумма выступает как АРГУМЕНТ для рекурсивного вызова, т. е. ДО самой рекурсии, и поэтому может начаться оптимизация хвоста (потому что рекурсия - это последнее, что должно произойти!).
Некоторые функциональные языки, такие как Scheme, указывают, что хвостовая рекурсия должна быть оптимизирована , чтобы быть эквивалентной итерации; следовательно, хвостовая рекурсивная функция в Scheme никогда не приведет к переполнению стека, независимо от того, сколько раз она рекурсивно повторяется (конечно, при условии, что она также не рекурсивна и не участвует во взаимной рекурсии в других местах, кроме конца).
Большинство других функциональных языков не требуют эффективной реализации хвостовой рекурсии; некоторые предпочитают это делать, другие нет, но это относительно легко реализовать, поэтому я ожидаю, что большинство реализаций так и поступят.
Функциональные языки обычно имеют НАМНОГО больший стек. Например, я написал функцию специально для проверки ограничений стека в OCaml, и она успела обработать более 10 000 вызовов, прежде чем она была заблокирована. Однако ваша точка зрения верна. Переполнение стека - это то, чего вам нужно остерегаться в функциональных языках.
Одной из стратегий, которые функциональные языки используют для смягчения своей зависимости от рекурсии, является использование оптимизации хвостового вызова . Если вызов следующей рекурсии текущей функции является последним оператором в функции, текущий вызов может быть исключен из стека и вместо него создается новый вызов. Сгенерированные инструкции сборки будут в основном такими же, как и инструкции для циклов while в императивном стиле.
Ваша функция не может быть оптимизирована с помощью хвостового вызова, потому что рекурсия - не последний шаг. Сначала ему нужно вернуться, а затем он может добавить x к результату. Обычно это легко обойти, вы просто создаете вспомогательную функцию, которая передает аккумулятор вместе с другими параметрами
let rec sum x =
let sum_aux accum x =
if x > 1 then sum_aux (accum + x) (x - 1)
else x
in sum_aux 0 x;;
Это сложно - в принципе да, но компиляторы и среды выполнения для функциональных языков учитывают повышенную степень рекурсии в функциональных языках. Самым простым является то, что большинство сред исполнения функциональных языков запрашивают гораздо больший стек, чем использовали бы обычные итерационные программы. Но в дополнение к этому компилятор функционального языка гораздо более способен преобразовывать рекурсивный код в нерекурсивный из-за гораздо более строгих ограничений языка.
Самым простым является то, что большинство сред исполнения функциональных языков запрашивают гораздо больший стек, чем использовали бы обычные итерационные программы. Но в дополнение к этому компилятор функционального языка гораздо более способен преобразовывать рекурсивный код в нерекурсивный из-за гораздо более строгих ограничений языка. Самым простым является то, что большинство сред исполнения функциональных языков запрашивают гораздо больший стек, чем использовали бы обычные итерационные программы. Но в дополнение к этому компилятор функционального языка гораздо более способен преобразовывать рекурсивный код в нерекурсивный из-за гораздо более строгих ограничений языка. Новичкам, безусловно, легко написать глубокую рекурсию, которая взорвет стек. Objective Caml необычен тем, что функции библиотеки List не поддерживают стек для длинных списков . Такие приложения, как Unison , фактически заменили стандартную библиотеку Caml List версией, безопасной для стека. Большинство других реализаций лучше справляются со стеком. (Отказ от ответственности: моя информация описывает Objective Caml 3.08; текущая версия, 3.11, может быть лучше.)
Стандартный ML of New Jersey необычен тем, что он не использует стек, поэтому ваши глубокие рекурсии продолжают работать пока у вас не закончится куча. Это описано в прекрасной книге Эндрю Аппеля Компиляция с продолжениями .
Я не думаю, что здесь есть серьезная проблема; Это'