что такое рекурсия в python
BestProg
Рекурсия в Python. Примеры решения задач
Содержание
Поиск на других ресурсах:
1. Понятие рекурсии. Рекурсивные функции
Рекурсия — это способ организации циклического процесса путем вызова рекурсивной функции. Рекурсивная функция — это функция, которая содержит код вызова самой себя с целью организации циклического процесса. С помощью рекурсивных функций можно с минимальным объемом кода решать некоторые задачи, обойдя использование (объявление) лишних структур данных. Рекурсию можно рассматривать как альтернативу циклам и итерациям.
2. Примеры решения задач на рекурсию
Вытащив первый элемент из списка с помощью среза, можно передать этот новосозданный список в следующий рекурсивный вызов функции.
Результат выполнения программы
Результат выполнения программы
Если нужно, чтобы рекурсивная функция обрабатывала вложенные списки, то в теле функции нужно реализовать цикл обхода элементов списка. Затем этот элемент нужно проверять, является ли он списком по образцу
Результат выполнения программы
Ряд Фибоначчи содержит числа, в которых следующее число определяется как сумма двух предыдущих чисел:
Нижеприведенная рекурсивная функция формирует ряд Фибоначчи в виде списка для заданного максимального значения в списке.
Результат выполнения программы
В примере приводится функция ReverseNumber() представления числа в обратном порядке. Например, для числа 12345 результат будет 54321.
Результат выполнения функции
Результат выполнения программы
Каждый рекурсивный вызов функции рассматривает список как две составляющие:
Результат выполнения программы
В данном примере, с целью сравнения, реализованы 2 функции, которые конвертируют целое число из десятичной системы исчисления в его аналог в двоичной системе исчисления:
Рекурсия в Python
Рекурсия — одна из фундаментальных концепций информатики, она важна как для программистов, так и для специалистов по обработке данных. Мало того, что многие алгоритмы сортировки и поиска рекурсивны, но каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это отмечает, что рекурсия является ключевой концепцией, которую необходимо пересмотреть перед любым собеседованием по кодированию.
Сегодня мы поможем вам освежить свои навыки рекурсивного программирования на Python и рассмотрим 6 практических задач, чтобы получить практический опыт.
Что такое рекурсия?
Рекурсия — это концепция в информатике, когда функция вызывает саму себя и выполняет цикл до тех пор, пока не достигнет желаемого конечного условия. Он основан на математической концепции рекурсивных определений, которая определяет элементы в наборе с точки зрения других элементов в наборе.
Каждая рекурсивная реализация имеет базовый случай, когда желаемое состояние было достигнуто, и рекурсивный случай, когда желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг.
Поведение в рекурсивном случае перед вызовом рекурсивной функции, внутренний самовызов, повторяется на каждом шаге. Поэтому рекурсивные структуры полезны, когда вы можете решить более серьёзную проблему (базовый случай), выполнив повторяющиеся подзадачи (рекурсивный случай), которые постепенно перемещают программу к базовому случаю.
Это приводит к поведению, аналогичному циклам for или while, за исключением того, что рекурсия приближается к целевому условию, в то время как for циклы выполняются заданное количество раз, а while циклы выполняются до тех пор, пока условие больше не будет выполняться.
Другими словами, рекурсия декларативна, потому что вы устанавливаете состояние, которого хотите достичь, а for/ while циклы являются итеративными, потому что вам нужно установить количество повторений.
Рекурсивные решения лучше всего подходят, когда проблема имеет чёткие подзадачи, которые необходимо повторить, и если вы не уверены, сколько раз вам нужно будет выполнить цикл с итеративным решением.
Например, если вы хотите создать программу-функцию факториала, которая находит факториал неизвестного числа.
Прямая против косвенной рекурсии
До сих пор мы обсуждали только прямую рекурсию, когда рекурсивная функция явно вызывает себя на своём рекурсивном шаге. Существует также косвенная рекурсия, когда рекурсивный вызов удаляется из функции, но всё ещё выполняется в результате исходного рекурсивного шага.
Например, functionAзвонки functionB, которые потом звонят function Aснова.
Плюсы и минусы рекурсии в Python
Все языки программирования поддерживают рекурсию, однако не все одинаково оптимизированы.
Итерация часто является предпочтительной в Python и считается более «питонической» из-за встроенных оптимизаций. Как правило, рекурсивные решения предпочтительнее итеративных решений при больших вычислениях, поскольку рекурсия часто приводит к меньшему количеству кода и более высокой производительности при масштабировании.
Плюсы
Минусы
Я не добавил удобочитаемости ни в один из столбцов, поскольку некоторые разработчики считают рекурсию более понятной, в то время как другие находят вложенное поведение запутанным. В конечном счёте, это индивидуально для каждой проблемы и разработчика.
Рекурсия в Python
Теперь давайте более подробно рассмотрим рекурсивные функции в Python.
Ниже приведён пример программы, которая рекурсивно печатает шаблон: 10 5 0 5 10.
5.1. Теория¶
5.1.1. Основные понятия и механизм работы¶
5.1.1.1. Определение подпрограммы¶
Подпрограмма должна быть объявлена и в общем случае содержать:
список имен и типов передаваемых параметров (необязательно);
тип возвращаемого значения (необязательно).
5.1.1.2. Вызов подпрограммы¶
Для того, чтобы использовать ранее определенную подпрограмму, необходимо в требуемом месте кода произвести ее вызов, указав:
указать имя подпрограммы;
передать требуемые аргументы (значения параметров).
Код, вызвавший подпрограмму, передает ей управление и ожидает завершения выполнения.
Подпрограмма также может вызывать сама себя, т.е. выполняться рекурсивно.
В настоящее время наиболее часто встречаются следующие способы передачи аргументов:
Для переменной, переданной по значению создается локальная копия и любые изменения, которые происходят в теле подпрограммы с переданной переменной, на самом деле, происходят с локальной копией и никак не сказываются на самой переменной.
Изменения, которые происходят в теле подпрограммы с переменной, переданной по ссылке, происходят с самой переданной переменной.
5.1.1.3. Механизм работы¶
Большинство современных языков программирования для управления вызовом подпрограмм используют стек вызовов.
Примерный цикл работы стека вызова следующий (Видео 5.1.1, Видео 5.1.2):
Вызов подпрограммы создает запись в стеке; каждая запись может содержать информацию о данных вызова (аргументах, результате, а также адресе возврата).
Когда подпрограмма завершается, запись удаляется из стека и программа продолжает выполняться, начиная с адреса возврата.
5.1.1.4. Преимущества и недостатки¶
Преимущества использования подпрограмм:
распределение большой задачи между несколькими разработчиками или стадиями проекта;
сокрытие деталей реализации от пользователей подпрограммы;
улучшение отслеживания выполнения кода (большинство языков программирования предоставляет стек вызовов подпрограмм).
Недостатком использования подпрограмм можно считать накладные расходы на вызов подпрограммы, однако современные трансляторы стремятся оптимизировать данный процесс.
5.1.2. Функции в Python¶
Для объявления функции в Python используется ключевое слово def :
Соглашение рекомендует использовать:
змеиный_регистр (англ. snake_case) для наименования функций: my_function ;
пустые строки для отделения функций, а большие блоки кода помещать внутрь функций;
При встрече оператора return в коде Python немедленно завершает выполнение функции, аналогично break для циклических конструкций.
Пример определения и вызова функции приведен в Листинге 5.1.1 и на Рисунке 5.1.1.
Python, как и многие другие языки, позволяет создавать собственные (пользовательские) функции, среди которых можно выделить четыре типа (Листинг 5.1.2):
Доступны из любой точки программного кода в том же модуле или из других модулей.
Объявляются внутри других функций и видны только внутри них: используются для создания вспомогательных функций, которые нигде больше не используются.
Не имеют имени и объявляются в месте использования. В Python и представлены лямбда-выражениями.
5.1.3. Глобальные и локальные функции¶
5.1.3.1. Параметры и аргументы¶
5.1.3.1.1. Позиционные и ключевые параметры/аргументы¶
Все параметры, указываемые в Python при объявлении и вызове функции делятся на:
позиционные: указываются простым перечислением:
ключевые: указываются перечислением ключ=значение :
Позиционные и ключевые аргументы могут быть скомбинированы. Синтаксис объявления и вызова функции зависит от типа параметра, однако позиционные параметры (и соответствующие аргументы) всегда идут перед ключевыми:
Преимущества ключевых параметров:
нет необходимости отслеживать порядок аргументов;
у ключевых параметров есть значение по умолчанию, которое можно не передавать.
Пример функции со смешанными типами параметров приведен в Листинге 5.1.3.
5.1.3.1.2. Упаковка и распаковка аргументов¶
Достичь такого поведения можно, используя механизм упаковки аргументов, указав при объявлении параметра в функции один из двух символов:
* : все позиционные аргументы начиная с этой позиции и до конца будут собраны в кортеж;
** : все ключевые аргументы начиная с этой позиции и до конца будут собраны в словарь.
Пример упаковки аргументов приведен в Листинге 5.1.4.
* : кортеж/список распаковывается как отдельные позиционные аргументы и передается в функцию;
** : словарь распаковывается как набор ключевых аргументов и передается в функцию.
Пример распаковки аргументов приведен в Листинге 5.1.5.
5.1.3.2. Область видимости¶
В Python выделяется четыре области видимости:
Локальная (англ. Local)
Нелокальная (англ. Enclosed)
Глобальная (англ. Global)
Встроенная (англ. Built-in).
«Системная» область модуля builtins : содержит предопределенные идентификаторы, например, функцию max() и т.п.
идентификатор может называться локальным, глобальным и т.д., если имеет соответствующую область видимости;
функции образуют локальную область видимости, а модули – глобальную;
чем ближе область к концу списка, тем более она открыта (ее содержимое доступно для более закрытых областей видимости; например, глобальные идентификаторы и предопределенные имена могут быть доступны в локальной области видимости функции, но не наоборот).
В Листинге 5.1.6 приведен пример четырех областей видимости.
Схема разрешения имен в языке Python называется правилом LEGB (Local, Enclosed, Global, Built-in) 6: когда внутри функции выполняется обращение к неизвестному имени, интерпретатор пытается отыскать его в четырех областях видимости по очереди до первого нахождения.
В Листингах 5.1.7 (а-д) приведены некоторые случае выполнения LEGB-правила.
По умолчанию, идентификаторы из другой области видимости доступны только для чтения, а, при попытке присвоения, функция создает локальный идентификатор.
Если необходимо изменять в функции переменные более закрытой области видимости, существует 3 способа:
использовать инструкцию global : сообщая, что функция будет изменять один или более глобальных идентификаторов;
использовать инструкцию nonlocal : сообщая, что вложенная функция будет изменять один или более идентификаторов внешних функций;
передать мутирующий аргумент в качестве параметра функции.
К изменению переменных из другой области видимости необходимо относиться крайне осторожно и прибегать только в случае крайней необходимости.
В большинстве случаев необходимо придерживаться концепции изолированного доступа через области видимости.
В связи с тем, что мутирующие аргументы могут быть изменены внутри функции, стоит аккуратно использовать их в качестве значений ключевых аргументов по умолчанию, которые создаются при инициализации функции (Листинг 5.1.11).
5.1.3.3. Возврат нескольких значений¶
Часто из функции необходимо вернуть несколько значений (например, в Паскале, для этого используются выходные параметры с ключевым словом var ). Одним из лучших способов для этого в Python является возврат кортежа с несколькими значениями (Листинг 5.1.12).
Прочие способы (например, изменение глобальных переменных) не рекомендуются 7.
5.1.3.4. Рекурсия¶
Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причем без явных повторений частей программы и использования циклов.
В Листинге 5.1.13 приведен пример реализации рекурсивной функции.
5.1.3.5. Строки документации¶
Соглашения по документированию функций содержатся в документе PEP 257.
В Листинге 5.1.14 приведен пример написания документации к функции.
5.1.4. Анонимные функции¶
Python поддерживает синтаксис, позволяющий определять анонимные функции (лямбда-функции или лямбда-выражения):
часть parameters является необязательной, и если она присутствует, то обычно представляет собой простой список имен переменных, разделенных запятыми (позиционных аргументов);
результатом лямбда-выражения является анонимная функция.
Пример записи лямбда-функции приведен в Листинге 5.1.15.
5.1.5. Побочный эффект¶
К побочным эффектам выполнения функции можно отнести:
изменение данных в памяти;
чтение/запись файла или устройства;
самостоятельную реакцию на исключительные ситуации;
Естественно, что полностью избежать побочных эффектов невозможно. В таких случаях необходимо локализовать участки кода с побочным эффектом в отдельные функции (Листинге 5.1.16).
Решая задачу, необходимо следить чтобы каждая проектируемая функция выполняла минимальную, логически полную задачу.
Например, если необходимо вычислить сумму и среднее значение элементов списка, правильнее будет создать 2 функции для каждого вычисления, а не одну; при этом ввод и вывод значений также оформить в виде отдельных функций.
Sebesta, W.S Concepts of Programming languages. 10E; ISBN 978-0133943023.
Саммерфилд М. Программирование на Python 3. Подробное руководство. — М.: Символ-Плюс, 2009. — 608 с.: ISBN: 978-5-93286-161-5.
Рекурсивная функция в 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?
Когда функция вызывает сама себя, она называется рекурсивной функцией. В этом руководстве мы узнаем, как написать функцию рекурсии 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() с использованием рекурсии.
Здесь рекурсивный код функции меньше и прост для понимания. Так что использование рекурсии в этом случае имеет смысл.
Базовый случай
При определении рекурсивной функции должен быть хотя бы один базовый случай, для которого нам известен результат. Затем каждый последующий вызов рекурсивной функции должен приближать ее к базовому случаю.
Это необходимо для того, чтобы в конечном итоге рекурсивные вызовы прекратились. В противном случае функция никогда не завершится и мы получим ошибку нехватки памяти.
Вы можете проверить это поведение в обоих приведенных выше примерах. Аргументы вызова рекурсивной функции становятся все ближе к базовому случаю.