Есть только 3 ситуации для РЕКУРСИИ
HTML-код
- Опубликовано: 10 апр 2024
- erid: 2Vtzqwe64BZ | Успей воспользоваться кэшбеком 15% на регистрацию, ведь акция совсем скоро закончится!
Переходи по ссылке и вперед в будущее с Aéza.net: aeza.net/?ref=extremecode
Объясняю все риски рекурсии и поясняю в каких ситуациях её стоит использовать, а в каких нет. Самый полный гайд по рекурсии в языках программирования здесь.
---
Подпишись на наш Telegram Канал 🖤 t.me/extremecode
Лицензия Creative Commons Attribution 4.0 на использование трека Hyperfun (исполнитель: Kevin MacLeod): creativecommons.org/licenses/...
Источник: incompetech.com/music/royalty-...
Исполнитель: incompetech.com/ 
Наука
Братан, хорош, давай подпишись на наш Telegram канал, мы там байки и кулстори травим
t.me/extremecode
А для бустеров у нас есть эксклюзивный контент: boosty.to/extremecode
Рекурсия классическая, задачка Ханойская башня. Есть ли решения чисто циклами, не знаю, делать не целесообразно.
.386
.model flat, stdcall
option casemap:none
include msvcrt.inc
include macros.asm
.code
solve proc uses ebx source:dword, target:dword, interm:dword, n:dword
mov ebx, n
.if (ebx)
solve(source, interm, target, &[ebx-1])
printf("%d: %d -\} %d
", ebx, source, target)
solve(interm, target, source, &[ebx-1])
.endif
ret
solve endp
align_proc
main proc C argc:sdword, argv:ptr ptr, envp:ptr ptr
local N:sdword
mov esi, argv
.if (argc
ruclips.net/video/b4-MCm6Px2E/видео.html&ab_channel=Toshka
Ну чо имбицил,как ситуация с линуксом после запуска стим дека?
Каждый знает, что рекурсия - это точное повторение одного и того же действия, раз за разом, в надежде на изменение.
Ты цикл описал
Безумие
Это безумие
Это кайфарик
скорее рекурсия это когда ты открываешь холодильник, чтобы добраться до колбасы (база), но открыв холодильник, внутри ты видишь смузи и ещё один холодильник поменьше, открываешь его, и видишь авокадо и ещё один холодильник поменьше, и так n раз, пока не доберёшься до колбасы.
наконец добираешься до колбасы, и далее ты можешь её забрать (возврат при базовом случае) либо ничего не забирать (вернуть 0, null, None, ...).
Далее закрываешь холодильник, и опять, либо ты забираешь все эти отвратительные ненужные побочные продукты (смузи, авокадо...) (возвращаешь результат каждого рекурсивного вызова), либо выкидываешь (возвращаешь 0, null, None и т.п.), но холодильники надо обязательно закрыть все.
и да, ныряя в холодильник, ты должен пообещать себе, что добравшись до колбасы, ты перестанешь дальше открывать холодильники и начнёшь их закрывать (условие выхода)
Мне мой дед всегда говорил, что рекурсия нужна только там, где нужна рекурсия
stack overflow
Рекурсивное…
Владение рекурсией - это как владение кунг-фу, настоящие мастера не применяют его без необходимости...
🤣🤣
27 Хаскелль-разработчиков ликуют
лол. у нас в универе была одна дисциплина - "Перспективные технологии разработки программных средств". так вот, мы в рамках этой дисциплины потоком из 3-х групп должны были прочитать Курта и сделать задачки из книги. плохо было всем, особенно учитывая опечатки, косяки перевода и несколько раз невозможность решения задачи со знаниями, имеющимися на момент решения задачи.
26*
один которого я знаю нашел себе жену и пересел на нормальный язык
@@voodookiidoo 25. Михалыч не вышел из реанимации после кодревью.
один диз - мой, за хамоватость какую-то и пренебрежение всеми, кто другого мнения. Российский ютуб-с, что поделать, тут такой вайб.
На хаскеле не писал ни дня, рекурсию не люблю.
@@bxp_bass спасибо за информацию брат, нам очень важно твоё мнение и дизлайк, обязательно дай знать всем в комментариями если захочешь отписаться от канала!
Братан хорош, давай, давай, вперед, контент в кайф, можно еще? Вообще красавчик!
нпс
@@TIKTOKCRAZY Братан хорош, давай, давай, вперед, контент в кайф, можно еще? Вообще красавчик!
Надо было рекурсивно зациклить эту фразу...
@@mndtr0 как я вилкой зацикливать буду?
Чтобы понять рекурсию, нужно сначала понять рекурсию
Ее просто объясняют неправильно и не на тех примерах.
Есть несколько объектов со ссылками друг на друга. И из метода одного объекта ты дергаешь такой же метод другого объекта. Это самый частый пример применения рекурсии. Он интуитивно понятен и очень полезен, потому что деревья - наше всë.
Ну а qsort и фракталы самому писать никогда не понадобится. А если понадобится, то можно тоже сказать, что мы просто одну и ту же функцию применяем к разным элементам, что звучит максимально интуитивно. Но нет, надо обязательно какой-то шизы наговорить про то, что это якобы сложно
5:34 > решение через цикл более массивное и вообще остойное
Действительно, почему же оно такое массивное? Может потому, что добавилась проверка на 0, которая в рекурсивном решении куда-то проеблась, а может потому что ты расписал фор в ебучий вайл и начал жаловаться, что лишние счетчики добавились))
var result = 1;
for (var i = n; i > 1; --i) result *= i;
return result;
Жду того дня, когда бы мне не удалось написать задачу итеративно вместо рекурсии. Пока такого не было.
Я свой стэк берегу, ну его в пень.
Вообще, оценивать каччество кода по количеству строк - это удел питонщиков-первогодок на степике и литкоде. Старики понимают, что хорошая и понятная портянка всегда лучше однострочного оголтелого вандализма.
Факториал вообще плохой пример для рекурсии. Например на питоне вообще цикл можно свести к одной строке
def factorial(n):
return sum([i for i in range(n+1)])
Я думал действительно расскажет о 3х случаях когда без рекурсии не жить. Тема волнительная, иногда рекурсивное решение красивое, но нервничаю, до конца её непонимаю.
да и вообще, автор хамло какое-то, неприятно было смотреть. Второе видео подряд - и в обоих вайб "вы все говно, вы все не правы" А в другом видосе вообще мол CS, алгоритмы и база не нужны, кодить и собаки могут.
Зря я на русский сегмент развлекательного кодерского ютуба зашёл.
@@antizai. в этом и минус - надо мозг сломать, чтобы осмыслить (хотя, с опытом ваще разницы нет), а вот нервничать стоит - потому что сэндвич из вызовов до Юпитера в стэке к добру не приводит.
В общем-то я понял, что рекурсивные функции нужны для работы с рекурсивными объектами, довольно логично
С огромным нетерпением жду новых роликов! Прям всё в кайф
Приятно было почти ничего нового не узнать про рекурсию. Только для деревьев ей пользовался, но любопытно заметить, что нарисованное дерево из видео которое треугольное превращается в квадратное скорее всего не использует рекурсию, я такую штуку недавно тоже рисовал)
Дерево можно обойти и без рекурсии. Адреса узлов можно помещать в обычный стек, а потом, как до конечного узла дойдёшь, извлекать из стека адрес родителя и т.д.
@@Alex_Krivonogov то есть ты написал рекурсивный алгоритм используя вместо стека вызовов, стек дарованный тебе от Бога(стандартной библиотеки). Что фактически и означает, что ты не обошелся без рекурсии
@@daiske2867 На уровне синтаксиса - это не рекурсия, потому что нет вызова функции из самой себя. На уровне практического результата - это не рекурсия, потому что стек не забьётся. Кроме того, стек нужен только для обхода дерева в глубину, а для обхода в ширину используется уже очередь.
@@user-ur8hn1ux7i если вам принципиальна работа со стековым кадром для идентификации алгоритма как рекурсивный, то конечно это не рекурсия, но с другой стороны рекурсия нужна исключительно для взаимодействием со стеком, не важно каким. В эту копилку вопрос, а разве у обычного стека не может быть проблем с переполнением памяти?
Итого разница исключительно в типе стека, пусть это выдаст во мне ламера, но подскажите в каком случае принципиально иметь именно стековый кадр?
@@daiske2867 На уровне стековых кадров не существует понятия рекурсии, примерно как на уровне деревьев не существует понятия леса. Рекурсия определяется через вызов функций, который, очевидно, является более высокоуровневым понятием по отношению к стеку вызовов.
"Итого разница исключительно в типе стека" - главная разница в логике верхнего уровня из которой мы к этому стеку приходим, но и на нижнем уровне есть нюансы.
"разве у обычного стека не может быть проблем с переполнением памяти?" - конечно может, но это почти всегда память другого типа, которая по объёму в тысячи раз больше. Соответственно, в подавляющем большинстве случаев, просто переделав рекурсию на нерекурсию - мы избавимся от переполнения.
Кроме того, алгоритм с ручным использованием стека не обязательно полностью копирует логику стека вызовов. Например, рекурсивный поиск по дереву, после нахождения элемента, должен будет последовательно подняться до корня, тогда как не рекурсивный может выйти сразу.
Например, есть задача обхода деревьев: ее можно решать или через рекурсию и стек операционной системы, или через собственный стек на хипе. Так вот, стек на хипе будет медленнее из-за работы с системным аллокатором (его кэш блоков памяти под нагрузкой фрагментируется и требует кучу лишних операций). А вот стек операционной системы куда быстрее (хоть он и конечного размера). Но хорошая новость в том, что деревья редко вырождаются в списки и на стеке нам нужно место только под высоту дерева. Короче, рекурсия при обходе деревьев - хорошее решение.
Посмеялся от души, вот это подача! Братан, давай, давай ещё контента!
Я как 30 лет назад не понимал накрена нужна рекурсия - так и сейчас не понимаю. При вызове подпрограммы в стек заносятся не только переменные, но и адрес выхода из функции и регистры процессора (возможно не все - это как компилятор решит). А регистры сейчас по 64 бита. Когда процесс дойдет до конца рекурсии - ему придется каждый раз обратно прыгать в функцию, исполнять до точки ret и опять прыгать, очищая стек. Умотаться можно. Если там этих вызовов даже пару тысяч - сколько бредовой работы для процессора. Вот на МК стэк делают в байт 400-1кб. и такой ересью не страдают. Если чо сильно не пинайте - я не программист )
Чё? 😅
Полностью поддерживаю эту точку зрения
Хороший пример показан в видео: реализация алгоритма quicksort. Использование рекурсии позволяет существенно короче описать логику - такой код писать быстрее и проще, так как он понятнее.
Но ты прав насчёт лишней траты ресурсов (+ возможно переполнение стека, и иногда просто объективно удобнее использовать циклы). Злоупотреблять этим не стоит.
@@rainbowunicorn2946 Это красиво и понятно, но это жесть какая-то. Массив на 1000 элементов при такой реализации в памяти скопируется сначала в два вызова подфункции. Потом в них еще раз эти два кусочка скопируются в четыре кусочка. И так 10 уровней вложенности. И всё в стеке.
А. Ну и в худшем случае, стек может доходить до размера массива, если не повезет и массив уже будет упорядочен по убыванию и его надо будет развернуть. А значит из 4Кб чисел int можно вполне реально получить 4Мб. Это если нет ограничений на размер стека. А-то можно просто StackOverflow получить.
UPD: а не. Если я правильно понял, то можно будет получить 4МБ если даже просто отсортированный массив на вход подать. Тут нет проверки на отсортированность. А спихивать всё в левый массив, что меньше pivot, что в правый - если всё больше pivot. Разницы никакой.
@@MyOwnShadowEclipse спасибо за подробный анализ! Тем не менее, потребность в памяти не растёт так быстро, так как разделение массива производится не параллельно, а последовательно, и с каждым шагом на стек добавляется массив всё меньшего размера. При этом, когда работа с какой-то частью массива будет закончена, она будет убираться со стека. Затраты памяти в худшем (!) случае удвоятся, а в среднем - увеличатся на log (размер массива). Это можно пережить, особенно при учёте того, что на современных устройствах размер стека - сотни мегабайт. Да, перемещение кусков массива туда-сюда стоит времени, но это компенсируется тем, что операций для сортировки нужно совершить намного меньше. Экономия существенно превышает дополнительные затраты.
Братан, хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще? Рекурсия, такая рекурсия...
Хорош братан так держать, спасибо за контент, давай давай живи долго и процветай.
Братан, хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?
Давайте пока
Рекурсией удобно какие-то форматы парсить. Компиляторы писать, директории, данные от другой системы разбирать. И то если посидеть подольше, может быть через стек/очередь сделать лучше с конфигом отдельно. Но с рекурсией код будет проще и понятнее и легче поддерживать его. Отлаживать компилятор со стеком тот еще пиздец.
я уже думал накукарекать тут негатива на 10 страниц, но, досмотрев до конца, полностью согласен с автором! Рекурсия незаменима (лично для меня) при работе с деревьями. Во всем остальном она н**й не нужна!
И с деревьями ее можно заменить на циклы. Я часто для этого использую очередь или стек и итерируюсь по детям добавляя их в контейнер
Если узлы деревьев нужно по уровням обрабатывать, то циклом даже проще
Какой смысл в деревьях рекурсия, кроме упрощения говнокодинга?
@@TheRuthenium44 вырастишь- поймешь.
@@user-fc3gh1rb7w Кормен смотрит на твой говнокод, как на говнокод
Братан хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик!
С первым вариантом согласен. Иногда (примерно раз в пару лет) пишу рекурсию просто потому что хочу написать рекурсию. Хотя можно и без неё.
Иногда пофлексить рекурсией можно.
Братан,хорош,давай давай,вперёд! Контент в кайф,можно ещё? Вообще красавчик! Можно вот этого вот почаще?
Братан - хорош! Давай-давай вперёд! Контент в кайф! Можно ещё! Вообще красавчик!
Братан хорош, давай, давай, вперед, контент в кайф, можно еще? Вообще красавчик
""одна ошибка и ты ошибся"" как глубоко
переживал, что не будет рекламы, но порадовал. Для того чтобы понять рекурсию - нужно понять рекурсию !
Рекурсивно получается)
Братан, хорош, давай, давай, давай, вперёд! Контент вообще в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?
Братан, хорош, давай, давай, давай, вперёд! Контент вообще в кайф, можно ещё? Вообще красавчик!
Спасибо за видео, жду ещё!!!
За все время программирования у меня была ровно одна ситуация когда пришлось пользоваться рекурсией. Нужно было перебрать все папки и файлы(со всеми вложениями) в произвольной папке. Тогда я просто слямзил код с стак оверфлоу и ничего не понял.
А я запарился и сделал алгоритм копирования через цикл, а не рекурсию.
Классно видео, было бы оно раньше)
Нам на 2 курсе когда проходили рекурсию препод заявил, что все можно реализовать с помощью рекурсии, но не с помощью циклов.
Этот факт быстро опровергли книги и статьи в интернете 😢🎉
Братан, хорош, давай ещё, контент в кайф!
Прочитал первые 40 страниц SICP, и с кайфом смотрел.
лайк не глядя за стЕк! было так же прекрасно, как на семинарах по информатике.
Братан, хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще? Давайте, пока
5:20 - вариант с циклом, который показан позже, не может быть хуже по определению, учитывая то, что он хотя бы каверит 0. Не говоря уже о том, что вариант с циклом будто нарочно был удлиннён. Достаточно было засетить res = 1 и в вайле/форе множить пока число > 1
Братан, красавяик, давай, давай еще! Контент кайф... Ждем продолжение...
братан хорош, давай давай, контент в кайф, можно почаще!
Братан хорош, давай, давай, вперед, контент в кайф, можно еще? Вообще красавчик! Можно вот этого вот по чаще? Давайте пока
наконец то видео с хорошим соотношением трёпа и пользы - редко на этом канале такие попадаются нынче
Рекурсию следует использовать в метапрограммировании, при раскрытии шаблонов, чтобы сгенерировать код без рекурсии. Так же стоит использовать рекурсию, когда компилятор ее раскрывает самостоятельно . Как итог : красивый короткий и эффективный масштабируемый код.
Братан, МЕГАХАРОШ, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?
Перебирал файловое хранилище по папкам для сопоставления структур данных. Когда только сел, понял что циклом придется писать несколько сотен строк кода, а когда оформил через рекурсию в 10 строк понял, что такое кайф
Обожаю рекурсию, так же как и древовидные структуры данных. Интеграция, миграция, отложенная инициализация таких данных в UI.
Один из лучших монтажей которые я когда-либо видел !)
Бро ты лучший!! чуть со стула не упал
Писал сапёра на реакте (ради эксперимента). Игровое поле у меня представляло собой матрицу структур, каждая из которых хранила значение текущей ячейки и пару логических переменных, отвечающих за состояние ячейки (закрыта - открыта, флаг есть - флага нет, и т.п.). Самой сложной задачей для меня стало цепное открытие ячеек - когда игрок нажимает на пустую закрытую ячейку, все рядом стоящие пустые ячейки должны автоматически открыться вплоть до ближайших ячеек с цифрами, стоящих сплошной линией, либо до конца поля, если ячеек с цифрами рядом нет. В голову кроме рекурсии ни одна мысль не приходила, да и без раздумий вполне логично, что циклически выполнять цепное открытие ячеек будет сложной и ненужной работой. В результате у меня получилось. При нажатии на ячейку, игра выполняла функцию открытия текущей ячейки и запускала её относительно восьми соседних ячеек, если они являлись пустыми. Таким образом, механика была реализована. Рекурсией пользуюсь не часто, но конкретно в этом случае она мне очень сильно помогла.
Интересно поделился своим примером использования рекурсии. Я тоже могу своим поделиться, но нахер это кому-то надо. Скажу лучше вот что: "Рекурсией пользуюсь не часто ... ", - так сказал, будто это какой-то предмет, который вот на столе лежит, и мы либо используем его, либо он лежит и мы его не трогаем. В данном случае этот предмет - это именно что КОГДА МЫ ВЫЗЫВАЕМ ФУНКЦИЮ ИЗ ЕЁ ЖЕ ТЕЛА. Т.е слово "рекурсия" в этом комментарии использовано в смысле что: "рекурсия - это когда в коде мы делаем так".
Иными словами я хочу сказать, что в данном случае у слова использован один из множества смыслов, всё. Обозначать словом "рекурсия" можно еще много чего еще. И интересно, что люди часто ОБЩАЮТСЯ одним и тем же словом, но каждый из двух использует его в ОТЛИЧНОМ смысле, и ОБА при этом этого не замечают, и получается шизоидный цирк, который для участников не заметен, что они общаются вдвоем, но на самом деле сами с собой.
Это я щас дал бесполезный комментарий на бесполезный комментарий на бесполезное видео.
@@tayzlelavarez6848
В одном из смыслов - рекурсивно получается)
Я бы это реализовал через буфер ячеек. Пока буфер не пуст, достаём одну ячейку, и если на ней 0 и она не открыта, открываем ячейку и добавляем соседние ячейки в буфер по тому же условию.
@@tayzlelavarez6848будь немного проще) Это всё сплошное "буквоедство". При недопонимании всегда что-то можно уточнить, а не стараться вложить в одно слово миллион смыслов. Для меня рекурсия и есть ситуация, когда функция вызывает сама себя. Соответственно, "рекурсией редко пользуюсь" - редко использую вышеописанный принцип.
Видео в целом, мне кажется, не имеет столь серьёзного направления. Разумеется, автор хотел что-то сказать, он это сделал, но видео явно на приколе, а не какой-нибудь урок по использованию рекурсии. Поэтому и комментарии тут выглядят как беседа на курилке. Я лишь захотел написать своё отношение и свой опыт. Кому надо - прочитают, не надо - пролистают. Я просто поделился мнением и ситуацией)
@@FoxSlyme нуу, учитывая то, что у меня был двумерный массив, я не заморачивался, и просто пускал рекурсию по соседним ячейкам)
Братан хорош, можно почаще, да, вот это всё
Разные типы рекурсии определяют ещё потому, что есть разные методы трансляции и оптимизации рекурсии в машинный код. Дроп зе майк!
Факториал можно найти через тот же цикл for(непонятно, что автор там нелаконичного наговорил):
int fact(int n){
int res = 1;
for(int i = 2; i
а любой цикл можно реализовать через рекурсию, и что? Польза рекурсии в тому, что в некоторых задачах она значительно облегчает роботу
с другой стороны, в функцию можно всегда прокидывать глубину стека и останавливать при больших значениях.
Зависит от яп. Обычно, рекурсия медленнее
Братан хорош, давай, давай, вперёд, контент в кайф, можно еще вообще красавчик можно вот этого вот почаще давайте пока
У Тимофея Хирьянова в плейлисте по алгоритмам и структурам данных на с++ есть 3часовая лекция на эту тему, и определение такое же как в видосе)
А вот это реально интересно, давай вот подобного почащ
Люто, бешено аплодирую, братан, все дела, ты молодец
Не только для работы с деревьями.
Есть у вас, например, многомерный массив (или многообразие в многомерном пространстве). Допустим, вам удалось написать такую функцию, что она за один шаг рекурсии понижает размерность задачи на 1.
Поскольку многомерные массивы растут в объёме очень быстро, то глубина рекурсии никогда не будет большой (скорее память для данных кончится, чем глубина рекурсии превысит 6 или 7).
Короче говоря, когда глубина рекурсии растёт не очень быстро (не быстрее чем log от объёма данных) - не грех её использовать.
А деревья - это просто частный случай этого условия.
Тоже об этом подумал.
Бро норм говоришь, сюжет от души, говори ещё и по чаще
Братан, хорош, давай давай, вперёд кайф. А вообще правда очень люблю твои видосы, они мемные и смешные, а больше мне и не надо (разве что придумаешь как интегрировать сиськи в ролик и чтобы уже полезная информация не утекала мимо ушей из-за большой потребления сиськами количества памяти и внимания, что сложно)
Очень самокритично, уважаю
Братааан, хорооош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?
Гистерезис например в ОУ идеальный случай рекурсии в устройствах подавления шумов и дискретизации сигналов. Сигнал не может изменяться резко на большой частоте, поэтому такой вид рекурсии облегчает подавление шумов. Рекурсия используется в TS и D триггерах которые образуют запоминающие ячейки. Именно симметрия рекурсивности(рекурентности) позволяет нам создавать регистры, оперативную память и т.п. то есть компьютеры
Хорошо рассказываешь. С удовольствием поработал бы с тобой.
Использовал рекурсию только на маленьких функциях (которые вызывают сами себя), которые легко понять, в остальном противник подобного, ибо спасибо, надебажился.
Из сложных рекурсий только в темплейтах плюсовых, не скажу что рад этому, но там без вариантов, надо ждать рефлексию.
С мнением автора по рекурсии согласен полностью.
Только я подумал использовать рекурсию в своём говнокоде на сишечке и тут попадается Ваше видео. Чуть стек себе не порвал от такого.... Спасибо
Я делал рекурсию на пайтоне во время учёбы.
Ещё она нужна на ЕГЭ для задания с рядами (те же факториалы, ряд фибоначчи и т.д.)
Огонь, братан молодец.
6:20 - я больше скажу -РАЗМЕРНОСТЬ стека фиксирована и равна единице (одномерное пространство).
А вот с размером да - беда :)
спасибо за водичку, захлебнулся.
Не сильно глубокую рекурсию еще мб можно в обфускации заюзать, это как удар по яйцам, красноглазик расковырял функцию, а она на определенной итерации начинает работать иначе)
Братан, хорош, давай давай вперёд, контент ваще в кайф!
Харош, зараза. Я б в 10 минут не вложился, но ведь нечего и добавить после тебя - пойду падованов подпишу на тебя.
Фактически рекурсия нужна только для вложенных структур и рекурсивных алгоритмов, и в основном в случае, когда ручная организация стека накладна в плане отладки и читаемости кода.
Например, когда глубина не известна, то есть нет возможности стартовать с точки конца рекурсии.
гномик-циклокрад - фраза дня 😆. Давай братан, хорош
Занималась прогой только в школе, половину слов не понимаю, но рассказываешь классно
круто, спасибо!
всё по фактам, разнёс и объяснил
Всем адептам рекурсии:
удачи фиксить баг в функции с хвостовой рекурсией без тестов(было такое 1 раз в жизни). Я тогда проклял все: и ЯП, и автора кода, и авторов ЯПа, и ЭкстримЦоде задодно.
О нет. Нормальная рекурсия что, должна иметь возможность логировать информацию?
@@user-fh3wg8oj6q
А это уже не адепт. Адепты так не могут.
когда-то делал систему продажи билетов через промоутеров - и директору понадобилось сделать систему кураторства, типа привёл прома и потом получаешь пару процентов с его дохода, и с того, что этот пром заработал на кураторстве и т.д.. до этого рекурсиями не баловался, но тут она пришла сама собой
Рекурсия в реальных проектах часто используется в формате паттернов компоновщик и визитёр. Самый яркий пример, это работа с файловой системой и любой древовидной структурой в которой есть разные типы сущностей.
угу, да тот же xml обработать
рекурсию в основном на собесах только спрашивают. граф, связный список или дерево обойти. в динамическом программировании еще часто используются. в случае продакшена лучше реализуйте обычный LIFO стек все же. это понятнее и безопаснее
Параметры во многих языках программиривония передаются на стеке, так что с точки зрения стека второй пример с параметром-аккумулятором мало чем отличается от первого.
Он отличается тем, что это хвостовая рекурсия, и она автоматически компилируется в цикл.
ООО, я тоже только в переборе дерева использовал😄
Goto - юзать можно в очень низкоуровневых языках, как в целом и рекурсию, но например в питоне js и всяких интерпретируемых медленных языках лучше не юзать ничего кроме циклов, т.к. рекурсия там сильно ограничена и ты будешь постоянно ловить эксепшены, а готу вообще - хз есть ли в таких языках
Вот и я не понял к чему он о goto так высрался. Видать наслушался "умных" блогеров)
+100500. Интерпретатор явно не предназначен для рекурсии: в глубокой теории варианты "с рекурсивным вызовом" и "без рекурсивного вызова" отличаются тем, что в случае рекурсивного вызова функции помимо данных в стек идёт некая дополнительная инфа (адрес возврата, регистры, ...), которая отнимает время и место в стеке. Если второе не очень болезненно (в большинстве случаев стек "бесконечен", если это не какой-то микроконтроллер), то первое тупо жаль. За эту потерю времени хочется иметь какую-то компенсацию, например, упрощение циклов или что-то подобное. В случае интерпретирующих ЯП падение производительности при рекурсивном вызове функций настолько высоко, что компенсации не будет (лично я не видел таких случаев).
Оч хорошо объяснил. Теперь буду трясти этими знаниями перед умниками рекурсионщиками
Все понял и очень интересно! Спасибо за контентъ. Братан хорош, давай еще, вперед назад лево право удар
Thanks bro!!!
А если у сложной структуры динамической вложенности вложенность окажется слишком велика, чтоб рекурсия не переполнила стек?
УРААААА, НОВОЕ ВИДЕО
В 5:57 quicksort через рекурсию выглядит красиво, но на деле говно, потому что хороший quicksort должен сортировать массив in place, а у тебя он кучу новых массивов создаёт. Тут конечно дело не в рекурсии, хотя в итеративном решении quicksort реализован вроде как правильно
6:36, лучший вариант избегать - это вынести в одну переменную и скидывать ссылку на неё.
Допустим у нас есть факториал
int factorial(int* value) {
if (*value == 1) {
return 1;
} else {
return *value * factorial(&(*value -= 1));
}
}
К сожалению я не могу с уверенностью сказать, что данный метод работает, нет под рукой компилятора C
При использовании переменной-аккумулятора "acc" стек все-равно засерается точками выхода из метода. Если глубина вложенности изначально не известна, то нужно использовать только циклы, иначе через некоторое время получите переполнение стека
Если язык с tail call optimization - то нет. Функция по факту будет вызвана один раз.
По факту, эта самая TCO сводится к преобразованию компилятором в плоскую итерацию. Он просто делает это неявно. Разработчику остаётся надеятся, что он не накосячил, и написал свою рекурсию способной к TCO.
братан, контент огонь, давай также
Братан, хорош, давай еще
Когда во время цифрового анализа (это там где миллионые циклы) решил с дури через рекурсию сделать и получил смачный мат от компа, понял что рекурсия как ром, по немногу приятно а если переборщить то можно в Челябинске очнуться.
Юзаешь вместо рекурсии контейнер с очередью или стеком и заебца. Ещё не много capacity намазываешь исходя из каких-нибудь соображений
Сниму видео про то, как этот канал снял видео про рекурсию
Господа, я всё понять не могу, а разве реализованный вариант с парамметром аккамулятором не будет точно так же засирать стек? только теперь мы до самой последней рекурсивной ступени храним не только переменную n, но и переменную acc? почему вдруг мы их перестали хранить на каждом шагу?
ООО, кстати по поводу рекламки AEZA ну типо сам их юзаю. Фрау VPS имею, и VPN накручиваю только в путь. Так что рекламка не дурная, не то что галимые курсы от скилбокс и скилфэктори. Типо вот ну правда aeza норм.
Пришёл к выводу, что рекурсия может быть полезна для реализации синтаксического разбора формул.
Так, т.е. в js хвостовая рекурсия будет работать? Или просто количество вызовов будет больше, перед тем как стек порвется?
нет, он для примера код привёл в js, но в нём этого нет. Насколько я знаю, в scala такое есть
Если вы решили разрешить проблему с помощью рекурсии, то теперь у вас две проблемы = )
Искусство - это РЕКУРСИЯ!
если можно использовать reduce я использую reduce