Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 9
В основе работы всех компьютеров лежат рассуждения о Машине Тьюринга, а доказательство её работы основано, в том числе, и за счет использования рекурсии, и очень жаль, что многие забывают, что это чистая математическая абстракция.
Ужасы рекурсии.
Скрытый текст
Обнаружился у меня как-то геморрой. Я боюсь медицины и операций, но терпеть больше не мог, что поделать, согласился на лазерное прижигание. Оно под местной анастезией происходит, так что терзания скорее психологические, полежал, надел штаны и домой. Меня предупредили, что самое суровое будет потом, когда первый раз сходишь в туалет. Поэтому я оттягивал этот момент подальше, старался есть поменьше, но вот оно наступило. Когда процесс закончился, я встал и решился посмотреть на результат. Вы, наверное, слышали выражение "пердак бомбанул", оно лучше всего описывает то, что я увидел: ошмётки крови и отходов жизнедеятельности разлетелись по унитазу. Увидев это, я чуть не обосрался, но вовремя сдержался, поняв, что это создаст рекурсию, и не простую, а, так сказать, "хвостовую". В чём же мораль этой истории? В организме и в рекурсии очень важно, чтобы правильно работал выход.
Извините.
"напишем два неэквивалентных кода и свалим всё на рекурсию". Я не понимаю, почему вы постоянно зовёте имлпментации без единого рекурсивного вызова рекурсиями. Это не считая того что зачем-то ещё и стек впендюриваете, хотя он там нафиг не нужен ни в одном из вариантов. Ещё и циклы никак не ограничены.
Лично мне чтобы понять как это работает и написать эквивалентный код потребовались и отладочный вывод и пошаговый разбор в отладчике и всё равно это оказалось не просто, потому что много нюансов.
ну не знаю, пробовали открыть учебник пятого класса и посмореть как работат степени? Ну и такое свойство как ассоциативность умножения вроде тогда же рассматривается, а то и ещё раньше. Как у вас из этого внезапно ДВА цикла появилось вообще не понимаю.
Ну, и основной прикол в том что правильная рекурсивная чистая функция отлично оптимизируется в цикле, в отличие всего того ахутнга, что вы понаписали. Ключевое слово - чистая, что прямо противоречит вашему желанию зачем-то впихнуть в неё ещё что-то, поломав скорость работы на том же спекулятивном исполнении на процессоре.
Я не понимаю, почему вы постоянно зовёте имлпментации без единого рекурсивного вызова рекурсиями.
В смысле без единого? - везде под "код x.2" идёт пример с рекурсией, а сопровождающие его два примера с циклами иллюстрируют как это нормально запрограммировать и что на самом деле делает рекурсия если посмотреть её под пошаговым отладчиком и/или через добавление отладочной информации.
Это не считая того что зачем-то ещё и стек впендюриваете, хотя он там нафиг не нужен ни в одном из вариантов.
Затем что рекурсия Всегда неявно использует стек процессора и в данных примерах делает это именно так как описано в статье, но если смотреть только на код рекурсии не пытаясь вникнуть в происходящее то этого не видно. Об этом и статья что "вы не видите суслика, а он есть!"
Ещё и циклы никак не ограничены.
При применении рекурсии всегда "автоматически" формируется как минимум два (может значительно больше) "псевдоцикла" и программист никак не может на это повлиять или оптимизировать. Точнее может если откажется от рекурсии.
Категорически не согласен со статьей. Главное возражение: учите, блин, матчасть. Почитайте про динамическое программирование, про обход в глубину. Тогда вся эта непонятность рекурсии быстро улетучится. Да, если не знать алгоритмы и computer science, то их писать и понимать будет сложно. Но это не проблема алгоритмов и рекурсии.
Рекурсия часто позволяет писать более простой и понятный код. Как то же возведение в степень в виде рекурсии гораздо понятнее. И выводится напрямую из арифметики. Тривиальная же логика x^2k = (x^k)^2 = (x^2)^k, x^(2k+1) = x(x^k)^2 = x(x^2)^k. И переводится в код напрямую, сначала с двумя случаями четного/нечетного, а потом их можно объединить для краткости кода.
Обход графа в глубину без рекурсии написать сложно и непонятно, почти любая работа с древовидными структурами данных в виде рекурсии получается читабельнее и понятнее.
Да, у рекурсии есть накладные расходы - вызовы не бесплатны, тратится стек. Но часто это тривиальная цена за более простой код, а иногда рекурсия даже оказывается быстрее. Например, в динамическом программировании рекурсивная реализация обходит только достижимые состояния, когда как реализация циклами снизу-вверх обходит вообще все. И во многих задачах достижимых состояний гораздо меньше чем вообще возможных, в результате чего рекурсивная реализация заметно быстрее, даже несмотря на накладные расходы на вызовы функций.
Да, пихать рекурсию туда, где это не надо - не надо. Как не надо городить фабрики билдеров фабрик или ассемблерные вставки там, где это не надо. Это не какая-то особенность рекурсии, это про целесообразность применения инструментов.
И переводится в код напрямую, сначала с двумя случаями четного/нечетного, а потом их можно объединить для краткости кода.
Да у меня там есть ссылка на эту логику с чётностью / не чётностью и комментарий к ней: "Однако с логикой там всё мутно и сложно - много букв и формул, а в конструкции 
усматривается сакральный смысл по преобразованию нечётных чисел в чётные, хотя на самом деле вычитание единицы из нечётного числа обнуляет младший двоичный разряд, а целочисленное деление на два этот младший разряд отбрасывает независимо от того был он предварительно обнулён вычитанием единицы или нет. "
почти любая работа с древовидными структурами данных в виде рекурсии получается читабельнее и понятнее.
Про древовидные структуры будет в следующих частях. Есть что сказать, но пока не буду спойлерить.
Но часто это тривиальная цена за более простой код,
Примеры с очень дорогой и главное неочевидной ценой тоже будут в продолжении. Причём цена там из серии когда в супермаркете выбрал товар по выгодной цене, а на кассе пробивают чек на цену х10 или х1000.
На простых задачах это неинтересно. Попробуйте сравнить на более сложных, особенно где есть нетривиальное состояние. Например:
quick sort: его, конечно, можно написать без рекурсии, но код будет, мягко говоря, нечитабельным
задача с литкода про восстановление дерева по его inorder и preorder. Решается элементарно за 5 минут с помощью рекурсии, в 5 строк кода на питоне. У нее есть нерекурсивное решение, в чем-то изящное, но оно сильно нетривиальное, и там надо додуматься до хитрого инварианта того, что пихать в стек.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Антирекурсия. Часть 1