Обучающий курс: stepik.org/course/100707 Что такое рекурсивные функции в Python. Как они работают. Примеры их использования. Telegram-канал: t.me/python_selfedu
Терминология. Если рекурсивная функция вызывает саму себя, то это ПРЯМАЯ РЕКУРСИЯ. А если она вызывает какую-то функцию, а та функция вызывает первоначальную - это КОСВЕННАЯ РЕКУРСИЯ. Может быть и более глубокая косвенность - одна функция вызывает другую, другая - третью, и т.д., а какая-то в этой цепочке вызывает первоначальную. Если функция делает не более одного рекурсивного вызова (т.е. либо возвращает результат, либо вызывает себя 1 раз), то это ЛИНЕЙНАЯ РЕКУРСИЯ. Если нарисовать вызовы такой рекурсии, то видим, что они выстроены в одну линию, а потом по этой же линии будет происходить возврат (в начале урока это наглядно показано). Функции recursive и факториал fact, показанные в уроке - примеры линейной рекурсии. Частный случай линейной рекурсии - ПОВТОРИТЕЛЬНАЯ РЕКУРСИЯ (называется также концевая или хвостовая рекурсия - tail recursion). Это если функция либо возвращает результат без рекурсивного вызова, либо делает рекурсивный вызов и сразу возвращает результат этого вызова, никак его не меняя и ничего больше не делая (рекурсивный вызов - последняя операция перед возвратом). Такая рекурсия легко может быть заменена циклом. Многие компиляторы опознают повторительную рекурсию и заменяют рекурсию на итерацию. Но, насколько знаю, Питон этого не делает (по крайней мере, несколько лет назад Гвидо Россум выстапал против такой оптимизации). В функции recursive рекурсия неповторительная (фунция выполняет print после рекурсивного вызова),. А функция fact модифицирует результат рекурсивного вызова перед возвратом (умножает результат на n), поэтому эта рекурсия тоже не повторительная.
Согласен. Чтобы лучше понять, надо посмотреть несколько раз через день-два, например. И обязательно своими руками писать код. Это важно. Писать надо по памяти из видео, а потом добавлять свои фишки и "играться". Очень полезно при этом пользоваться отладчиком и пошагово следить, что происходит в программе
@@xrilicc1154 Вроде бы, с рекурсией прогресс есть🤘Понял про стек вызовов при рекурсии, разобрался в базовом и рекурсивном случае. Порешал еще немного задач🤏 Поэтому успехи есть💥
недавно я понял, что рекурсия мне начала нравится, я просто понял как она работает, благодаря лекциям автора в том числе) ну и после перечитывания "Грокаем алгоритмы". Ранее эту тему не допонял. Спасибо)
Сергей, в целом ваш контент пожалуй действительно лучший в рунете(да и не только), но ваш нейминг переменных… for f in path - тема и так непростая, а тут ещё и гадаешь мысленно, что за f такой:) Наверное, с опытом на такие вещи просто не обращаешь внимания, но новичкам было бы проще понять например: for folder in path - гораздо читабельнее же, хотя и длиннее на пару байт:) В целом же огромное спасибо за ваш труд)
как chat объяснил Функция get_files рекурсивно обходит иерархию каталогов и файлов, описанную в словаре F, и выводит названия файлов и каталогов на экран. Аргумент path содержит текущий уровень иерархии (словарь с названиями файлов и каталогов и их содержимым), а depth - текущую глубину рекурсии (сколько раз функция вызывала сама себя). На каждом шаге рекурсии функция выводит название текущего файла или каталога, а затем проверяет, является ли содержимое текущего элемента словарем. Если это словарь, то функция вызывает сама себя рекурсивно, передавая в качестве аргумента содержимое элемента и увеличивая глубину рекурсии на 1. Если содержимое элемента - список, то функция просто выводит список с отступом.
А что про хэш-функцию? Хэш-функция это функция в смысле математики, а не программирования. Это в общем смысле свертка данных любого размера к ограниченному размеру, по особому правилу (алгоритму). Таких функций можно придумать стотыщьпицот! Например, берете любое число любого размера и складываете его цифры. Если в сумме получилось число больше 99 - повторяем, и так далее. Как только получится число меньше 100 - останавливаемся, полученное число и будет результатом, называемым "хэш" от исходных данных. Пример: число 895475289549999278, складываем цифры получается 119 складываем еще раз получается 11. Это и есть хэш от числа 895475289549999278 Это примитивный пример. Настоящие используемые на практике алгоритмы более сложные.
На десятой минуте мозги закипели! Придется пересматривать, потому что на элементе path[f] мозги ломаются, хотя принцип вроде понятен до этого момента За труды большое спасибо
Обобщенный пример повторительной рекурсии 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. Алгоритм Евклида для нахождения НОД"
Обобщенный пример повторительной рекурсии с отложенными действиями, зависящими только от результата def F(X): if P(X): return H(X) # нерекурсивное вычисление else: return G(F(D(X))) # возврат рекурсивного вызова от модифицированного аргумента От чисто повторительной отличается дополнительным модификатором результата рекурсивного вызова G, т.е. после получения результата рекурсивного вызова функция что-то дополнительно делает с этим результатом, а только потом его возвращает. Ее преобразовать в итерацию сложнее.
Сергей. У меня рекурсивная функция по аналогии с Вашей закончилась на 984 итерации без ошибки в PYCharm. Не как у Вас. Это нормально? Кстати, рекурсивная функция мне напомнила эффект бумеранга. Если для понимания, как она работает.
Правильно я понимаю, что если бы я вручную вычислял факторил например от 4-х то записал бы следующим образом 1*2*3*4, а функция с рекурсией делает это с конца 4*3*2*1
Она не идёт назад, она поочередно, с конца, закрывает полностью отработанные функции, выполняя необработанные фрагменты, которые как раз являются 4 3 2 1
Штука прикольная, но в целом не эффективная. Видимо только для обхода дерева и подходит. Для факториалов и других прогрессий цикл проще и скорее всего быстрее. Автор обьяснил хорошо, рассказал про стек, про то, что при вызове следующей функции текущая как бы замораживается сохраняя текущие параметры. И так для каждого последующего вызова. И потом когда выполнится последняя, начинается путь обратно по стеку вызовов функций к изначальной постепенно размораживая функции и их параметры. Но все же, где рекурсия еще максимально полезна кроме обхода дерева?
Вы правы, по скорости она проигрывает циклам (если задачу можно на циклы заменить). Но иногда скорость не имеет большого значения и глубина рекурсии небольшая. В этом случае для удобства реализации ее вполне можно применить.
Сергей подскажите пожалуйста по каким правилам вы называете фактические и формальные параметры, и почему вы так делаете, отступая от общепризнанных правил, принятых в программировании, не только на Python.
в реальной жизни этими терминами программисты не пользуются (никогда не слышал), говорят просто: параметры со значениями по умолчанию или аргументы со значениями
@@selfedu_rus Да, но по общепринятым правилам, включая другие языки программирования, Формальными параметрами называются переменные (имена), объявленные в заголовке функции и используемые внутри этой функции. Фактический параметр (или по-другому аргумент) это значение, передаваемое в функцию при ее вызове. У вас совершенно иной смысл. Фактическим параметром вы называете позиционные, формальным параметром вы называете параметр со значением по-умолчанию, к которому вы обращаетесь при вызове функции именованным аргументом. Кстати, я не единственный, кто высказывает свое недоумение в комментариях ваших видео, по данному вопросу.
@@selfedu_rus а, если я не знаю заранее, сколько там файлов, то, соответственно, я и не знаю на сколько мне это все увеличивать. Проще циклом тогда перебрать, чем гадать сидеть. Возможно, я и не прав
@@selfedu_rus то есть не будет ошибкой, если я буду пользоваться циклом вместо такого рода функции, или же, всё-таки, есть какое-то правило/стандарт, который говорит, что в таких-то моментах надо использовать эту функцию?
Честно говоря ничего не понял. Зачем нужны рекурсивные функции, в каких кейсах нужно использовать именно их. Где без этих функций невозможно выполнить программу. Или где эти функции существенно упрощают код...
@@selfedu_rus Почитал, посмотрел ещё. Перебор папок (то что Вы показали в ролике). В целом, получше стало, когда ещё допом инфу закинул. Вам спасибо за видео!
автор объясняет рекурсию и при этом НЕ ОБЪЯСНЯЕТ почему она работает так, как работает. Функция напечатала 4 и завершила свою работу и мы перешли к предыдущей функции. А почему мы перешли к предыдущей функции? Я это просто должен принять как данность? Ладно, на этом этапе принял решение бросить курс и учить по другим источникам, ужасное объяснение тем
