Обучающий курс: stepik.org/cou... Что такое рекурсивные функции в Python. Как они работают. Примеры их использования. Telegram-канал: t.me/python_se...
@@xrilicc1154 Вроде бы, с рекурсией прогресс есть🤘Понял про стек вызовов при рекурсии, разобрался в базовом и рекурсивном случае. Порешал еще немного задач🤏 Поэтому успехи есть💥
Согласен. Чтобы лучше понять, надо посмотреть несколько раз через день-два, например. И обязательно своими руками писать код. Это важно. Писать надо по памяти из видео, а потом добавлять свои фишки и "играться". Очень полезно при этом пользоваться отладчиком и пошагово следить, что происходит в программе
как chat объяснил Функция get_files рекурсивно обходит иерархию каталогов и файлов, описанную в словаре F, и выводит названия файлов и каталогов на экран. Аргумент path содержит текущий уровень иерархии (словарь с названиями файлов и каталогов и их содержимым), а depth - текущую глубину рекурсии (сколько раз функция вызывала сама себя). На каждом шаге рекурсии функция выводит название текущего файла или каталога, а затем проверяет, является ли содержимое текущего элемента словарем. Если это словарь, то функция вызывает сама себя рекурсивно, передавая в качестве аргумента содержимое элемента и увеличивая глубину рекурсии на 1. Если содержимое элемента - список, то функция просто выводит список с отступом.
недавно я понял, что рекурсия мне начала нравится, я просто понял как она работает, благодаря лекциям автора в том числе) ну и после перечитывания "Грокаем алгоритмы". Ранее эту тему не допонял. Спасибо)
Терминология. Если рекурсивная функция вызывает саму себя, то это ПРЯМАЯ РЕКУРСИЯ. А если она вызывает какую-то функцию, а та функция вызывает первоначальную - это КОСВЕННАЯ РЕКУРСИЯ. Может быть и более глубокая косвенность - одна функция вызывает другую, другая - третью, и т.д., а какая-то в этой цепочке вызывает первоначальную. Если функция делает не более одного рекурсивного вызова (т.е. либо возвращает результат, либо вызывает себя 1 раз), то это ЛИНЕЙНАЯ РЕКУРСИЯ. Если нарисовать вызовы такой рекурсии, то видим, что они выстроены в одну линию, а потом по этой же линии будет происходить возврат (в начале урока это наглядно показано). Функции recursive и факториал fact, показанные в уроке - примеры линейной рекурсии. Частный случай линейной рекурсии - ПОВТОРИТЕЛЬНАЯ РЕКУРСИЯ (называется также концевая или хвостовая рекурсия - tail recursion). Это если функция либо возвращает результат без рекурсивного вызова, либо делает рекурсивный вызов и сразу возвращает результат этого вызова, никак его не меняя и ничего больше не делая (рекурсивный вызов - последняя операция перед возвратом). Такая рекурсия легко может быть заменена циклом. Многие компиляторы опознают повторительную рекурсию и заменяют рекурсию на итерацию. Но, насколько знаю, Питон этого не делает (по крайней мере, несколько лет назад Гвидо Россум выстапал против такой оптимизации). В функции recursive рекурсия неповторительная (фунция выполняет print после рекурсивного вызова),. А функция fact модифицирует результат рекурсивного вызова перед возвратом (умножает результат на n), поэтому эта рекурсия тоже не повторительная.
Сергей, в целом ваш контент пожалуй действительно лучший в рунете(да и не только), но ваш нейминг переменных… for f in path - тема и так непростая, а тут ещё и гадаешь мысленно, что за f такой:) Наверное, с опытом на такие вещи просто не обращаешь внимания, но новичкам было бы проще понять например: for folder in path - гораздо читабельнее же, хотя и длиннее на пару байт:) В целом же огромное спасибо за ваш труд)
А что про хэш-функцию? Хэш-функция это функция в смысле математики, а не программирования. Это в общем смысле свертка данных любого размера к ограниченному размеру, по особому правилу (алгоритму). Таких функций можно придумать стотыщьпицот! Например, берете любое число любого размера и складываете его цифры. Если в сумме получилось число больше 99 - повторяем, и так далее. Как только получится число меньше 100 - останавливаемся, полученное число и будет результатом, называемым "хэш" от исходных данных. Пример: число 895475289549999278, складываем цифры получается 119 складываем еще раз получается 11. Это и есть хэш от числа 895475289549999278 Это примитивный пример. Настоящие используемые на практике алгоритмы более сложные.
На десятой минуте мозги закипели! Придется пересматривать, потому что на элементе path[f] мозги ломаются, хотя принцип вроде понятен до этого момента За труды большое спасибо
Правильно я понимаю, что если бы я вручную вычислял факторил например от 4-х то записал бы следующим образом 1*2*3*4, а функция с рекурсией делает это с конца 4*3*2*1
Сергей подскажите пожалуйста по каким правилам вы называете фактические и формальные параметры, и почему вы так делаете, отступая от общепризнанных правил, принятых в программировании, не только на Python.
в реальной жизни этими терминами программисты не пользуются (никогда не слышал), говорят просто: параметры со значениями по умолчанию или аргументы со значениями
@@selfedu_rus Да, но по общепринятым правилам, включая другие языки программирования, Формальными параметрами называются переменные (имена), объявленные в заголовке функции и используемые внутри этой функции. Фактический параметр (или по-другому аргумент) это значение, передаваемое в функцию при ее вызове. У вас совершенно иной смысл. Фактическим параметром вы называете позиционные, формальным параметром вы называете параметр со значением по-умолчанию, к которому вы обращаетесь при вызове функции именованным аргументом. Кстати, я не единственный, кто высказывает свое недоумение в комментариях ваших видео, по данному вопросу.
Штука прикольная, но в целом не эффективная. Видимо только для обхода дерева и подходит. Для факториалов и других прогрессий цикл проще и скорее всего быстрее. Автор обьяснил хорошо, рассказал про стек, про то, что при вызове следующей функции текущая как бы замораживается сохраняя текущие параметры. И так для каждого последующего вызова. И потом когда выполнится последняя, начинается путь обратно по стеку вызовов функций к изначальной постепенно размораживая функции и их параметры. Но все же, где рекурсия еще максимально полезна кроме обхода дерева?
Вы правы, по скорости она проигрывает циклам (если задачу можно на циклы заменить). Но иногда скорость не имеет большого значения и глубина рекурсии небольшая. В этом случае для удобства реализации ее вполне можно применить.
Сергей. У меня рекурсивная функция по аналогии с Вашей закончилась на 984 итерации без ошибки в PYCharm. Не как у Вас. Это нормально? Кстати, рекурсивная функция мне напомнила эффект бумеранга. Если для понимания, как она работает.
Она не идёт назад, она поочередно, с конца, закрывает полностью отработанные функции, выполняя необработанные фрагменты, которые как раз являются 4 3 2 1
Обобщенный пример повторительной рекурсии 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. Алгоритм Евклида для нахождения НОД"
@@selfedu_rus а, если я не знаю заранее, сколько там файлов, то, соответственно, я и не знаю на сколько мне это все увеличивать. Проще циклом тогда перебрать, чем гадать сидеть. Возможно, я и не прав
@@selfedu_rus то есть не будет ошибкой, если я буду пользоваться циклом вместо такого рода функции, или же, всё-таки, есть какое-то правило/стандарт, который говорит, что в таких-то моментах надо использовать эту функцию?
Обобщенный пример повторительной рекурсии с отложенными действиями, зависящими только от результата def F(X): if P(X): return H(X) # нерекурсивное вычисление else: return G(F(D(X))) # возврат рекурсивного вызова от модифицированного аргумента От чисто повторительной отличается дополнительным модификатором результата рекурсивного вызова G, т.е. после получения результата рекурсивного вызова функция что-то дополнительно делает с этим результатом, а только потом его возвращает. Ее преобразовать в итерацию сложнее.
Честно говоря ничего не понял. Зачем нужны рекурсивные функции, в каких кейсах нужно использовать именно их. Где без этих функций невозможно выполнить программу. Или где эти функции существенно упрощают код...
@@selfedu_rus Почитал, посмотрел ещё. Перебор папок (то что Вы показали в ролике). В целом, получше стало, когда ещё допом инфу закинул. Вам спасибо за видео!
автор объясняет рекурсию и при этом НЕ ОБЪЯСНЯЕТ почему она работает так, как работает. Функция напечатала 4 и завершила свою работу и мы перешли к предыдущей функции. А почему мы перешли к предыдущей функции? Я это просто должен принять как данность? Ладно, на этом этапе принял решение бросить курс и учить по другим источникам, ужасное объяснение тем
![Kodak Black - Versatile 4 [Official Video]](http://i.ytimg.com/vi/VcP_1Ua__vY/mqdefault.jpg)
Открытый перелом мозга с необратимыми процессами.
Да вроде не такая прям сложная тема, в отличие от циклов тех же.
Урок классный, за пол года смотрю уже восьмой раз) Возможно когда-нибудь пойму. Спасибо
Как успехи? Пробовали конспектировать материал?
@@xrilicc1154 Вроде бы, с рекурсией прогресс есть🤘Понял про стек вызовов при рекурсии, разобрался в базовом и рекурсивном случае. Порешал еще немного задач🤏 Поэтому успехи есть💥
@@youcandoit1559 отлично, я рад за вас! :)
Ура! Неделю разбирал последний пример и сегодня наконец досконально понял, как он работает. Спасибо за урок!
Отличный урок. Тема дается несложно, если подходить к ней аккуратно и размеренно
Согласен. Чтобы лучше понять, надо посмотреть несколько раз через день-два, например. И обязательно своими руками писать код. Это важно. Писать надо по памяти из видео, а потом добавлять свои фишки и "играться". Очень полезно при этом пользоваться отладчиком и пошагово следить, что происходит в программе
Как же классно объяснена такая сложная тема. Здорово!
Большое спасибо! Ещё ни разу не встречал такое наглядное и доступное объяснение 👍🤝
добра и здоровья тебе! никакие скил боксы не тянут по качеству подачи!! СПАСИБО!
Спасибо, посмотрела!
как chat объяснил
Функция get_files рекурсивно обходит иерархию каталогов и файлов, описанную в словаре F, и выводит названия файлов и каталогов на экран.
Аргумент path содержит текущий уровень иерархии (словарь с названиями файлов и каталогов и их содержимым), а depth - текущую глубину рекурсии (сколько раз функция вызывала сама себя). На каждом шаге рекурсии функция выводит название текущего файла или каталога, а затем проверяет, является ли содержимое текущего элемента словарем. Если это словарь, то функция вызывает сама себя рекурсивно, передавая в качестве аргумента содержимое элемента и увеличивая глубину рекурсии на 1. Если содержимое элемента - список, то функция просто выводит список с отступом.
Одно из лучших объяснений рекурсивных функций
Сергей, благодарю! Как всегда всё очень понятно и просто! Особенно за пример с файловой системой - очень круто красиво наглядно👍
Сергей, спасибо за ваши труды!
Этот парень гений, лучше него никто не может объяснить
Пересматриваю регулярно. Почему нельзя каждый раз лайк поставить? )
То есть выполняете рекурсию. )
недавно я понял, что рекурсия мне начала нравится, я просто понял как она работает, благодаря лекциям автора в том числе) ну и после перечитывания "Грокаем алгоритмы". Ранее эту тему не допонял. Спасибо)
Спасибо. Хорошие примеры.
Терминология. Если рекурсивная функция вызывает саму себя, то это ПРЯМАЯ РЕКУРСИЯ. А если она вызывает какую-то функцию, а та функция вызывает первоначальную - это КОСВЕННАЯ РЕКУРСИЯ. Может быть и более глубокая косвенность - одна функция вызывает другую, другая - третью, и т.д., а какая-то в этой цепочке вызывает первоначальную.
Если функция делает не более одного рекурсивного вызова (т.е. либо возвращает результат, либо вызывает себя 1 раз), то это ЛИНЕЙНАЯ РЕКУРСИЯ. Если нарисовать вызовы такой рекурсии, то видим, что они выстроены в одну линию, а потом по этой же линии будет происходить возврат (в начале урока это наглядно показано).
Функции recursive и факториал fact, показанные в уроке - примеры линейной рекурсии.
Частный случай линейной рекурсии - ПОВТОРИТЕЛЬНАЯ РЕКУРСИЯ (называется также концевая или хвостовая рекурсия - tail recursion). Это если функция либо возвращает результат без рекурсивного вызова, либо делает рекурсивный вызов и сразу возвращает результат этого вызова, никак его не меняя и ничего больше не делая (рекурсивный вызов - последняя операция перед возвратом). Такая рекурсия легко может быть заменена циклом. Многие компиляторы опознают повторительную рекурсию и заменяют рекурсию на итерацию. Но, насколько знаю, Питон этого не делает (по крайней мере, несколько лет назад Гвидо Россум выстапал против такой оптимизации).
В функции recursive рекурсия неповторительная (фунция выполняет print после рекурсивного вызова),. А функция fact модифицирует результат рекурсивного вызова перед возвратом (умножает результат на n), поэтому эта рекурсия тоже не повторительная.
Этот комментарий надо закрепить я считаю
отличный практический пример !
СПАСИБО!
Сергей, в целом ваш контент пожалуй действительно лучший в рунете(да и не только), но ваш нейминг переменных… for f in path - тема и так непростая, а тут ещё и гадаешь мысленно, что за f такой:)
Наверное, с опытом на такие вещи просто не обращаешь внимания, но новичкам было бы проще понять например: for folder in path - гораздо читабельнее же, хотя и длиннее на пару байт:)
В целом же огромное спасибо за ваш труд)
Душнила
Упражнения по рекурсивным функциям давались непросто)
Про рекурсии знал, а про обратный ход нет, 🙂
Спасибо большое, очень наглядно и как всегда интересно! Если есть возможность, было бы здорово посмотреть про хэш - функцию 🙂
А что про хэш-функцию? Хэш-функция это функция в смысле математики, а не программирования. Это в общем смысле свертка данных любого размера к ограниченному размеру, по особому правилу (алгоритму). Таких функций можно придумать стотыщьпицот! Например, берете любое число любого размера и складываете его цифры. Если в сумме получилось число больше 99 - повторяем, и так далее. Как только получится число меньше 100 - останавливаемся, полученное число и будет результатом, называемым "хэш" от исходных данных.
Пример: число 895475289549999278, складываем цифры получается 119 складываем еще раз получается 11. Это и есть хэш от числа 895475289549999278
Это примитивный пример. Настоящие используемые на практике алгоритмы более сложные.
Благодарю! 👍🔥
else в вашей функции вычисления факториала избыточно, а условие должно проверять n == 1
На десятой минуте мозги закипели! Придется пересматривать, потому что на элементе path[f] мозги ломаются, хотя принцип вроде понятен до этого момента
За труды большое спасибо
Интересно, почему в примере факториала , значение n не пошло в отрицательную сторону, ведь условие все равно выполнится
спасибо!
Боюсь представить что ждёт меня на практические задания.
спасибо помогло!
Класс!
Подскажите, пожалуйста, если нет ветвлений, почему именно if используется, а не while?
Сам смысл рекурсии понял там где с числами (обратный процесс закрытия). А вот со словарём никак понять не могу, как происходит погружение в глубину?
Спасибо за видео, все понятно.
Одну строчку только не понял, во втором примере, где написано (17) print, зачем нужен параметр f?
f - это обозначение F-строки в Python
@@selfedu_rus хм, понятно, просто её обычно видел в начале ставят, а тут переменная f цикла и f-строка, немного путает
круто
спасибо за урок!
один вопрос :зачем перед depth нужна *
Чтобы глубже входить можно было🥵
SERGEY✊
Правильно я понимаю, что если бы я вручную вычислял факторил например от 4-х то записал бы следующим образом 1*2*3*4, а функция с рекурсией делает это с конца 4*3*2*1
детали реализации уже не помню, но вроде так (факториал верно записан)
Почему, если выполнение происходит с последнего стэка? А в последнем стэке как раз единица
Сергей подскажите пожалуйста по каким правилам вы называете фактические и формальные параметры, и почему вы так делаете, отступая от общепризнанных правил, принятых в программировании, не только на Python.
в реальной жизни этими терминами программисты не пользуются (никогда не слышал), говорят просто: параметры со значениями по умолчанию или аргументы со значениями
@@selfedu_rus Да, но по общепринятым правилам, включая другие языки программирования,
Формальными параметрами называются переменные (имена), объявленные в заголовке функции и используемые внутри этой функции. Фактический параметр (или по-другому аргумент) это значение, передаваемое в функцию при ее вызове.
У вас совершенно иной смысл. Фактическим параметром вы называете позиционные, формальным параметром вы называете параметр со значением по-умолчанию, к которому вы обращаетесь при вызове функции именованным аргументом.
Кстати, я не единственный, кто высказывает свое недоумение в комментариях ваших видео, по данному вопросу.
Штука прикольная, но в целом не эффективная. Видимо только для обхода дерева и подходит. Для факториалов и других прогрессий цикл проще и скорее всего быстрее. Автор обьяснил хорошо, рассказал про стек, про то, что при вызове следующей функции текущая как бы замораживается сохраняя текущие параметры. И так для каждого последующего вызова. И потом когда выполнится последняя, начинается путь обратно по стеку вызовов функций к изначальной постепенно размораживая функции и их параметры. Но все же, где рекурсия еще максимально полезна кроме обхода дерева?
Вы правы, по скорости она проигрывает циклам (если задачу можно на циклы заменить). Но иногда скорость не имеет большого значения и глубина рекурсии небольшая. В этом случае для удобства реализации ее вполне можно применить.
Подскажите, не совсем понятно в случае с факториалом за счет чего останавливается рекурсия.
За счет if´a.
Лайк!
это похлеще всяких кроссвордов "теребит мозговые нейроны")))
👍
В конце было все непонятно тк как использовалось многое чего не было дано ранее
Сергей. У меня рекурсивная функция по аналогии с Вашей закончилась на 984 итерации без ошибки в PYCharm. Не как у Вас. Это нормально? Кстати, рекурсивная функция мне напомнила эффект бумеранга. Если для понимания, как она работает.
Другая версия Пайтона. Естественно не нормально, сноси Винду и все данные в нулину
я так и не понял, почему у нас функция начинает назад идти, у нас ведь значение value не меняется.
Она не идёт назад, она поочередно, с конца, закрывает полностью отработанные функции, выполняя необработанные фрагменты, которые как раз являются 4 3 2 1
Обобщенный пример повторительной рекурсии
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. Алгоритм Евклида для нахождения НОД"
Если кто может распишите последний код
Вроде понял но путаюсь
Спасибо)
Вкратце, где применяются рекурсивные функции и какую задачу выполняют , для наглядности?
Какую работу выполняют программисты с этой функцией?
Иерархический перебор чего-либо
А, если файлов, в каком-нибудь каталоге, будет больше 1000?
Либо увеличивать глубину рекурсии (есть настройки), либо не рекурсивный алгоритм применять.
@@selfedu_rus а, если я не знаю заранее, сколько там файлов, то, соответственно, я и не знаю на сколько мне это все увеличивать. Проще циклом тогда перебрать, чем гадать сидеть. Возможно, я и не прав
@@vadimgof8260 нет, правы )
@@selfedu_rus то есть не будет ошибкой, если я буду пользоваться циклом вместо такого рода функции, или же, всё-таки, есть какое-то правило/стандарт, который говорит, что в таких-то моментах надо использовать эту функцию?
@@vadimgof8260 да ладно вам, правил на все случаи жизни не напасешься ) просто здравый смысл в большинстве случаев и опыт
Обобщенный пример повторительной рекурсии с отложенными действиями, зависящими только от результата
def F(X):
if P(X):
return H(X) # нерекурсивное вычисление
else:
return G(F(D(X))) # возврат рекурсивного вызова от модифицированного аргумента
От чисто повторительной отличается дополнительным модификатором результата рекурсивного вызова G, т.е. после получения результата рекурсивного вызова функция что-то дополнительно делает с этим результатом, а только потом его возвращает. Ее преобразовать в итерацию сложнее.
Что значит depth?????
глубина рекурсии
Спасибо за ответ
это я понял что она тут делает
На что влияет
Спасибо за урок!
Пожалуйста, каталОг! Ведь Вы преподаватель, потом неправильно говорят Ваши студенты (
Спасибо! Почти нет ни одного человека, который бы все слова произносил верно, включая и вас :)
Чтобы сделать матрешку, надо сделать матрешку...
Какой же у вас сексуальный голос... Умммм
Честно говоря ничего не понял. Зачем нужны рекурсивные функции, в каких кейсах нужно использовать именно их. Где без этих функций невозможно выполнить программу. Или где эти функции существенно упрощают код...
классика: перебор листьев бинарного дерева
@@selfedu_rus Почитал, посмотрел ещё. Перебор папок (то что Вы показали в ролике). В целом, получше стало, когда ещё допом инфу закинул. Вам спасибо за видео!
Все ок только когда смотришь. Когда берешься кодить, вся логичность испаряется.
Ну и "вэлуе" :) режет слух.
ужас
автор объясняет рекурсию и при этом НЕ ОБЪЯСНЯЕТ почему она работает так, как работает.
Функция напечатала 4 и завершила свою работу и мы перешли к предыдущей функции.
А почему мы перешли к предыдущей функции? Я это просто должен принять как данность?
Ладно, на этом этапе принял решение бросить курс и учить по другим источникам, ужасное объяснение тем
КатАлог режет слух, можно ведь преподавателю правильное произношение слова выучить