Рекурсивная функция в python
Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:
Рекурсивные функции
Рекурсивная функция — это та, которая вызывает сама себя.
В качестве простейшего примера рассмотрите следующий код:
Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).
Вкратце о факториалах
Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.
Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040
Вывести факториал числа можно с помощью функции:
Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:
Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.
Это и есть рекурсия. В нашем примере это так сработало:
Детали работы рекурсивной функции
Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.
Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:
Как работает рекурсия
Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.
Рекурсия в Python имеет ограничение в 3000 слоев.
Рекурсивно или итеративно?
Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?
Важно учитывать временную и пространственную сложности. Рекурсивные функции занимают больше места в памяти по сравнению с итеративными из-за постоянного добавления новых слоев в стек в памяти. Однако их производительность куда выше.
Рекурсия может быть медленной, если реализована неправильно
Тем не менее рекурсия может быть медленной, если ее неправильно реализовать. Из-за этого вычисления будут происходить чаще, чем требуется.
Написание итеративных функций зачастую требуется большего количества кода. Например, дальше пример функции для вычисления факториала, но с итеративным подходом. Выглядит не так изящно, не правда ли?
Как написать рекурсивную функцию python
Напомним, что в математике факториал числа n определяется как Например, Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.
Однако, если мы ошибёмся один раз в начальном коде, то потом эта ошибка попадёт в код во все места, куда мы скопировали вычисление факториала. Да и вообще, код занимает больше места, чем мог бы. Чтобы избежать повторного написания одной и той же логики, в языках программирования существуют функции.
Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.
Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение — факториал этого числа.
Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.
Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.
Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.
Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).
Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.
2. Локальные и глобальные переменные
Внутри функции можно использовать переменные, объявленные вне этой функции
Здесь переменной a присваивается значение 1, и функция f() печатает это значение, несмотря на то, что до объявления функции f эта переменная не инициализируется. В момент вызова функции f() переменной a уже присвоено значение, поэтому функция f() может вывести его на экран.
Такие переменные (объявленные вне функции, но доступные внутри функции) называются глобальными.
Но если инициализировать какую-то переменную внутри функции, использовать эту переменную вне функции не удастся. Например:
Интересным получится результат, если попробовать изменить значение глобальной переменной внутри функции:
Чтобы функция могла изменить значение глобальной переменной, необходимо объявить эту переменную внутри функции, как глобальную, при помощи ключевого слова global :
В этом примере на экран будет выведено 1 1, так как переменная a объявлена, как глобальная, и ее изменение внутри функции приводит к тому, что и вне функции переменная будет доступна.
Тем не менее, лучше не изменять значения глобальных переменных внутри функции. Если ваша функция должна поменять какую-то переменную, пусть лучше она вернёт это значением, и вы сами при вызове функции явно присвоите в переменную это значение. Если следовать этим правилам, то функции получаются независимыми от кода, и их можно легко копировать из одной программы в другую.
Например, пусть ваша программа должна посчитать факториал вводимого числа, который вы потом захотите сохранить в переменной f. Вот как это не стоит делать:
Этот код написан плохо, потому что его трудно использовать ещё один раз. Если вам завтра понадобится в другой программе использовать функцию «факториал», то вы не сможете просто скопировать эту функцию отсюда и вставить в вашу новую программу. Вам придётся поменять то, как она возвращает посчитанное значение.
Гораздо лучше переписать этот пример так:
Если нужно, чтобы функция вернула не одно значение, а два или более, то для этого функция может вернуть список из двух или нескольких значений:
Тогда результат вызова функции можно будет использовать во множественном присваивании:
3. Рекурсия
Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=n⋅(n-1)!. Но как вычислить (n-1)!? Если бы мы вычислили (n-2)!, то мы сможем вычисли и (n-1)!=(n-1)⋅(n-2)!. А как вычислить (n-2)!? Если бы. В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:
Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.
Поэтому при разработке рекурсивной функции необходимо прежде всего оформлять условия завершения рекурсии и думать, почему рекурсия когда-либо завершит работу.
Рекурсия в Python
Рекурсия — одна из фундаментальных концепций информатики, она важна как для программистов, так и для специалистов по обработке данных. Мало того, что многие алгоритмы сортировки и поиска рекурсивны, но каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это отмечает, что рекурсия является ключевой концепцией, которую необходимо пересмотреть перед любым собеседованием по кодированию.
Сегодня мы поможем вам освежить свои навыки рекурсивного программирования на Python и рассмотрим 6 практических задач, чтобы получить практический опыт.
Что такое рекурсия?
Рекурсия — это концепция в информатике, когда функция вызывает саму себя и выполняет цикл до тех пор, пока не достигнет желаемого конечного условия. Он основан на математической концепции рекурсивных определений, которая определяет элементы в наборе с точки зрения других элементов в наборе.
Каждая рекурсивная реализация имеет базовый случай, когда желаемое состояние было достигнуто, и рекурсивный случай, когда желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг.
Поведение в рекурсивном случае перед вызовом рекурсивной функции, внутренний самовызов, повторяется на каждом шаге. Поэтому рекурсивные структуры полезны, когда вы можете решить более серьёзную проблему (базовый случай), выполнив повторяющиеся подзадачи (рекурсивный случай), которые постепенно перемещают программу к базовому случаю.
Это приводит к поведению, аналогичному циклам for или while, за исключением того, что рекурсия приближается к целевому условию, в то время как for циклы выполняются заданное количество раз, а while циклы выполняются до тех пор, пока условие больше не будет выполняться.
Другими словами, рекурсия декларативна, потому что вы устанавливаете состояние, которого хотите достичь, а for/ while циклы являются итеративными, потому что вам нужно установить количество повторений.
Рекурсивные решения лучше всего подходят, когда проблема имеет чёткие подзадачи, которые необходимо повторить, и если вы не уверены, сколько раз вам нужно будет выполнить цикл с итеративным решением.
Например, если вы хотите создать программу-функцию факториала, которая находит факториал неизвестного числа.
Прямая против косвенной рекурсии
До сих пор мы обсуждали только прямую рекурсию, когда рекурсивная функция явно вызывает себя на своём рекурсивном шаге. Существует также косвенная рекурсия, когда рекурсивный вызов удаляется из функции, но всё ещё выполняется в результате исходного рекурсивного шага.
Например, functionAзвонки functionB, которые потом звонят function Aснова.
Плюсы и минусы рекурсии в Python
Все языки программирования поддерживают рекурсию, однако не все одинаково оптимизированы.
Итерация часто является предпочтительной в Python и считается более «питонической» из-за встроенных оптимизаций. Как правило, рекурсивные решения предпочтительнее итеративных решений при больших вычислениях, поскольку рекурсия часто приводит к меньшему количеству кода и более высокой производительности при масштабировании.
Плюсы
Минусы
Я не добавил удобочитаемости ни в один из столбцов, поскольку некоторые разработчики считают рекурсию более понятной, в то время как другие находят вложенное поведение запутанным. В конечном счёте, это индивидуально для каждой проблемы и разработчика.
Рекурсия в Python
Теперь давайте более подробно рассмотрим рекурсивные функции в Python.
Ниже приведён пример программы, которая рекурсивно печатает шаблон: 10 5 0 5 10.
Рекурсия в Python
Введение
Примеры
Сумма чисел от 1 до n
Или использовать рекурсию:
У рекурсии есть несколько преимуществ в сравнении с первыми двумя методами. Рекурсия занимает меньше времени, чем выписывание 1 + 2 + 3 на сумму от 1 до 3. Для [рекурсии(4)] рекурсия может работать в обратную сторону:
Как и когда происходит рекурсия
Рекурсия появляется когда вызов функции повторно вызывает ту же функцию до завершения первоначального вызова функции. Например, рассмотрим известное математическое выражение x! (т.е. факториал). Факториал определяется для всех неотрицательных целых чисел следующим образом:
Если число равно 0, то будет 1.
В противном случае ответом будет то, что число умножается на факториал на единицу меньше этого числа.
В Python наивная реализация факториала может быть определена как функция следующим образом:
У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в подробности, потому что это редкий случай, и его трудно мысленно обрабатывать.
Вы также можете иметь «параллельные» рекурсивные вызовы функций. Например, рассмотрим последовательность Фибоначчи, которая определяется следующим образом:
В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.
Мы можем определить это следующим образом:
Теперь давайте рассмотрим еще несколько терминов:
Оптимизация хвоста вызова (TCO) — это способ автоматического сокращения рекурсии в рекурсивных функциях.
Оптимизация хвоста вызова может пригодиться по нескольким причинам:
Интерпретатор может снизить объём памяти, занятый средами. Поскольку ни у кого нет неограниченной памяти, чрезмерные рекурсивные вызовы функций приведут к переполнению стека.
Интерпретатор может уменьшить количество переключателей кадров стека.
В Python нет TCO по нескольким причинам, поэтому для обхода этого ограничения можно использовать другие методы. Выбор используемого метода зависит от варианта использования. Интуитивно понятно, что factorial и fib можно относительно легко преобразовать в итеративный код следующим образом:
Обычно это самый эффективный способ устранения рекурсии вручную, но для более сложных функций может быть трудно.
Другим полезным инструментом является декодер lru_cache, который можно использовать для уменьшения количества лишних вычислений.
Теперь вы знаете, как избежать рекурсии в Python, но когда её нужно использовать? Ответ «не часто». Все рекурсивные функции могут быть реализованы итеративно. Это просто вопрос, как именно сделать. Однако есть редкие случаи, когда можно использовать рекурсию. Рекурсия распространена в Python, когда ожидаемые вводы не вызовут значительного количества вызовов рекурсивных функций.
Если вы интересуетесь рекурсией, стоит изучить функциональные языки, такие как Scheme или Haskell. На таких языках рекурсия намного полезней.
В таком случае лучше использовать линейную рекурсию:
Но у этого примера есть проблема в возвращении пары чисел. Это показывает, что не всегда стоит использовать рекурсию.
Исследование дерева с рекурсией
Допустим, у нас есть такое дерево:
Возможно, вы не хотите вывести, а вернуть список всех имён узлов. Это можно сделать с помощью передачи прокручиваемого списка в качестве параметра.
Увеличение максимальной глубины рекурсии
Существует предел глубины возможной рекурсии, который зависит от реализации Python. Когда предел достигнут, возникает исключение RuntimeError :
RuntimeError: Maximum Recursion Depth Exceeded
Пример программы, которая может вызвать такую ошибку:
Можно изменить предел глубины рекурсии с помощью
Чтобы проверить текущие параметры лимита, нужно запустить:
Если запустить тот же метод выше с новым пределом, мы получаем
В Python 3.5 ошибка стала называться RecursionError, которая является производной от RuntimeError.
Хвостовая рекурсия — как не надо делать
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Вот пример обратного отсчета, написанного с использованием хвостовой рекурсии:
Любое вычисление, которое может быть выполнено с использованием итерации, также может быть выполнено с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:
Хвостовую рекурсию лучше не использовать, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. В таких случаях рекурсивное решение использует больше системных ресурсов, чем итеративное.
Оптимизация хвостовой рекурсии с помощью интроспекции стека
По умолчанию рекурсивный стек Python не превышает 1000 кадров. Это ограничение можно изменить, установив sys.setrecursionlimit(15000) который быстрее, однако этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему рекурсии хвоста, используя интроспекцию стека.
Чтобы оптимизировать рекурсивные функции, мы можем использовать декоратор @tail_call_optimized для вызова нашей функции. Вот несколько примеров общей рекурсии с использованием декоратора, описанного выше:
Синтаксис
Параметры
Примечания
Исходная переменная должна быть передана рекурсивной функции, чтобы сохранить её.
Научим основам Python и Data Science на практике
Это не обычный теоритический курс, а онлайн-тренажер, с практикой на примерах рабочих задач, в котором вы можете учиться в любое удобное время 24/7. Вы получите реальный опыт, разрабатывая качественный код и анализируя реальные данные.
Как работает рекурсия в python?
Когда функция вызывает сама себя, она называется рекурсивной функцией. В этом руководстве мы узнаем, как написать функцию рекурсии Python.
Что такое рекурсия в Python?
Когда функция определена таким образом, что она вызывает сама себя, она называется рекурсивной функцией. Это явление называется рекурсией. Python поддерживает рекурсивные функции.
Рекурсия очень похожа на цикл, в котором функция вызывается на каждой итерации. Вот почему мы всегда можем использовать циклы как замену функции рекурсии Python.
Но некоторые программисты предпочитают рекурсию циклам. В основном это вопрос выбора, и вы можете использовать циклы или рекурсию.
Примеры
Следующий код возвращает сумму первых n натуральных чисел, используя рекурсивную функцию python.
Это печатает сумму первых 100 натуральных чисел и первых 500 натуральных чисел
1. Факториал целого числа
Факториал целого числа вычисляется путем умножения целых чисел от 1 до этого числа. Например, факториал 10 будет 1 * 2 * 3…. * 10.
Давайте посмотрим, как мы можем написать факториальную функцию с помощью цикла for.
Давайте посмотрим, как мы можем изменить функцию factorial() для использования рекурсии.
На изображении ниже показано выполнение рекурсивной функции.
2. Ряд Фибоначчи
Ряд Фибоначчи — это последовательность чисел, каждое из которых представляет собой сумму двух предыдущих чисел. Например — 1, 1, 2, 3, 5, 8, 13, 21 и так далее.
Давайте посмотрим на функцию для возврата чисел ряда Фибоначчи с помощью циклов.
Вот реализация функции fibonacci() с использованием рекурсии.
Здесь рекурсивный код функции меньше и прост для понимания. Так что использование рекурсии в этом случае имеет смысл.
Базовый случай
При определении рекурсивной функции должен быть хотя бы один базовый случай, для которого нам известен результат. Затем каждый последующий вызов рекурсивной функции должен приближать ее к базовому случаю.
Это необходимо для того, чтобы в конечном итоге рекурсивные вызовы прекратились. В противном случае функция никогда не завершится и мы получим ошибку нехватки памяти.
Вы можете проверить это поведение в обоих приведенных выше примерах. Аргументы вызова рекурсивной функции становятся все ближе к базовому случаю.