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

Question

[tranquil]

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


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

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


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

Answer 1

[sergei-grigorev]

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

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

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

Comments

[mayhem]

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

[silvansky]

Мне кажется, что если задача легко решается рекурсией, не стоит её решать другими методами. Это я к задаче об обходе дерева — рекурсия здесь более чем уместна.

Answer 2

[youngmysteriouslight]

Используй то, что более удобно. Если реализация очевидна в терминах цикла, не следует использовать рекурсию. И наоборот. Так, если мыслишь решение задачи как функциональную зависимость (пусть для того же факториала), то тебе поможет рекурсия. Она позволит отделить тебе одно вычисление от другого, которое опирается только на результат первого. Впрочем, если ты четко видишь, что именно следует делать с переменными предыдущей итерации, чтоб получить следующий результат, то цикл будет организовать проще.
Поддерживать, опять же, проще тот код, в котором четко просматривается логика (эта оценка субъективна).
Ответь себе на вопрос: что такое факториал? «n!=n*(n-1)!, если n>1; n!=1 иначе» или «n! есть то, что получится, умножив подряд 1 на 2, на 3, на 4, ..., на n»
Или же такой: какой вариант приходит тебе первым, если требуется просуммировать элементы в динамическом списке? Создать указатель, идти по списку до конца и прибавлять к переменной, пока указатель не станет нулевым? Или просуммировать первый элемент с суммой хвоста (если тот не пуст)?
Для каждой задачи первый приходящий в голову вариант будет определять, к чему ты ближе, что тебе будет удобнее использовать, что будет проще читать.

Comments

[tranquil]

Мне то удобнее что-то одно. Но код, написанный одним человеком, потом возможно придётся читать другим людям. Поэтому и интересно собрать как можно больше мнений.

Answer 3

[gro]

Если бы что-нибудь одно было предпочтительнее другого во всех случаях, этого другого бы не было.

Comments

[tranquil]

В legacy бывает даже то, что хуже чего-то другого во всех случаях.

[Дима Соколов]

tranquil: с чем это связано?

Answer 4

[Пума Тайланд]

В академическом программировании уместнее конечно рекурсия, так как код получается красивее и местами понятнее.
Но при практическом программировании рекурсии на мой взгляд места почти нет, так как местами сложно отлаживать и + проблемы со стеком.

Comments

[tranquil]

Что такое «академическое программирование»?

[Пума Тайланд]

Ну когда ради души там в школе, на олимпиадах, в универе.

[Владимир Чернышев]

Когда не для production :)

[yeputons]

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

[silvansky]

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

Answer 5

[utyv]

Есть еще третий вариант: обобщенные функции, работающие со списками (массивами). map f l применяет функцию f к каждому элементу f и возвращает список результатов. filter p l возвращает список элементов, для которых выполняется условие p. fold f l «сворачивает» список, помещая функцию f между его элементами. Большинство циклов в имеративном коде можно свести к этим функциям. А если программист понял, как они работают, ему уже не надо отлаживать код глазами (что в случае цикла, что в случае рекурсии).
Надо только, чтобы язык поддерживал работу с функциями как со значениями. И анонимные функции не помешают (лябда-выражения по научному).

Answer 6

[bagyr]

В CLR tail медленнее call даже в тех языках, где он поддерживается.

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