Ни для кого не секрет что иногда рекурсия позволяет писать читаемы и красивый код, но всегда есть риск совершить ошибку, что может например вызвать переполнение стека. Мне кажется, что рекурсии стараются избегать почти всегда. Уважаемые программисты, хочу спросить — насколько часто вы используете рекурсию на своих проектах?
ни разу в проде на java, для scala и haskell рекурсия норм
Иногда. Ниче страшного в рекурсии нету, особенно, если она хвостовая.
Ответ тут: dou.ua/...rums/topic/21219/#1149133
Мож мне кто читсо маркетингово объяснить, чем более позний пост Майка заслужил гораздо большее количество лайков, чем аналогичный раний пост чуть ниже ?
Може. Якщо a() зове b(), а те — a(), це теж рекурсія.
Але не така яскрава. :)
Це було неминуче!
На Scala и если списки(в Scala они имеют рекуррентную природу) то часто. В Java не часто. При функциональном подходе очень часто, т.к. ближе в математики, а там рекурсия довольно хорошо используется.
О каком языке идет речь ?
В джаве никогда не использовал.
В скале вполне пременимо. От переполнения стека стека существует хвостовая рекурсия и трамполины.
Только..
dou.ua/forums/topic/21219
На співбесіді декілька разів використовував.
Дай вгадаю — це був цикл із декількох співбесід, на ту саму посаду, з тими самим питаннями :)
www.youtube.com/watch?v=V4bniWXTGhU
У меня «следующее видео» выдаёт получче...
я использую часто на JS, когда нужно сделать много асинхронных запросов последовательно и использовать Promise.all не удобно
хм. а можно подробнее: как тут применить рекурсию?
Mike Gorchak
anonymous
Нестор Иванович
Vasilij Tjorkin
Grez
Valentin Nechayev
Yurii Khomenko
Александр Шевченко
Ювженко Денис
Олексій Пєніє
Alex Fogol
Alona H
Євген Козлов
Alona H
function generateAsync(coordinatesPromise) {
return coordinatesPromise
.then((coordinates) => {
// тут меняем наши координаты
})
.then((coordinates)=> request(options)) //делаем какой то запрос
.then(() => generateAsync(Promise.resolve(coordinates))) //Рекурсивно вызываем эту же функцию с промисом
}
бесконечно слать запросы на координаты последовательно, пока ошибка не вывалится?
и использовать Promise.all не удобно
ага, не подумал, это ж Promise.all попробует всё выполнить в параллель, что не надо, надо последовательность.
Оп-па, девушка Node.js девелопер. Вот это номер! Я в хорошем смысле, если что...
Странная у вас реакция, в мире js половой дискриминации нема
стараюсь не використовувати.
лише для якихось «малих» задач, коли точно знаю ніколи не буде занадто багато визовів.
Интересно если акторы по кругу шлют друг друга это уже можно считать рекурсией или таки нет?
Вообще-то да. Но ключевая бяка рекурсии, из-за которой её боятся — это необходимость потом возвращаться в точку вызова. Если этой необходимости нет (и есть специальные приёмы, чтобы от неё избавиться) — рекурсию просто перестают замечать.
В принципе, как догадываетесь, даже 1000 (или для ровного счёта, 1024) последовательно вложенных вызова — это пыль для моряка. Можете на тестовом юните проверить скорость и потребление. Грабли начинаются, когда в этой рекурсии создаются ОБЪЕКТЫ, которые через связи оказываются завязанными друг на друга. Точно знаю, что Garbage collector имел с такими большие затруднения, и можно элементарно отхватить утечку памяти. Современные вроде как умеют распутывать сложные связи — пусть это и непростая задача, и таки требующая ресурса.
Крайне рекомендую на рекурсиях, если создаются связанные объекты — писать деструктор класса, чтобы эти связи разрывать самостоятельно, не полагаясь на GarbageCollector что он «догадается». Эти догадки дорого обходятся. Равно как и искать подобные утечки — удовольствие ниже среднего, учитывая что становятся заметными они при серьёзной боевой нагрузке, и способны жёстко зафейлить казалось бы финальный релиз.
в джаве помимо всех бед еще и сборщик мусора мусор найти не может?
Уборка мусора в Java — лучше чем где бы то ни было. И задача сборки мусора — самая важная в принципе, и самая сложная. Ну может готова посоревноваться с потоками (хотя опять-таки, я не понимаю написания логики потоков именно на Java, нативные вещи надо писать под конкретные операционки.
Простой пример: как много ты знаешь программеров на Java, которые не боятся писать деструкторы своим классам? Вот теперь подойди в конторе к общему холодильнику, и попробуй выбросить из него ВСЁ лишнее. Если хоть что-то останется — you lose.
как много ты знаешь программеров на Java, которые не боятся писать деструкторы своим классам?
да я как бы джавистов пару человек всего видел
Вот теперь подойди в конторе к общему холодильнику, и попробуй выбросить из него ВСЁ лишнее. Если хоть что-то останется — you lose.
он инкапсулирован
Честно крайне слабо представляю себе чем рекурсия сама по себе поможет в создании кривосвязанных объектов создание которых было бы б недоступно или даже просто затруднено без употребления таковой (рекурсии).
Т.е. с самой идее
GarbageCollector г.но!
— я как бы согласен но роль рекурсии щетаю нераскрыта и более того щетаю (хотя и признаю не эксперт) таки в данной роли тщетна.
Они не криво связаны. Они оказываются рекурсивно связаны. И когда стек распутывается, объект может остаться — особенно если корневой объект имеет долгий срок жизни.
А без алгоритмической рекурсии сделать рекурсивно ссылающиеся объекты можно?
Можно всё. Только зачем? Рекурсивно ссылающиеся объекты для того и делают, чтобы каждый раз рекурсию не вызывать, а просто пройти по ссылкам. А вот собрать такой объект проще всего как раз рекурсией.
Мало того, если вы соберёте каким-то другим способом, вас не поймут. Код будет куда более громоздким и отвратительно читаемым.
Т.е. в джаве рекурсия применяет чтобы х.рить GC? #trollface
А события в них проливать? А обрабатывать события?
использовал не так давно в банальной задаче — импорт дерева категорий из csv файла. По-моему, иначе как рекурсивно задачу и не решить — нельзя быть уверенным в том, что на момент чтения очередной категории уже импортирована вся родительская ветка.
Очень редко, не помню когда в последний раз использовал. Но каждой задаче свой инструмент. Если рекурсия подходит для решения лучше всего — использую её.
Ніколи не використовую, embedded не місце для рекурсій! :)
«чи можна використовувати рекурсію при написанні firmware, і які наслідки з цього можуть бути» -
одне з елементарних запитань які задають на співбесідах.
Звичайно можна. Але зазвичай, не потрібно. Але embedded таки різний буває, і якщо з якихось причин там з′явилося наприклад 32Mb SDRAM — то чому б і не користуватися усім щастям програмування, включаючи С++ із його збирачами сміття. Можна навіть Java підняти.
чому б і не користуватися усім щастям програмування, включаючи С++ із його збирачами сміття. Можна навіть Java підняти.
потому что, кроме требований по памяти — есть ещё и требования по реал-тайму
включаючи С++ із його збирачами сміття
годная шутка я щетаю #notbad
у C++ відсутній збирач сміття.
Та й не зовсім розумію як він може допомогти, коли рекурсія переповнила стек який зіпсував певні області пам’яті.
у C++ відсутній збирач сміття.
На самом деле, есть: www.hboehm.info/gc /// в каждой шутке лишь только доля шутки
Незачот то что на си++ можно GC можно сделать не значит что он там есть. ))
ЗЫ: на си++ можно даже джаву сделать и даже (крестится староверно) джаваскрипт!
Ну не знаю, работать на C++ и без сборщика мусора — ну редкостный же гемор. Одно дело если там действительно ограничения железобетонные, реалтайм и всё такое. Но блин, цена ошибки? Так что если позволяет железо, то сборщик мусора лучше таки иметь. А если не позволяет — то и на C писать, нефиг туда с ООП приближаться. В том числе пользовать столь некошерные (но очень эффективные) GOTO.
лямбда #trollface
Ну не знаю, работать на C++ и без сборщика мусора — ну редкостный же гемор.
Это устаревшая информация. Сегодняшние умные указатели (unique_ptr/shared_ptr) дают почти такие же возможности, как и языки со сборкой мусора. В новом С++ (Rust называется) new и delete вообще убрали и оставили только стэк и умные указатели, и вместе с концепцией borrowing получилось вполне юзабельно.
А если не позволяет — то и на C писать, нефиг туда с ООП приближаться.
В геймдеве, например, и без ООП как без рук, и ресурсы железа очень ценны, поэтому либо C#, либо, если вам хочется нормального графона без framerate drops во время перекуров GC — только C++.
Ну прямо там лаги от того что очистятся 30кб чуть позже чем они перестанут быть нужны, нарукожопить можно на любом языке
Во-первых, геймдев — это таки рай по ресурсам по сравнению с маленькими коробочками. Которые, как ни странно, тоже надо программить. Вот когда напишешь приблуду под T2-приставку, расскажешь как оно — на коленке гигабайтами ворочать.
Умные указатели — древняя и проверенная технология. Но поверь, а лучше проверь — если ты сам не пользуешься деструкторами каждый раз когда забываешь об объекте — то кто-то таки должен его уничтожить. А достоверно выяснить что это мусор не помогут никакие гениальный указатели.
Сборщик мусора — уже далеко не такая древняя технология, и не останавливает всё и вся ради своей работы. Разве только ты сам его вызовешь, например для проверки на утечки памяти. А самостоятельный поток прекрасно умеет в фоновом режиме расстреливать большинство типового мусора. А по оставшемуся не-типовому идёт сортировка на поколения, то есть детальное расследование кто есть ху. И только когда с памятью уже совсем-совсем жопа, GC останавливает процессы и занимается авральной чисткой помойки.
В переводе на русский это значит, что нарваться на принудительный GC можно только если у тебя течёт память, откровенно мало памяти изначально, либо же ты сам его закронтабил (типично для сервера). В остальном же это такая няшечка, что я просто мечтаю об искусственном интеллекте чтобы у меня в доме кто-то так же аккуратно и быстро мог прибраться.
Вот когда напишешь приблуду под T2-приставку
Вот когда эти приставки научатся рендерить сцены в миллион треугольников, параллельно считая физику, тогда они и будут иметь какое-то значение в этом вопросе. До этого светлого момента они мне так же неинтересны, как и виртуальные машины Brainfuck с 3 килобайтами памяти.
Но поверь, а лучше проверь — если ты сам не пользуешься деструкторами каждый раз когда забываешь об объекте — то кто-то таки должен его уничтожить.
Очень интересно, спасибо, не знал. Осталось только понять, зачем об объекте забывать :)
Сборщик мусора — уже далеко не такая древняя технология, и не останавливает всё и вся ради своей работы. Разве только ты сам его вызовешь, например для проверки на утечки памяти. А самостоятельный поток прекрасно умеет в фоновом режиме расстреливать большинство типового мусора.
Что такое «в фоновом режиме»? Паузы на маркировку объектов всегда будут. Достаточно остановить главный поток на несколько миллисекунд, чтобы выйти за границы ограничения 16,6 миллисекунд на кадр, которое нужно для достижения 60 FPS.
Мне бы, конечно, и самому было бы приятно писать игры, не заботясь о подчищании памяти, однако реальность такова, что всем, кто пишет игры на C#, поясняют: не создавайте новые объекты в теле игрового цикла, переиспользуйте старые, не трогайте GC почём зря. Так было что пять лет назад во времена XNA (geekswithblogs.net/...-and-silverlight-too.aspx), что сейчас во времена Unity (docs.unity3d.com/...aticMemoryManagement.html). Единственная игра под Android на Unity, исходники которой я видел, чётко следовала этим принципам и большинство объектов там выделялись через object pools, но игроки все равно жаловались на FPS jitter и вылеты по OOM, и через год её сервера закрыли. Если у вас есть другой опыт использования GC — прекрасно, но лично у меня как-то не срослось.
Хм, вот тут как раз интересно было бы вспомнить про Go. Они обещают субмиллисекундные задержки на GC (точнее,
Везде, где деревья/списки списков. В принципе, стараюсь разворачивать в циклы — но иногда ленюсь.
В задачах различного закрашивания/обхода областей — разворачиваю в циклы.
Штирлиц попятился назад и напоролся на сук.
— Шли бы вы, девочки, домой — сказал Штирлиц ©
— Штирлиц, подумали сyки, подумал Штирлиц.
при полном переборе каких то вариантов очень часто, тапа дано 30 рейсов которые нада комбинировать по 4 и найти минимум функции (стоимость*время в пути), делается на рекурсии
Використовував як мінімум у двох випадках — деревовидні коментарі на сайті (коли в’юха коментаря викликає сама себе для відображення дочірніх коментарів), а також під час парсингу деревовидної структури на чужому сайті.
В останньому випадку слабо уявляю, як це зробити інакшим методом.
Взагалі, рекурсія, це дуже красивий і ефективний метод власне для роботи зі всякими фрактальними структурами. Тут важливо застосовувати її «в касу», а не куди попало, де можна обійтись циклом. Якраз хрестоматійний приклад — факторіал, який чомусь використовується у всіх підручниках для ілюстрації рекурсія — це те, що набагато зрозуміліше виглядає, якщо користуватися циклом. Рекурсія тут зайва. Про це Маконелл пише у своїй книзі, між іншим.
Я на своих проектах использую очень часто, но у меня очень специфическая область. В энтерпрайзе циклы только — больше ничего не надо было
define «использовать рекурсию», а то банальная сортировка использует рекурсию
Когда путь вызовов проходит через написанную тобой функцию заранее неизвестное число раз, но вероятно больше одного.
Во-первых, сейчас не
Ну и совсем уже мелочь: некоторые языки (особенно скриптовые) прекрасно умеют работать без общего стека. То есть рекурсить можно хоть до бесконенчости. Есть языки, позволяющие бесконечную рекурсию, если команда последняя. Ну и есть старые добрые инлайн-функции, функторы, и лямбды, которыми можно рулить как цыган солнцем.
Отдельный вопрос — рекурсии в JavaScript. Этот язык настолько через жопу особенно устроен, что его ещё 100500 раз перепишут и наклепают 100500 версий, которые разумеется надо будет поддерживать не только лишь все.
Вообще мой совет — прекратить беспокоиться по этому вопросу, просто использовать всякий раз, как они нужны. Но дважды подумать, прежде чем рискнуть обработать ВНЕШНИЕ данные рекурсией без счётчика итераций. Потому что всегда найдётся сволочь, которая подсунет нечто вроде
Во-первых, сейчас не80-е годы прошлого века, и переполнить стек надо ОЧЕНЬ постараться.
Я смог ) И даже без рекурсии ) Хватило спринга и авторизации )
И попытки поднять это на Arduino?
Пыфф, я смог npe в javac8 поймать
Во-первых, сейчас не80-е годы прошлого века, и переполнить стек надо ОЧЕНЬ постараться.
Многих С++ программеров — любителей _alloca() часто ждал нежданчик при использовании множественных потоков, у которых стек не резиновый, как у основного треда.
Ну многих «любителей программеров» вообще ждал нежданчик когда при использовании множественных потоков оказывалось что стек есть и что по памяти он тоже «что-то ест»...
ЗЫ: кстати отличный вопрос «а на многопоточность» «а стек?» начиная от «вот началась многопоточность а (куда делся) стек?» и продолжая «вот мы сделали объект в одном потоке а вот мы его передали в другой а вот мы его используем а стек?» или вот синьоры одной большой и сравнительно тёплой страны для таких передач так вообще глобальные переменные используют и ничего живут люди прошлый год $108 млрд. на экспорт сделали и ещё 50+ внутре...
ЗЫ: кстати отличный вопрос «а на многопоточность» «а стек?» начиная от "вот началась многопоточность а (куда делся)
Вторым и третьим вопросом можешь загнать в гроб любого сеньора: а какой дефолтный размер стека в потоке созданном через std::thread на его платформе и как его изменить. Правильные ответы: 1) хз, 2) никак. Правильный ответ для приёма на работу — я не использую std::thread.
Размер стека то ещё ерунда мне пришлось «инициалиализацию окружения» делать для работы одного окружения на потоках другого окружения ну чё через TLS побырику запилил прямо в рабочих задачах благо в нужном фреймворке оно оказалось совсем под рукой только тссс а то палевно... ))
ЗЫ: ответ «я не использую» я думаю не очень правильный хорошо бы понимания...
[Протирая глобус Украины]
— Так говоришь, будто глобальные объекты это что-то плохое.
Да изыди уже со своими жабным коллектором! ))
ЗЫ: но вообще мысль интересная надо бы посмотреть «отрешенным взглядом» и на глобальный scope в отношении локального я уже догадался если положить всё нужное окружение на начало стека то оно будет автоматически доступно всему остальному в том же ж потоке и даже будет сугубо локальным для этого потока включая время жизни но пока не придумал как половчее эту идею применить в том смысле что и не думал пока «так просто идея видимо годная».
ЗЫ: но это не жаба!!!
Если я не ошибаюсь, в JS уйти со стека можно через setTimeout(, 0). Но, если, как Вы пишете, какому-то умнику в очередной версии прийдет в голову на каждый такой вызов заводить поток, то будет черевато.
Сам встречал подобных «умников», когда рекурсия плодилась в бесконечном цикле из-за неправильного сравнения дат. Самое смешное, заметили очень не сразу. На продакшене с неделю проработало. И только при очередном плановом тесте, поймав производный баг, и добавив логирование — заметили сколько тысяч раз в секунду оно успевает отработать.
Даже не так, там круче бага: при ПРЕВЫШЕНИИ значения таймаута
Пример: при наступлении события браузер должен перерендерить календарь. И если событие оказывалось более чем через 25 дней — то календарь рендерился, и СНОВА запускал тот же таймаут.
рекурсия плодилась в бесконечном цикле плодящем бесконечные циклы
на проде бесконечные ресурсы? или все же циклы конечные? или не рекурсия?
Никогда. Всегда стараюсь вырефакторивать рекурсию в бесконечные циклы.
скорей всего это мартышкин труд, в большинстве высокоуровневых языков компилятор/транслятор сам развернет линейную рекурсию в цикл.
Опыт дофига лет. Ни разу не использовал. Реентерабельные функции, обработчики прерываний — часто. Рекурсию в чистом виде — не разу. Но я уже не программист, по сроку годности вышел.
нужно вопрос уточнять, те кто пишет на FP всегда используют рекурсию
Ок. Когда вы последний раз использовали рекурсию?)
Лучше использовать презерватив мёбиуса.
Да, Шрёддингера, конечно. Спасибо. Хотя, Шрёддера — тож ничо, если подумать.
Всегда есть риск совершить ошибку, когда ты не понимаешь зачем и для чего ты это делаешь! Это как с патернами, если лепить патерны ради ради самих патернов то и на выходе получите абстрактную фабрику абстрактных фабрик. А вообще KISS вам в помощь
Vasilij Tjorkin
Roman Gelembjuk
Alex Fogol
Vadim Kopanev
Eugene Varava
Gennady Dogaev
Nikolay Mihalych
Vasyl Yosypenko
Vasyl Yosypenko
Andriy Kunitsin
Mike Gorchak
mobile mobile
Матвій Шкотняр
Владимир Кожаев
Олексій Пєніє
Александр Шевченко
Sergii Pekarskyi
Dmytro Shchurov
Глеб Кузнецов
Artem Bondarenko
Dmitry Panfilov
Andrii Serhiienko
Васисуалий Лоханкин
Oleksandr Tkalenko
Alex Rock
Найкращі коментарі пропустити