Циклы или рекурсия?

С точки зрения теории вычислительных процессов программа с рекурсией может быть заменена эквивалентной программой с циклами.


Какая альтернатива предпочтительна в программировании?

Что проще писать, читать, поддерживать?


Чтобы не уводить тему в сторону эффективности кода, предположим, что задача не глубокая по сравнению с размером стека. Или компилятор поддерживает хвостовую рекурсию.
  • Вопрос задан
  • 26010 просмотров
Пригласить эксперта
Ответы на вопрос 6
@sergei-grigorev
Все зависит от задачки. Порою достаточно простого цикла, с ним и работать проще и нет проблем со стеком. Еще, лучше все таки в цикле решать задачи, где результат следующего полностью зависит от результата предыдущего (например, факториал).

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

Еще рекурсия будет эффективна, если рекурсивная функция кешируемая, например, она запоминает результат и при следующем запросе просто возвращается кешированный вариант.
Ответ написан
youngmysteriouslight
@youngmysteriouslight
ТК, ТТ, JS, FP, WM
Используй то, что более удобно. Если реализация очевидна в терминах цикла, не следует использовать рекурсию. И наоборот. Так, если мыслишь решение задачи как функциональную зависимость (пусть для того же факториала), то тебе поможет рекурсия. Она позволит отделить тебе одно вычисление от другого, которое опирается только на результат первого. Впрочем, если ты четко видишь, что именно следует делать с переменными предыдущей итерации, чтоб получить следующий результат, то цикл будет организовать проще.
Поддерживать, опять же, проще тот код, в котором четко просматривается логика (эта оценка субъективна).
Ответь себе на вопрос: что такое факториал? «n!=n*(n-1)!, если n>1; n!=1 иначе» или «n! есть то, что получится, умножив подряд 1 на 2, на 3, на 4, ..., на n»
Или же такой: какой вариант приходит тебе первым, если требуется просуммировать элементы в динамическом списке? Создать указатель, идти по списку до конца и прибавлять к переменной, пока указатель не станет нулевым? Или просуммировать первый элемент с суммой хвоста (если тот не пуст)?
Для каждой задачи первый приходящий в голову вариант будет определять, к чему ты ближе, что тебе будет удобнее использовать, что будет проще читать.
Ответ написан
@gro
Если бы что-нибудь одно было предпочтительнее другого во всех случаях, этого другого бы не было.
Ответ написан
opium
@opium
Просто люблю качественно работать
В академическом программировании уместнее конечно рекурсия, так как код получается красивее и местами понятнее.
Но при практическом программировании рекурсии на мой взгляд места почти нет, так как местами сложно отлаживать и + проблемы со стеком.
Ответ написан
@utyv
Есть еще третий вариант: обобщенные функции, работающие со списками (массивами). map f l применяет функцию f к каждому элементу f и возвращает список результатов. filter p l возвращает список элементов, для которых выполняется условие p. fold f l «сворачивает» список, помещая функцию f между его элементами. Большинство циклов в имеративном коде можно свести к этим функциям. А если программист понял, как они работают, ему уже не надо отлаживать код глазами (что в случае цикла, что в случае рекурсии).
Надо только, чтобы язык поддерживал работу с функциями как со значениями. И анонимные функции не помешают (лябда-выражения по научному).
Ответ написан
Комментировать
bagyr
@bagyr
В CLR tail медленнее call даже в тех языках, где он поддерживается.

Ну и надо быть сильно уверенным в себе, чтобы утверждать, что всякая «задача не глубокая по сравнению с размером стека» всегда таковой и останется при любых условиях, я бы не рисковал без нужды.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы