Функциональные языки лучше в рекурсии?

TL; DR: функциональные языки обрабатывают рекурсию лучше, чем нефункциональные?

В настоящее время я читаю Code Complete 2. В какой-то момент в книге автор предупреждает нас о рекурсии. Он говорит, что этого следует избегать, когда это возможно, и что функции, использующие рекурсию, обычно менее эффективны, чем решения, использующие циклы. В качестве примера автор написал функцию Java, использующую рекурсию для вычисления факториала числа, например, (например, это может быть не совсем так, поскольку у меня сейчас нет книги):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Это представляется как плохое решение. Однако в функциональных языках использование рекурсии часто является предпочтительным способом работы. Например, вот такая функция в Haskell с использованием рекурсии:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

И широко принимается как хорошее решение. Как я видел, Хаскелл очень часто использует рекурсию, и я нигде не видел, чтобы ее осуждали.

Так что мой вопрос в основном таков:

• Функциональные языки обрабатывают рекурсию лучше, чем нефункциональные?

РЕДАКТИРОВАТЬ: я знаю, что примеры, которые я использовал, не являются лучшими, чтобы проиллюстрировать мой вопрос. Я просто хотел отметить, что Haskell (и функциональные языки в целом) использует рекурсию гораздо чаще, чем нефункциональные языки.

Да, они делают, но не только потому, что могут , но и потому, что должны .

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

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

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

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

Однако итерация требует смены счетчика. Это означает, что должна быть изменяемая переменная , которая запрещена в чисто функциональной настройке. Таким образом, функциональные языки специально разработаны для работы без необходимости итерации, следовательно, упорядоченные вызовы функций.

Но ничего из этого не объясняет, почему ваш пример кода такой гладкий. В вашем примере демонстрируется другое свойство - сопоставление с шаблоном . Вот почему образец на Haskell не имеет явных условий. Другими словами, это не упрощенная рекурсия, которая делает ваш код маленьким; это сопоставление с образцом.

Технически нет, но практически да.

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

1. Оптимизация вызовов Как указывают другие авторы, функциональные языки часто требуют TCO.

2. Ленивая оценка. Haskell (и несколько других языков) лениво оценивают. Это задерживает фактическую «работу» метода до тех пор, пока он не потребуется. Это приводит к более рекурсивным структурам данных и, соответственно, к рекурсивным методам работы с ними.

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

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

Haskell и другие функциональные языки обычно используют ленивую оценку. Эта функция позволяет писать бесконечные рекурсивные функции.

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

Haskell также поддерживает рекурсивные оптимизации вызовов функций. В Java каждый вызов функции складывается и вызывает накладные расходы.

Так что да, функциональные языки обрабатывают рекурсию лучше, чем другие.

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

Обратите внимание, что эта оптимизация не работает ни для одного рекурсивного вызова, а только для рекурсивных методов с хвостовым вызовом (т. Е. Методов, которые не поддерживают состояние во время рекурсивного вызова)

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

Язык программирования Alef , который раньше приходил вместе с Plan 9 от Bell Labs, имел утверждение «становиться» (см. Раздел 6.6.4 этой ссылки ). Это своего рода явная оптимизация рекурсии хвостового вызова. "Но он использует стек вызовов!" аргумент против рекурсии потенциально может быть покончено.

TL; DR: Да, они делают
Рекурсия является ключевым инструментом в функциональном программировании, и поэтому была проделана большая работа по оптимизации этих вызовов. Например, R5RS требует (в спецификации!), Чтобы все реализации обрабатывали несвязанные вызовы хвостовой рекурсии без беспокойства программиста о переполнении стека. Для сравнения, по умолчанию компилятор C не будет выполнять даже очевидную оптимизацию хвостового вызова (попробуйте рекурсивную обратную обработку связанного списка), и после некоторых вызовов программа завершит работу (хотя компилятор оптимизирует, если вы используете - O2).

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

РЕДАКТИРОВАТЬ: Под примером FIB я имею в виду следующее:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)

Функциональные языки лучше справляются с двумя очень специфическими видами рекурсии: хвостовая рекурсия и бесконечная рекурсия. Они так же плохи, как и другие языки в других видах рекурсии, как в вашем factorialпримере.

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

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

Например, предложение Делнана factorial n = product [1..n]не только более лаконично и легко читается, но и очень распараллелимо. То же самое для использования foldили reduceесли ваш язык не имеет productуже встроенного. Рекурсия является последним средством для решения этой проблемы. Основная причина, по которой вы видите, что это решается рекурсивно в учебных пособиях, заключается в том, что это является отправной точкой для достижения лучших решений, а не примером лучшей практики.