Извините, ничего не найдено.

impersonalis · 29.04.2011, 13:02

А ну-ка срач на тему:
Рекурсия хороша только как алгоритмическая абстракция.
Минусы р:
- исчерпание стека (в цикле мы можем использовать свою реализацию итераторов, поддерживающую Большие значения)
- различное поведение в разных местах вызова (стек может быть уже забит)
- частенько реализация рекурсии в коде выглядит брейнфачно

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

SBJoker · 29.04.2011, 13:05

Например построение дерева папок на диске... давайте без рекурсии сделайте.

impersonalis · 29.04.2011, 13:08

Как и с заливкой полиогна - достаточно списка структур, фиксирующих объекты (состояния обхода).
Рекурсия - простота или примитив? Кто стоит за Джокером?
Узнайте на булке!

ffinder · 29.04.2011, 13:44

Сообщение от impersonalis

А ну-ка срач на тему:

хочешь срача - получи

Сообщение от impersonalis

Рекурсия хороша только как алгоритмическая абстракция.

еще год назад я бы сказал то же самое. теперь я скажу: "рекурсия - основа всего"

Сообщение от impersonalis

исчерпание стека

кури "оптимизация хвостовой рекурсии", рекурсия с аккумуляторами

Сообщение от impersonalis

стек может быть уже забит

есть рантаймы, которые автоматически наращивают стек (дада, Эрланг), если его вдруг не хватает

Сообщение от impersonalis

реализация рекурсии в коде выглядит брейнфачно

часто код без рекурсии выглядит как говно. а код без паттерн матчинга и подавно всегда выглядит как говно (но это я уже отвлекся).

Сообщение от impersonalis

Пока все примеры использования рекурсии я мог разложить в цикл.

думай об этом иначе - цикл это частный (вырожденный) случай рекурсии.

impersonalis · 29.04.2011, 17:46

2ffinder: подача мысли нравится - спасибо за коммент.
"оптимизация", "есть такие", "кури то-то" - постараться если (на самом деле - особо и не надо), то можно оправдать использование goto и вообще любой паттерн. Понятно: раз живёт - то иногда-то используется, однако от вычисления факториала через рекурсию - волосы дыбом (код кристально ясен, но автор далёк и от проганья, и от численных методов и подобного матана)

HolyDel · 29.04.2011, 18:32

вычисления факториала через рекурсию - волосы дыбом

ето скорее пример на котором учат дошкольников рекурсии.

любые алгоритмы для работы с деревьями решаются красиво через рекрсию. от решения поиска в бинарном дереве через списки структур фиксирующие объекты волосы встают не меньше чем от решения факториала рекурсией.

SBJoker · 29.04.2011, 18:40

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

pax · 29.04.2011, 19:37

Сообщение от impersonalis

то можно оправдать использование goto и вообще любой паттерн.

В эрланге хвостовая рекурсия используется как стандарт/паттерн, большинство методов используют ее для итерации и т.д. Она вообще не использует стек помойму.

http://itc.ua/articles/yazyk_erlang_...cessorov_26721

Начнем с простой задачи вычисления факториала.
...
и запускаем функцию с аргументом, скажем, 20 000 (команда: fac(20 000)).

После небольшой задержки на экран начинает выводиться результат – свыше 70 тыс. цифр. Может быть, на неспециалиста это не произведет особого впечатления, но любой программист, работающий с «обычными» языками, сразу же испытает к Erlang уважение. Во-первых, мы получили результат с невероятной точностью (к примеру, в C# без использования специализированных библиотек «длинной арифметики» программистам доступны целые числа с максимальной 64-разрядной точностью – а это всего каких-то 20 знаков), а во-вторых, он получен рекурсивной функцией с огромной глубиной вложенности – в том же C# неминуемо произойдет переполнение стека.

Но самое поразительное то, что в Erlang вообще нет никаких ограничений ни на длину целых чисел, ни на глубину рекурсивных функций! Единственный ограничивающий фактор – это вычислительные возможности компьютера. Таким образом, программист не должен отвлекаться на такие вопросы, как «Сколько знаков способен хранить используемый тип данных?» или «Cколько уровней вложенности может иметь рекурсивный вызов?».

правда в примере не хвостовая рекурсия на сколько я понял.

ffinder · 29.04.2011, 20:41

Сообщение от impersonalis

"оптимизация", "есть такие", "кури то-то" - постараться если (на самом деле - особо и не надо), то можно оправдать использование goto и вообще любой паттерн.

отставить нытьё. С++ уже несколько лет это умеет.
добрый stackoverflow подсказывает как это делать.
так что это вам не это. главное чтобы рекурсия была хвостовой (когда рекурсивный вызов - последний sequence point в функции), а не обычной.

impersonalis · 30.04.2011, 14:14

Сообщение от pax

...

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

***

Как и с гото, аргументировать (судя по кол-ву СПС ко 2-ому посту) использование рекурсии вместо цикла средний (! перечитай слово слева 20 раз) программист может только тем, что не хватает воображалки реализовать алгоритм не в лоб.