F# хвостовая рекурсия и почему бы не написать цикл while?
Я изучаю F# (новичок в функциональном программировании в целом, хотя в течение многих лет он использовал функциональные аспекты C#, но давайте посмотрим правде в глаза, это совсем другое дело), и одна из вещей, которые я прочитал, заключается в том, что компилятор F# определяет хвостовую рекурсию и компилирует ее во время цикла (см. http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).
Чего я не понимаю, так это почему вы пишете рекурсивную функцию вместо цикла while, если это то, во что это все равно превратится. Особенно учитывая, что вам нужно проделать дополнительную работу, чтобы сделать вашу функцию рекурсивной.
У меня есть чувство, что кто-то может сказать, что цикл while не особенно функционален, и вы хотите действовать полностью функционально, и поэтому вы используете рекурсию, но тогда почему компилятору достаточно превратить его в цикл while?
Может кто-то объяснить это мне?
4 ответа
Вы можете использовать тот же аргумент для любого преобразования, которое выполняет компилятор. Например, когда вы используете C#, вы когда-нибудь использовали лямбда-выражения или анонимные делегаты? Если компилятор просто собирается превратить их в классы и (неанонимные) делегаты, то почему бы просто не использовать эти конструкции самостоятельно? Точно так же вы когда-нибудь использовали блоки итераторов? Если компилятор просто собирается превратить их в конечные автоматы, которые явно реализуют IEnumerable<T>тогда почему бы просто не написать этот код самостоятельно? Или, если компилятор C# просто все равно будет генерировать IL, зачем вообще писать C# вместо IL? И так далее.
Одним из очевидных ответов на все эти вопросы является то, что мы хотим написать код, который позволяет нам четко выражать свои мысли. Аналогично, есть много алгоритмов, которые являются естественно рекурсивными, и поэтому написание рекурсивных функций часто приводит к четкому выражению этих алгоритмов. В частности, возможно, легче рассуждать о завершении рекурсивного алгоритма, чем цикла while во многих случаях (например, существует ли четкий базовый случай, и делает ли каждый рекурсивный вызов проблему "меньшей"?).
Однако, поскольку мы пишем код, а не математические статьи, также неплохо иметь программное обеспечение, которое соответствует определенным реальным критериям производительности (например, возможность обрабатывать большие входные данные без переполнения стека). Поэтому тот факт, что хвостовая рекурсия преобразуется в эквивалент циклов while, имеет решающее значение для возможности использования рекурсивных формулировок алгоритмов.
Рекурсивная функция часто является наиболее естественным способом работы с определенными структурами данных (такими как деревья и списки F#). Если компилятор хочет преобразовать мой естественный, интуитивно понятный код в неловкий цикл while по соображениям производительности, это нормально, но зачем мне это писать самому?
Кроме того, ответ Брайана на связанный вопрос актуален здесь. Функции высшего порядка часто могут заменить как циклы, так и рекурсивные функции в вашем коде.
Тот факт, что F# выполняет оптимизацию хвоста, - это просто деталь реализации, которая позволяет использовать хвостовую рекурсию с той же эффективностью (и не опасаясь переполнения стека), что и цикл while. Но это просто - деталь реализации - на первый взгляд ваш алгоритм по-прежнему рекурсивен и структурирован таким образом, что для многих алгоритмов является наиболее логичным и функциональным способом его представления.
То же самое относится к некоторым внутренним элементам обработки списка, а также в F# - внутренняя мутация используется для более эффективной реализации манипулирования списком, но этот факт скрыт от программиста.
Суть в том, как язык позволяет вам описывать и реализовывать ваш алгоритм, а не то, какие механизмы используются для этого.
while петля является обязательным по своей природе. Большую часть времени при использовании while циклы, вы обнаружите, что пишете такой код:
let mutable x = ...
...
while someCond do
...
x <- ...
Этот шаблон распространен в императивных языках, таких как C, C++ или C#, но не так распространен в функциональных языках.
Как говорили другие авторы, некоторые структуры данных, точнее рекурсивные структуры данных, пригодны для рекурсивной обработки. Поскольку наиболее распространенной структурой данных в функциональных языках является, безусловно, односвязный список, решение проблем с использованием списков и рекурсивных функций является обычной практикой.
Другим аргументом в пользу рекурсивных решений является тесная связь между рекурсией и индукцией. Использование рекурсивного решения позволяет программисту думать о проблеме индуктивно, что, вероятно, помогает в ее решении.
Опять же, как говорили другие авторы, тот факт, что компилятор оптимизирует хвостовые рекурсивные функции (очевидно, не все функции могут извлечь выгоду из оптимизации хвостовых вызовов), является деталью реализации, которая позволяет вашему рекурсивному алгоритму работать в постоянном пространстве.