Могут ли программы на функциональных языках чаще иметь переполнение стека?

Все (достойные реализации ;-) функциональных языков оптимизируют хвостовую рекурсию, но это не то, что вы делаете здесь, поскольку рекурсивный вызов не является ПОСЛЕДНЕЙ операцией (за ним должно следовать добавление).

Итак, вскоре вы научитесь использовать вспомогательную функцию, которая является хвостовой рекурсией (и принимает в качестве аргумента текущую сумму, накапливаемую), чтобы оптимизатор мог выполнять свою работу, то есть за вычетом возможного синтаксиса O'Caml, в котором я заржавел:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Здесь сумма возникает как АРГУМЕНТ для рекурсивного вызова, т. е. ДО самой рекурсии, и поэтому может начаться хвостовая оптимизация (поскольку рекурсия — это последнее, что должно произойти!).

Функциональные языки обычно имеют НАМНОГО больший стек. Например, я написал функцию специально для проверки ограничений стека в OCaml, и она выполнила более 10 000 вызовов, прежде чем ее вырвало. Тем не менее, ваша точка зрения верна. Переполнения стека по-прежнему нужно остерегаться в функциональных языках.

Одной из стратегий, которые функциональные языки используют для снижения своей зависимости от рекурсии, является использование оптимизации хвостового вызова. Если вызов следующей рекурсии текущей функции является последним оператором в функции, текущий вызов может быть удален из стека, а на его месте создан новый вызов. Сгенерированные ассемблерные инструкции будут в основном такими же, как и для циклов while в императивном стиле.

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;;

Некоторые функциональные языки, такие как Scheme, указывают, что хвостовая рекурсия должна быть оптимизирована. быть эквивалентным итерации; следовательно, функция хвостовой рекурсии в Scheme никогда не приведет к переполнению стека, независимо от того, сколько раз она рекурсивна (предполагая, конечно, что она также не рекурсивно или не участвует во взаимной рекурсии в других местах, кроме конца).

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

Новичкам, безусловно, легко писать глубокие рекурсии, которые взрывают стек. Objective Caml необычен тем, что функции библиотеки List не безопасны для стека для длинных списков. Такие приложения, как Unison, фактически заменили стандартную библиотеку Caml List библиотекой, безопасной для стека. версия. Большинство других реализаций лучше справляются со стеком. (Отказ от ответственности: моя информация описывает Objective Caml 3.08; текущая версия 3.11 может быть лучше.)

Стандартный ML штата Нью-Джерси отличается тем, что не использует стек, поэтому ваши глубокие рекурсии продолжаются. пока у вас не кончится куча. Это описано в отличной книге Эндрю Аппеля Компиляция с продолжением .

Я не думаю, что здесь есть серьезная проблема; это скорее «точка осознания» того, что если вы собираетесь писать много рекурсивного кода, что вы, скорее всего, будете делать на функциональном языке, вы должны знать о не-хвостовых вызовах и размере стека как по сравнению с размером данных, которые вы будете обрабатывать.

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