Рекурсия что это. Рекурсия программирование. Рекурсия и цикл. Рекурсия с++. Для начинающих. Урок #43

by: #SimpleCode

Download this transcript

Transcript:

[0.0]
приветствую вас друзья меня зовут сергей мы с вами продолжаем изучать программирование на примере я закрасил + + и сегодняшняя наша тема это рекурсия прежде чем мы приступим с вами к изучению рекурсии хочу напомнить что у нас был прошлый урок урок подготовительный именно для того чтобы вам было легче понять что такое рекурсия там мы рассматривали что такое стек ну большей мере с точки зрения алгоритма его работы и если вы не смотрели то видео то рекомендую вам сначала его посмотреть но потом уже вернуться к изучению рекурсии в текущее видео ну а мы с вами приступим к изучению собственно самой рекурсии вообще рекурсии называют вызов программы самой себя либо как-то непосредственно либо косвенно в нашем случае рекурсия это вызов функции ей самой себя вообще обычно как пример работы рекурсии для новичков дают программку которая рассчитывает факториал числа но как по мне им этому может быть несколько сложно поэтому в этом уроке мы сначала разберемся с рекурсией самой по себе но в следующем уроке применим рекурсию вот к такому алгоритму как вычисление факториала числа как я уже сказал рекурсия в нашем случае это вызов функции самой себя поэтому давать или начал напишем какую-нибудь функцию наша функция будет называться фон она у нас пока ничего не будет делать и собственно я вам покажу просто как выглядит рекурсия в мы не мы вызываем нашу функцию первый раз она отрабатывает и в самом функции в самой функции и ее теле мы можем сделать наши вызов нашей функции еще раз что мы сейчас будем иметь как результат работа вот такой программы мы будем иметь очень нехорошую ошибку у нас все выпадет ну и на самом деле у нас скорее всего будет переполнение стека как я вам уже говорил в прошлом уроке где рассказывал плод про алгоритм стеком стык помещаются задачи данном случае у нас задачей которая помещается в стык выступает наша функция foo когда мы в мы не вызываем первый раз она помещается в стык обратите внимание я сейчас не буду полностью рассказать что такое стек эта тема предыдущего урока то есть я надеюсь что вы уже это знаете итак наша функция помещается в стек но результаты и работает мы получить не можем и поэтому вернуть ее результат на место вызова а также удалите функцию из стека и очистить память которая выделилась под нее мы тоже не можем именно потому что наша функция foo вызывает себя еще раз то есть наша функция фон который сейчас в стеке доходит ну вот вот этому вот моменту ее теле и снова вызывает сама себя поэтому к нам в стек опять добавляется новая функция foo это функция foo в свою очередь опять доходит до этого момента и снова вызывает сама себя но в итоге мы получается имеем вот такой вот вид когда мы доходим до определенного момента что в наш стек уже не помещается больше ничего вы в таком случае наша программа крошиться и выпадают собственно поэтому рекурсия как само по себе без какого-то условия выхода из нее бесполезно потому что это получается нечто вроде вечного цикла ну что к тому же еще и вызывает караш программу если мы хотя бы напишем допустим циклы while и здесь будет условия труп то есть вечный цикл наша программа к просто подвижника будет бесконечно выполняться мы хотя бы она не красится рекурсия же если мы хотя бы один раз и вызовем функцию которая рекурсивная и не имеет условия выхода просто вызовет у краж программы я не зря сравнил рекурсию с циклом обычно да даже не то что обычно любая задача которая может реализоваться с помощью рекурсии может реализоваться с помощью цикла ну и наоборот задача которая реализуется с помощью цикла может быть реализована с помощью рекурсии другое дело что ту или иную задачу может быть удобнее делать либо с помощью рекурсии либо с помощью цикла ну вот собственно расчета может того же самого факториала например удобнее делать с помощью рекурсии а также если уже еще более глубже копнуть как пример например работа с бинарным деревом тоже более удобно с помощью рекурсии например если вам нужно вывести все ветки такого дерева когда-нибудь мы тоже к этому моменту с вами пойдем но сейчас давайте вернёмся к нашей рекурсии у нас есть проблема что наша функция бесконечно вызывают сама себя поэтому мы не можем таким образом пользоваться рекурсией нам нужно условие при котором будет осуществляться выход из рекурсии поэтому наша функция foo должна иметь какое-то условие при котором она перестанет себя бесконечного вызывать давайте каким-нибудь образом эту штуку реализуем и посмотрим что у нас получится изменим нашу функцию так что она у нас будет возвращать целочисленное значение и принимать какой-нибудь и целочисленный параметр эй так как наша функция принимает существенный параметр а ты здесь при ее вызове нам тоже нужно что-то передавать допустим вначале при вызове мы будем передавать что число 10 возвращать наша функция должна какой-то результат работы но наша функция вместо того чтобы вернуть результат работы будет опять вызывать сама себя передавать туда опять же этот параметр и в итоге мы получаем сейчас такой результат такой алгоритм работы наша функция вызывается и в тот момент когда она должна вернуть какое-то значение мы опять вызываем нашу функцию фу и возвращаемое значение первого вызова подставляется возвращаемое значение 2 вызова вот именно вот здесь нам нужно добавить еще какую-то логику которая будет отвечать за выход из рекурсии из-за уменьшения на примеров этого числа ну а теперь мы добавим какой-нибудь условие для выхода из рекурсии к примеру если наша переменная эй будет равна допустим нет даже не равна меньше 1 то мы будем возвращать 0 и далее сделаем еще вот такую вещь и минус минус то есть декремент какова логика работы сейчас нашей рекурсии каждый раз когда мы будем выполнять хотя бы один раз нашу программу точнее нашу функцию переменная которая передается в новый вызов функции foo вот эта водка и будет меньше на единицу и когда-нибудь мы дойдем до такого момента что переменная эй станет равна меньше единицы таком случае у нас самый последний вызов функции вернёт 0 и мы начнём потихонечку выходить из цепочки рекурсии сейчас я вам на примере вот этого вот стыка который мы здесь нарисовали более подробно покажу как это все происходит ну а здесь для удобства мы сделаем салат который будет просто выводить состояние нашей переменной эй обратите внимание что изначально мы сюда передали 10 и каждую итерацию вызова нашей функции примерно и будет становиться все меньше и меньше и меньше пока не станет меньше единицы и собственно тогда мы выходим из рекурсии в данном случае получается что наша функция вызвалась 10 раз ну если вы заметили какую-то аналогию это что то типа того как отработал как работает какой-нибудь цикл да то есть мы просто ограничили количество итераций которая может быть нашей рекурсии теперь давайте немножечко сделаем меньше итерации для того чтобы нам было проще отлаживать нашу программу теперь у нас 5 итерации в нашей рекурсии и посмотрим в отладчике как это все работает чтобы уже точно удостовериться что там к чему ну а затем я вам объясню именно с вот это его точки зрения с точки зрения стыка как здесь все получается давайте наверно сделаем даже немножечко не так мы будем параллельно смотреть его отладчике и вот здесь на картинке ну тогда уж думаю будет предельно ясно что в чем у итак сейчас у нас первый вызов нашей функции foo мы туда передаем параметром нашу цифру 5 давайте сейчас вот здесь в нашем стеке отобразим как это все происходит вот это стык нашей программы сюда помещается одна задача данном случае вызов наших функции foo и сюда мы параметром передали цифру 5 вот это вот стрелка будет отображать направлении точнее очередь помещение задач вот это вот первая задача поместилась в очередь далее у нас будет вторая задача ну и так далее до 5 я буду здесь все это добавлять напомню что в стеке действует принцип последний зашел первым вышел то есть последняя задача которая попала стык выполняется самое первое то есть стыке задачи выполняются в обратном порядке относительно того каким образом они попали встык то есть вот это вот сдача которая сейчас передалось у нас 1 с переменной 5 она выполнится самой последней хотя попала сюда первых и так продолжаем вот у нас вызов нашей первой функции foo мы попали мы поместили в стек первую задачу с переменной 5 делаем шаг в нашем отладчике мы сейчас заходим в нашу функцию здесь условия выхода не выполняется потому что для того чтобы выйти из функции с нулем нам нужно чтобы наша переменная эй было меньше единицы у нас нас больше поэтому сюда мы не попадаем в этот ritorna идем дальше доходим до места где у нас значение переменной и уменьшается на единицу собственно вот она у нас уменьшилась и дальше у нас для отладки для удобства и seat который выводит нам состояние нашей переменной эй в консоль вот четверочка вывелось дальше наша функция которой мы вызвали по идее должна вернуть результат своей работы но на месте возврата результата ее работы у нас опять вызов этой функции этой же функции куда мы передаем опять переменную и который у нас уже стало на единицу меньше поэтому сейчас когда мы дойдем до вот этого ritorna он не может вернуть результат какой-то работаем потому что он зависит от того как отработать вот эта функция поэтому сюда ну не попадем а мы поставим новую еще в стек когда мы сейчас сделаем шаг вот мы его сделали мы ставим новую задача встык и на данный момент в этой задачи наша переменная уже равна 4 ну потому что в прошлый раз мы ее на единицу меньше давайте это же сюда и запишем четыре теперь снова та же самая логика наша переменная и уменьшается на единицу мы выводим ее в консоль и снова доходим до ritorna но а вместо ritorna как вы помните у нас опять вызов функции foo и мы туда уже перед этим эйс параметрам 3 целочисленным параметрам 3 обратите внимание что вы те задачи которые у нас были предыдущие 2 они там так и висят они никуда не делись сейчас вместо в памяти занимают потому что они могут решиться только после того как решится сама экране самой последней задачи и так новая итерация у нас добавляется еще одна задача опять вы за новой функции теперь уже по цифрой 3 и собственно и переменная и которую мы туда передадим в эту функции тоже будет 3 ну здесь уже отработанная схема и уменьшается единиц становится 2 опять доходим до вызова функции опять вызывается функция foo это уже у нас 4 раз но переменная которое мы туда передадим уже будет равно двойки следующем вызове переменная и уменьшается и становится уже равно единице мы опять вызываем функцию фу вот она и это 5 вызов здесь у нас переменная уже равно единица из этой функции опять вызывается новая функция foo и данном случае мы опять проскакиваем это условие и переменная эй уже равна 0 когда мы вызываем новую функцию fun так я здесь немножечко сильно с размахом поехал поэтому буду писать начни рисовать немножко поменьше мы вызываем еще раз функции foo но теперь уже с нулем это моль такой уже шестой раз заметить что все предыдущие функция до сих пор висят в стеке потому что они они друг друг от друга зависело от такой вот цепочки теперь вызывается наша функция foo последний раз почему последний потому что теперь уже наша переменная i равна нулю а у нас есть условие выхода из рекурсии она собственно гласит то что если переменная и меньше единицы то мы возвращаем 0 вот так как у нас функция возвращает целочисленное значение мы просто вернем ей 0 собственно мы сюда попадаем и давайте посмотрим что у нас здесь будет происходить мы вызвали вот этом месте еще один раз функцию рекурсивно это уже получается 7 раз и она у нас вернула 0


[978.509]
если что это слово return просто мне очень неудобно писать я немножечко не рассчитал с местом итак наша функция вернула 0 и что происходит данном случае с нашей рекурсии так как вот эта функция сейчас возвращает 0 в нашем стеке она уже считается как выполненное здесь у нас справа будут выполненные задачи здесь будет по порядку поступления здесь по порядку выполнения 1 выполненная задача мы и выполнили а так как на эту задачу выполнили вот это вот функция из которой мы вызывали вот эту функцию сейчас получит свой ritorna результат работы вот этой функции предыдущий 7 то есть 6 функция получить результат работы 7 вот мы кстати вернулись на вот этот вот рита рн и так как она получит свой результат работы то она тоже выполнится и у нас освободится место в стеке от этой функции я вам еще шаг и опять у нас получается последовательно закрываются наши функции и освобождается место в стеке ну и в памяти тоже еще шаг ну и собственно я сейчас здесь просто допишу вот в таком порядке дальше по выполняются наши функции аж до тех пор пока мы не дойдем до вот это вот место где мы передали в нашу функцию пятерку это мы сделали в мае не и сейчас в эту функцию самую последние вернется результаты ее работы вот здесь и на этом мы выйдем из рекурсии вот собственно такая вот штука рекурсия как видите видимо и все таки не зря рекомендовал вам пройти предыдущий урок чтобы понимать как работает стык потому что без этого понять как отрабатывает рекурсия мы просто невозможно как я уже говорил обычный новичок понимает что такое рекурсия да то есть функция вызывает саму себя на что-либо сделать с этим он не может но надеюсь вы такими не будете после моего урока и у вас и вам более-менее станет понятно что такое рекурсия конечно возможного сразу не сможете ее использовать все приходит с опытом но хотя бы понимание более глубокое понимание чем на каком-то примитивном уровне том что такое рекурсия у вас уже будет собственно на этом мы данную урока рекурсии закончим а в следующем уроке мы уже реализуем с помощью рекурсии что-нибудь полезное но собственно мы рассчитаем факториал числа с помощью рекурсии и я вам подробно объясню что как там происходит на что такое факториал и почему его выше точнее не то что лучше просто удобнее для программиста рассчитывать с помощью рекурсии но у меня на этом пока всё если вам понравилось это видео обязательно поставьте под ним лайк и конечно же подписывайтесь на канал чтобы не пропустить следующий выпуск всем спасибо за



Description:
More from this creator:
Понравилось видео или оказалось полезным? Подпишись! Рекурсия что это. Рекурсия программирование. Рекурсия и цикл. Рекурсия с++. Для начинающих. Урок #43 Если вам нравятся мои уроки, вы хотите поддержать меня и развитие канала, то можете сделать это тут! =) http://www.donationalerts.ru/r/simplecode

или тут https://www.patreon.com/SimpleCode

Уроки по программированию Наша группа ВК https://vk.com/smplcode

Подписывайтесь на канал https://www.youtube.com/channel/UCtLKO1Cb2GVNrbU7Fi0pM0w

Disclaimer:
TranscriptionTube is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to amazon.com
Contact:
You may contact the administrative operations team of TranscriptionTube with any inquiries here: Contact
Policy:
You may read and review our privacy policy and terms of conditions here: Policy