F # хвостовая рекурсия и почему бы не написать цикл while?

Question

Я изучаю F # (новичок в функциональном программировании в целом, хотя в течение многих лет использовались функциональные аспекты C #, но давайте посмотрим правде в глаза, это совсем другое дело), ​​и одна из вещей, которые я прочитал, заключается в том, что компилятор F # идентифицирует хвостовую рекурсиюи компилирует его в цикл while (см. http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).

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

У меня есть чувство, что кто-то может сказать, что цикл while не особенно функционален, и вы хотите действовать все функционально и все такое, поэтому вы используете рекурсию, но тогда почемудостаточно ли для компилятора превратить его в цикл while?

Может кто-нибудь объяснить мне это?

Answer 1

Вы можете использовать тот же аргумент для любого преобразования, которое выполняет компилятор.Например, когда вы используете C #, вы когда-нибудь использовали лямбда-выражения или анонимные делегаты?Если компилятор просто собирается превратить их в классы и (неанонимные) делегаты, то почему бы просто не использовать эти конструкции самостоятельно?Точно так же вы когда-нибудь использовали блоки итераторов?Если компилятор просто собирается превратить их в конечные автоматы, которые явно реализуют IEnumerable<T>, то почему бы просто не написать этот код самостоятельно?Или, если компилятор C # просто собирается испускать IL, зачем вообще писать C # вместо IL?И так далее.

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

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

Answer 2

Рекурсивная функция часто является наиболее естественным способом работы с определенными структурами данных (такими как деревья и списки F #). Если компилятор хочет превратить мой естественный, интуитивно понятный код в неловкий цикл while по соображениям производительности, это нормально, но зачем мне это писать самому?

Кроме того, ответ Брайана на связанный вопрос актуален здесь. Функции высшего порядка часто могут заменить как циклы, так и рекурсивные функции в вашем коде.

Answer 3

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

То же самое относится к некоторым внутренним элементам обработки списка, а также в F # - внутренняя мутация используется для более эффективной реализации манипулирования списком, но этот факт скрыт от программиста.

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

Answer 4

A while петля обязательна по своей природе.В большинстве случаев при использовании циклов while вы будете писать код, подобный следующему:

let mutable x = ...
...
while someCond do
    ...
    x <- ...

Этот шаблон распространен в императивных языках, таких как C, C ++ или C #, но не так распространен в функциональных.языки.

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

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

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