forum.boolean.name - Рекурсия

forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Рекурсия (http://forum.boolean.name/showthread.php?t=14648)

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 (Сообщение 187000)

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

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

Цитата:

Сообщение от impersonalis (Сообщение 187000)

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

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

Цитата:

Сообщение от impersonalis (Сообщение 187000)

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

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

Цитата:

Сообщение от impersonalis (Сообщение 187000)

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

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

Цитата:

Сообщение от impersonalis (Сообщение 187000)

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

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

Цитата:

Сообщение от impersonalis (Сообщение 187000)

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

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

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 (Сообщение 187017)

то можно оправдать использование 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 (Сообщение 187017)

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

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

impersonalis

30.04.2011 14:14

Ответ: Рекурсия

Цитата:

Сообщение от pax (Сообщение 187030)

...

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

***

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

Часовой пояс GMT +4, время: 02:38.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot