#41. Рекурсивные функции | Python для начинающих

[@youcandoit1559]

Урок классный, за пол года смотрю уже восьмой раз) Возможно когда-нибудь пойму. Спасибо

[@xrilicc1154]

Как успехи? Пробовали конспектировать материал?

[@youcandoit1559]

@@xrilicc1154 Вроде бы, с рекурсией прогресс есть🤘Понял про стек вызовов при рекурсии, разобрался в базовом и рекурсивном случае. Порешал еще немного задач🤏 Поэтому успехи есть💥

[@xrilicc1154]

@@youcandoit1559 отлично, я рад за вас! :)

[@андрейхоменко-и5я]

Открытый перелом мозга с необратимыми процессами.

[@garalexalex9007]

Да вроде не такая прям сложная тема, в отличие от циклов тех же.

[@Combo_killa]

@@garalexalex9007 ну хз, циклы это просто, а тут уже 4й день разбираюсь и не могу разобраться

[@FromJWtoJesus]

@@Combo_killa Каждая функция когда работает сверху вниз не отрабатывает до конца, а только до места где мы вызываем ее рекурсивно, а стоящий ниже print(value) "зависает", там как бы точка останова остается. После того как дошли до самого низа, python начинает возвращать выполнение кода к тому месту (точке останова) откуда была вызвана функция полностью завершившая свою работу, таким образом мы поднимаемся снизу вверх, попутно отрабатывает оставшийся в каждой функции print(value). При этом value в каждой функции имеет свое значение. Поэтому и получаем 3 - 2 - 1 То есть любая функция должна отработать до конца, поэтому Python возвращает нас рекурсивно вверх.

[@Combo_killa]

@ спасибо

[@86Blind]

Как же классно объяснена такая сложная тема. Здорово!

[@paleface_brother]

Большое спасибо! Ещё ни разу не встречал такое наглядное и доступное объяснение 👍🤝

[@coffeeglek6773]

Отличный урок. Тема дается несложно, если подходить к ней аккуратно и размеренно

[@utka111]

Согласен. Чтобы лучше понять, надо посмотреть несколько раз через день-два, например. И обязательно своими руками писать код. Это важно. Писать надо по памяти из видео, а потом добавлять свои фишки и "играться". Очень полезно при этом пользоваться отладчиком и пошагово следить, что происходит в программе

[@DmitryTimofeev]

Ура! Неделю разбирал последний пример и сегодня наконец досконально понял, как он работает. Спасибо за урок!

[@ПавелАнаньев-я2к]

Сергей, благодарю! Как всегда всё очень понятно и просто! Особенно за пример с файловой системой - очень круто красиво наглядно👍

[@diplomdeady]

Сергей, спасибо за ваши труды!

[@logdan]

добра и здоровья тебе! никакие скил боксы не тянут по качеству подачи!! СПАСИБО!

[@ZZZ5204]

Одно из лучших объяснений рекурсивных функций

[@Чуваш-ы3ц]

недавно я понял, что рекурсия мне начала нравится, я просто понял как она работает, благодаря лекциям автора в том числе) ну и после перечитывания "Грокаем алгоритмы". Ранее эту тему не допонял. Спасибо)

[@_mrmark]

Пересматриваю регулярно. Почему нельзя каждый раз лайк поставить? )

[@DmitriyKarpov-b1i]

То есть выполняете рекурсию. )

[@sofiipochta]

Спасибо, посмотрела!

[@ivanlino3747]

Спасибо большое, очень наглядно и как всегда интересно! Если есть возможность, было бы здорово посмотреть про хэш - функцию 🙂

[@eugenedukatta9355]

А что про хэш-функцию? Хэш-функция это функция в смысле математики, а не программирования. Это в общем смысле свертка данных любого размера к ограниченному размеру, по особому правилу (алгоритму). Таких функций можно придумать стотыщьпицот! Например, берете любое число любого размера и складываете его цифры. Если в сумме получилось число больше 99 - повторяем, и так далее. Как только получится число меньше 100 - останавливаемся, полученное число и будет результатом, называемым "хэш" от исходных данных. Пример: число 895475289549999278, складываем цифры получается 119 складываем еще раз получается 11. Это и есть хэш от числа 895475289549999278 Это примитивный пример. Настоящие используемые на практике алгоритмы более сложные.

[@slizverg23]

Сергей, в целом ваш контент пожалуй действительно лучший в рунете(да и не только), но ваш нейминг переменных… for f in path - тема и так непростая, а тут ещё и гадаешь мысленно, что за f такой:) Наверное, с опытом на такие вещи просто не обращаешь внимания, но новичкам было бы проще понять например: for folder in path - гораздо читабельнее же, хотя и длиннее на пару байт:) В целом же огромное спасибо за ваш труд)

[@PavelNebo]

Душнила

[@archibaldivanovich4103]

как chat объяснил Функция get_files рекурсивно обходит иерархию каталогов и файлов, описанную в словаре F, и выводит названия файлов и каталогов на экран. Аргумент path содержит текущий уровень иерархии (словарь с названиями файлов и каталогов и их содержимым), а depth - текущую глубину рекурсии (сколько раз функция вызывала сама себя). На каждом шаге рекурсии функция выводит название текущего файла или каталога, а затем проверяет, является ли содержимое текущего элемента словарем. Если это словарь, то функция вызывает сама себя рекурсивно, передавая в качестве аргумента содержимое элемента и увеличивая глубину рекурсии на 1. Если содержимое элемента - список, то функция просто выводит список с отступом.

[@olegkomlev]

Терминология. Если рекурсивная функция вызывает саму себя, то это ПРЯМАЯ РЕКУРСИЯ. А если она вызывает какую-то функцию, а та функция вызывает первоначальную - это КОСВЕННАЯ РЕКУРСИЯ. Может быть и более глубокая косвенность - одна функция вызывает другую, другая - третью, и т.д., а какая-то в этой цепочке вызывает первоначальную. Если функция делает не более одного рекурсивного вызова (т.е. либо возвращает результат, либо вызывает себя 1 раз), то это ЛИНЕЙНАЯ РЕКУРСИЯ. Если нарисовать вызовы такой рекурсии, то видим, что они выстроены в одну линию, а потом по этой же линии будет происходить возврат (в начале урока это наглядно показано). Функции recursive и факториал fact, показанные в уроке - примеры линейной рекурсии. Частный случай линейной рекурсии - ПОВТОРИТЕЛЬНАЯ РЕКУРСИЯ (называется также концевая или хвостовая рекурсия - tail recursion). Это если функция либо возвращает результат без рекурсивного вызова, либо делает рекурсивный вызов и сразу возвращает результат этого вызова, никак его не меняя и ничего больше не делая (рекурсивный вызов - последняя операция перед возвратом). Такая рекурсия легко может быть заменена циклом. Многие компиляторы опознают повторительную рекурсию и заменяют рекурсию на итерацию. Но, насколько знаю, Питон этого не делает (по крайней мере, несколько лет назад Гвидо Россум выстапал против такой оптимизации). В функции recursive рекурсия неповторительная (фунция выполняет print после рекурсивного вызова),. А функция fact модифицирует результат рекурсивного вызова перед возвратом (умножает результат на n), поэтому эта рекурсия тоже не повторительная.

[@gairatakbarov9422]

Этот комментарий надо закрепить я считаю

[@vladimirkulakov6126]

Упражнения по рекурсивным функциям давались непросто)

[@aleksandr_nokhrin]

отличный практический пример !

[@andredru4278]

Спасибо. Хорошие примеры.

[@ВладиславАндреев-э8т]

На десятой минуте мозги закипели! Придется пересматривать, потому что на элементе path[f] мозги ломаются, хотя принцип вроде понятен до этого момента За труды большое спасибо

[@lun4ik739]

СПАСИБО!

[@newvanya]

Интересно, почему в примере факториала , значение n не пошло в отрицательную сторону, ведь условие все равно выполнится

[@user-tv9xp7uf6z]

Этот парень гений, лучше него никто не может объяснить

[@Dmitrii-Zhinzhilov]

Благодарю! 👍🔥

[@romanbush5164]

Про рекурсии знал, а про обратный ход нет, 🙂

[@oopsimath]

else в вашей функции вычисления факториала избыточно, а условие должно проверять n == 1

[@jamjam3337]

спасибо!

[@return_1101]

Боюсь представить что ждёт меня на практические задания.

[@sergeyv1534]

Класс!

[@oleksiy.tryfonov8]

Подскажите, пожалуйста, если нет ветвлений, почему именно if используется, а не while?

[@Psoglawec]

Сам смысл рекурсии понял там где с числами (обратный процесс закрытия). А вот со словарём никак понять не могу, как происходит погружение в глубину?

[@sergeyshestakov607]

спасибо помогло!

[@ЗНАКОМЫЙСВАРЩИК]

Подскажите, не совсем понятно в случае с факториалом за счет чего останавливается рекурсия.

[@crok4u]

За счет if´a.

[@iiepe1915]

Спасибо за видео, все понятно. Одну строчку только не понял, во втором примере, где написано (17) print, зачем нужен параметр f?

[@selfedu_rus]

f - это обозначение F-строки в Python

[@iiepe1915]

@@selfedu_rus хм, понятно, просто её обычно видел в начале ставят, а тут переменная f цикла и f-строка, немного путает

[@eugenedukatta9355]

Сергей подскажите пожалуйста по каким правилам вы называете фактические и формальные параметры, и почему вы так делаете, отступая от общепризнанных правил, принятых в программировании, не только на Python.

[@selfedu_rus]

в реальной жизни этими терминами программисты не пользуются (никогда не слышал), говорят просто: параметры со значениями по умолчанию или аргументы со значениями

[@eugenedukatta9355]

@@selfedu_rus Да, но по общепринятым правилам, включая другие языки программирования, Формальными параметрами называются переменные (имена), объявленные в заголовке функции и используемые внутри этой функции. Фактический параметр (или по-другому аргумент) это значение, передаваемое в функцию при ее вызове. У вас совершенно иной смысл. Фактическим параметром вы называете позиционные, формальным параметром вы называете параметр со значением по-умолчанию, к которому вы обращаетесь при вызове функции именованным аргументом. Кстати, я не единственный, кто высказывает свое недоумение в комментариях ваших видео, по данному вопросу.

[@СергейСмирнов-ь8у]

Лайк!

[@SAPERPEducation]

Правильно я понимаю, что если бы я вручную вычислял факторил например от 4-х то записал бы следующим образом 1*2*3*4, а функция с рекурсией делает это с конца 4*3*2*1

[@selfedu_rus]

детали реализации уже не помню, но вроде так (факториал верно записан)

[@symbiozzzzzzzzz]

Почему, если выполнение происходит с последнего стэка? А в последнем стэке как раз единица

[@АртемНиконов-у7я]

спасибо за урок! один вопрос :зачем перед depth нужна *

[@VeihShizoo]

Чтобы глубже входить можно было🥵

[@ИванИванов-й8н9д]

круто

[@nouchance]

SERGEY✊

[@vitalybessonov6138]

Штука прикольная, но в целом не эффективная. Видимо только для обхода дерева и подходит. Для факториалов и других прогрессий цикл проще и скорее всего быстрее. Автор обьяснил хорошо, рассказал про стек, про то, что при вызове следующей функции текущая как бы замораживается сохраняя текущие параметры. И так для каждого последующего вызова. И потом когда выполнится последняя, начинается путь обратно по стеку вызовов функций к изначальной постепенно размораживая функции и их параметры. Но все же, где рекурсия еще максимально полезна кроме обхода дерева?

[@selfedu_rus]

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

[@ДмитрийКрашенинников-г7ш]

Сергей. У меня рекурсивная функция по аналогии с Вашей закончилась на 984 итерации без ошибки в PYCharm. Не как у Вас. Это нормально? Кстати, рекурсивная функция мне напомнила эффект бумеранга. Если для понимания, как она работает.

[@VeihShizoo]

Другая версия Пайтона. Естественно не нормально, сноси Винду и все данные в нулину

[@Tony-gx8ye]

я так и не понял, почему у нас функция начинает назад идти, у нас ведь значение value не меняется.

[@ИНТЕР.КОМ]

Она не идёт назад, она поочередно, с конца, закрывает полностью отработанные функции, выполняя необработанные фрагменты, которые как раз являются 4 3 2 1

[@vadimgof8260]

А, если файлов, в каком-нибудь каталоге, будет больше 1000?

[@selfedu_rus]

Либо увеличивать глубину рекурсии (есть настройки), либо не рекурсивный алгоритм применять.

[@vadimgof8260]

@@selfedu_rus а, если я не знаю заранее, сколько там файлов, то, соответственно, я и не знаю на сколько мне это все увеличивать. Проще циклом тогда перебрать, чем гадать сидеть. Возможно, я и не прав

[@selfedu_rus]

@@vadimgof8260 нет, правы )

[@vadimgof8260]

@@selfedu_rus то есть не будет ошибкой, если я буду пользоваться циклом вместо такого рода функции, или же, всё-таки, есть какое-то правило/стандарт, который говорит, что в таких-то моментах надо использовать эту функцию?

[@selfedu_rus]

@@vadimgof8260 да ладно вам, правил на все случаи жизни не напасешься ) просто здравый смысл в большинстве случаев и опыт

[@Иваниванов-д7у9о]

В конце было все непонятно тк как использовалось многое чего не было дано ранее

[@ibrahimoglu]

👍

[@mrdenzl3929]

Вкратце, где применяются рекурсивные функции и какую задачу выполняют , для наглядности? Какую работу выполняют программисты с этой функцией?

[@selfedu_rus]

Иерархический перебор чего-либо

[@ney107-iz6xl]

Что значит depth?????

[@selfedu_rus]

глубина рекурсии

[@ney107-iz6xl]

Спасибо за ответ это я понял что она тут делает На что влияет

[@musicforyou1380]

это похлеще всяких кроссвордов "теребит мозговые нейроны")))

[@ney107-iz6xl]

Если кто может распишите последний код Вроде понял но путаюсь Спасибо)

[@tizyanoonie8483]

Спасибо за урок! Пожалуйста, каталОг! Ведь Вы преподаватель, потом неправильно говорят Ваши студенты (

[@selfedu_rus]

Спасибо! Почти нет ни одного человека, который бы все слова произносил верно, включая и вас :)

[@olegkomlev]

Обобщенный пример повторительной рекурсии с отложенными действиями, зависящими только от результата def F(X): if P(X): return H(X) # нерекурсивное вычисление else: return G(F(D(X))) # возврат рекурсивного вызова от модифицированного аргумента От чисто повторительной отличается дополнительным модификатором результата рекурсивного вызова G, т.е. после получения результата рекурсивного вызова функция что-то дополнительно делает с этим результатом, а только потом его возвращает. Ее преобразовать в итерацию сложнее.

[@olegkomlev]

Обобщенный пример повторительной рекурсии def F(X): if P(X): return H(X) # нерекурсивное вычисление else: return F(D(X)) # возврат рекурсивного вызова от модифицированного аргумента Может быть преобразовано в итеративную функцию def F(X): while not P(X): X=D(X) return H(X) Для примера рекурсивный способ вычисления алгоритма Евклида: НОД(a,b) = a, при a=b НОД(a,b) = НОД(a-b, b) при a > b НОД(a,b) = НОД(a, b-a), при b > a За Х (аргумент) принимаем пару (а,b). Условие прекращения рекурсии P(a,b) = a=b . А противоположное (условие продолжения рекурсии) not P (a,b) будет a != b. Модификатор аргумента D(X) будет такой D(a,b) = (a-b, b) при a > b D(a,b) = (a, b-a), при b > a На питоне модификатор D будет реализован так: if a > b: a=a-b # b = b else: b=b-a # a = a За нерекурсивное вычисление Н(Х) принимаем: H(a,b) = a Получаем рекурсивную функцию def get_nod(a, b): if a != b: return a # нерекурсивное вычисление else: # здесь придется записать в виде условного оператора с двумя ветвями, но рекурсивный вызов в каждый момент один if a > b: return get_nod(a-b, b) else: return get_nod(a, b-a) А если переделать в итеративную функцию по приведенному выше шаблону, получим программу из урока "#37. Алгоритм Евклида для нахождения НОД"

[@АнатолийКузнецов-ж6б]

Честно говоря ничего не понял. Зачем нужны рекурсивные функции, в каких кейсах нужно использовать именно их. Где без этих функций невозможно выполнить программу. Или где эти функции существенно упрощают код...

[@selfedu_rus]

классика: перебор листьев бинарного дерева

[@АнатолийКузнецов-ж6б]

@@selfedu_rus Почитал, посмотрел ещё. Перебор папок (то что Вы показали в ролике). В целом, получше стало, когда ещё допом инфу закинул. Вам спасибо за видео!

[@nikolay7013]

Чтобы сделать матрешку, надо сделать матрешку...

[@АлександрВладимирович-ь3е]

Все ок только когда смотришь. Когда берешься кодить, вся логичность испаряется. Ну и "вэлуе" :) режет слух.

[@lorensio]

Какой же у вас сексуальный голос... Умммм

[@inkognito21blr1080p]

автор объясняет рекурсию и при этом НЕ ОБЪЯСНЯЕТ почему она работает так, как работает. Функция напечатала 4 и завершила свою работу и мы перешли к предыдущей функции. А почему мы перешли к предыдущей функции? Я это просто должен принять как данность? Ладно, на этом этапе принял решение бросить курс и учить по другим источникам, ужасное объяснение тем

[@vladvlad9555]

ужас

[@valeriyn.144]

КатАлог режет слух, можно ведь преподавателю правильное произношение слова выучить