В чем преимущество рекурсии перед циклом? Почему программисты с таким упорством продолжают пихать в курсы по программированию целые разделы, посвященные рекурсиич хотя циклы насного легяе для понимания, и зачастую гораздо менее требовательные к ресурсам?
Например, тебе нужно рекурсивно обойти все файлы в директориях, ты не знаешь сколько там файлов, в таком случае использывание рекурсивного генератора очень удобно
И кто же в 2020 обходит файловую систему? Для каких целей?
Рекурсия неявным образом использует стек, поэтому некоторые алгоритмы (как правило это что-то связаное с деревьями) на ней значительно проще и наглядней, чем в итеративном варианте, так как в нем тебе нужно либо явно работать со стеком, либо придумывать стеку равноценую замену, либо искать альтернативный алгоритм более лаконичный при итеративном подходе. Если ты можешь решить задачу итеративно то рекурсия нахуй не нужна. Есть еще разные мемные языки в которых итеративный конструкций может просто не быть, но это отдельный случай.
Обход в глубину (который делается рекурсивно) обычно короче и более очевидный.
В нормальных языках нет циклов
Это пример, блеать. Многие задачи, где есть структура данных, похожая на дерево, тупо легче решаются с рекурсией. Но не обязательно дерево.
Ну представь себе любую задачу где нужно обойти граф в глубину.
Допустим тебе нужно написать тест-хелпер, чтобы можно было рекурсивно развернуть любой GraphQL тип по имени.
>В нормальных языках нет циклов
И вакансий
Есть, но мало.Элитно, хули.
Циклы не могут заменить рекурсию. Это разные вещи. Часто бывает нужна рекурсия внутри цикла который внутри рекурсит
>Циклы не могут заменить рекурсию
Le proofs?
>циклы насного легяе для понимания, и зачастую гораздо менее требовательные к ресурсам?
Не обязательно.
https://ru.wikipedia.org/wiki/Хвостовая_рекурсия
Циклы могут заменить хвостовую рекурсию, а хвостовую рекурсию могут заменить циклы. Не знаю, можно ли любую рекурсию превратить в хвостовую в общем случае, но в ряде конкретных случаев можно.
Вот хвостовая рекурсия как раз уебищная и такая же многословная как обычный цикл.
Но ведь все равно нужно какое-то условие выхода из рекурсии, не? А если есть какое-то условия выхода, то можно и циклом сделать.
То есть ты считаешь, что существует только один вид рекурсии - бесконечная?
В общем случае можно заменить любую рекурсию на цикл. Вопрос лишь в цене.
Ну рекурсия без условия выхода - вечная рекурсия.
Вот поэтому в ФП есть fold, map, filter и прочие функции высшего порядка, которые прячут кишки рекурсии.
Если можно, то чтож авторы компиляторов только хвостовую рекурсию в цикл научились превращать, да и то не всегда?
Потому что КРУТО!
Хороший вопрос. Видимо, у такой оптимизации есть далеко идущие последствия. А может, стандарты языков не требуют этого, вот и авторы компиляторов не заморачиваться. Иногда всё же заморачиваются, например GHC (haskell). Но в нормальных языках я с этим не сталкивался.
Ни в чем, и работает дольше. Рекурсии только для выебонов и случаев типа хождений по ветвистой хуйне с неизвестной вложенностью.
Все намного проще: заменять не-хвостовую рекурсию на цикл нет никакого смысла, т.к. единственный способ это сделать автоматически - сохранять все аргументы в стек в конце каждой итерации, что и так происходит при рекурсивном вызове функции.
Задача же нахождения для рекурсивного алгоритма итеративного эквивалента, сдается мне, не решаема автоматически.
В GHC оптимизирована только хвостовая рекурсия, не?
> что и так происходит при рекурсивном вызове функции
Разница в том, что при этом используется стек (системный), и его размер сильно ограничен. При переписывании с явным использованием своего стека его можно хотя бы ресайзнуть. Наверное, автоматически это не оптимизируют всё же потому, что при бесконечной рекурсии лучше уж программа быстро упадёт, чем сначала сожрёт всю оперативку.
Насколько я понимаю, не только хвостовая. По крайней мере, я когда-то давно это дело тыкал, и мне не удалось добиться переполнения стека. А это должно быть достаточно легко, рекурсия там на каждый чих юзается.
Ленивость в каком то смысле в том числе оптимизирует рекурсию, не давая выполнять некоторые вызовы, если от них не зависит общий результат.
Я погуглил, в Хаскелле вообще не используется стэк в общем случае.
wiki.haskell.org/Stack_overflow
>Я погуглил, в Хаскелле вообще не используется стэк в общем случае.
Ну т.е. call stack, так то там какие то стэки есть.
Ленивость это ленивость, она с оптимизацией рекурсии никак не связана. Ты любом языке можешь сделать бесконечный стрим с рекурсией, но если ты запустишь его на достаточно большой последовательности можно получить stack overflow, о чем и пишется в статье по твоей ссылке.
When GHC is evaluating a thunked expression it uses an internal stack. This inner stack for thunk evaluation is the one that can overflow in practice.
First, read Performance/Accumulating parameter. If you are not writing your code tail-recursively, then that is why you are getting stack overflows.
> и случаев типа хождений по ветвистой хуйне с неизвестной вложенностью.
Ну то есть всего лишь для реализации быстрой сортировки и хуевой тучи других элементарных и неочень алгоритмов.
Никто кроме борщехлёбов и не говорил, что "рекурсия - это лучшая вещь всех времён и народов, всегда используйте её вместо цикла".
Ну хорошо.
