Как сделать рекурсию в питоне
Обновлено: 03.07.2024
Подпрограмма - средство языка программирования, позволяющее упаковывать и параметризовать функциональность.
Как правило, подпрограмма - это именованный фрагмент программного кода, к которому можно обратиться из другого места программы, однако она может и не иметь имени (называясь в таком случае анонимной).
5.1.1. Основные понятия и механизм работы¶
5.1.1.1. Определение подпрограммы¶
Подпрограмма должна быть объявлена и в общем случае содержать:
список имен и типов передаваемых параметров (необязательно);
тип возвращаемого значения (необязательно).
Если подпрограмма возвращает значение вызывающему коду (одно или несколько), она называется функцией, иначе - процедурой.
5.1.1.2. Вызов подпрограммы¶
Для того, чтобы использовать ранее определенную подпрограмму, необходимо в требуемом месте кода произвести ее вызов, указав:
указать имя подпрограммы;
передать требуемые аргументы (значения параметров).
Код, вызвавший подпрограмму, передает ей управление и ожидает завершения выполнения.
Подпрограмма также может вызывать сама себя, т.е. выполняться рекурсивно.
В настоящее время наиболее часто встречаются следующие способы передачи аргументов:
Для переменной, переданной по значению создается локальная копия и любые изменения, которые происходят в теле подпрограммы с переданной переменной, на самом деле, происходят с локальной копией и никак не сказываются на самой переменной.
Изменения, которые происходят в теле подпрограммы с переменной, переданной по ссылке, происходят с самой переданной переменной.
5.1.1.3. Механизм работы¶
Большинство современных языков программирования для управления вызовом подпрограмм используют стек вызовов.
Примерный цикл работы стека вызова следующий (Видео 5.1.1, Видео 5.1.2):
Вызов подпрограммы создает запись в стеке; каждая запись может содержать информацию о данных вызова (аргументах, результате, а также адресе возврата).
Когда подпрограмма завершается, запись удаляется из стека и программа продолжает выполняться, начиная с адреса возврата.
Видео 5.1.1 - Cтек вызовов (пример, Нетология)
5.1.1.4. Преимущества и недостатки¶
Главное назначение подпрограмм сегодня - структуризация программы с целью удобства ее понимания и сопровождения.
Преимущества использования подпрограмм:
декомпозиция сложной задачи на несколько более простых подзадач: это один из двух главных инструментов структурного программирование (второй - структуры данных);
распределение большой задачи между несколькими разработчиками или стадиями проекта;
сокрытие деталей реализации от пользователей подпрограммы;
улучшение отслеживания выполнения кода (большинство языков программирования предоставляет стек вызовов подпрограмм).
Недостатком использования подпрограмм можно считать накладные расходы на вызов подпрограммы, однако современные трансляторы стремятся оптимизировать данный процесс.
5.1.2. Функции в Python¶
В Python нет формального разделения подпрограмм на функции и процедуры (как, например, в Паскале или Си), и процедурой можно считать функцию, возвращающую пустое значение - в остальном используется единственный термин - функция.
Для объявления функции в Python используется ключевое слово def :
На имя функции в Python накладываются такие же ограничения, как и на прочие идентификаторы .
Соглашение рекомендует использовать:
змеиный_регистр (англ. snake_case) для наименования функций: my_function ;
пустые строки для отделения функций, а большие блоки кода помещать внутрь функций;
В Python все данные - объекты, при вызове в функцию передается ссылка на этот объект. При этом, мутирующие объекты передаются по ссылке, немутирующие - по значению.
Функция в Python может возвращать результат своего выполнения, используя оператор return (например, return 5 ). В случае, если он не был указан или указан пустой оператор return , возвращается специальное значение None .
При встрече оператора return в коде Python немедленно завершает выполнение функции, аналогично break для циклических конструкций.
Пример определения и вызова функции приведен в Листинге 5.1.1 и на Рисунке 5.1.1.
Рисунок 5.1.1 - Передача параметров и возвращение результата функции ¶
Python, как и многие другие языки, позволяет создавать собственные (пользовательские) функции, среди которых можно выделить четыре типа (Листинг 5.1.2):
Доступны из любой точки программного кода в том же модуле или из других модулей.
Объявляются внутри других функций и видны только внутри них: используются для создания вспомогательных функций, которые нигде больше не используются.
Не имеют имени и объявляются в месте использования. В Python и представлены лямбда-выражениями.
Функции, ассоциированные с каким-либо объектом (например, list.append() , где append() - метод объекта list ).
5.1.3. Глобальные и локальные функции¶
5.1.3.1. Параметры и аргументы¶
5.1.3.1.1. Позиционные и ключевые параметры/аргументы¶
Все параметры, указываемые в Python при объявлении и вызове функции делятся на:
позиционные: указываются простым перечислением:
ключевые: указываются перечислением ключ=значение :
Позиционные и ключевые аргументы могут быть скомбинированы. Синтаксис объявления и вызова функции зависит от типа параметра, однако позиционные параметры (и соответствующие аргументы) всегда идут перед ключевыми:
Преимущества ключевых параметров:
нет необходимости отслеживать порядок аргументов;
у ключевых параметров есть значение по умолчанию, которое можно не передавать.
Пример функции со смешанными типами параметров приведен в Листинге 5.1.3.
5.1.3.1.2. Упаковка и распаковка аргументов¶
В ряде случаев бывает полезно определить функцию, способную принимать любое число аргументов. Так, например, работает функция print() , которая может принимать на печать различное количество объектов и выводить их на экран.
Достичь такого поведения можно, используя механизм упаковки аргументов, указав при объявлении параметра в функции один из двух символов:
* : все позиционные аргументы начиная с этой позиции и до конца будут собраны в кортеж;
** : все ключевые аргументы начиная с этой позиции и до конца будут собраны в словарь.
Пример упаковки аргументов приведен в Листинге 5.1.4.
Python также предусматривает и обратный механизм - распаковку аргументов, используя аналогичные обозначения перед аргументом:
* : кортеж/список распаковывается как отдельные позиционные аргументы и передается в функцию;
** : словарь распаковывается как набор ключевых аргументов и передается в функцию.
Пример распаковки аргументов приведен в Листинге 5.1.5.
5.1.3.2. Область видимости¶
Область видимости - область программы, где определяются идентификаторы, и транслятор выполняет их поиск. За пределами области видимости тот же самый идентификатор может быть связан с другой переменной, либо быть свободным (не связанным ни с какой из них).
В Python выделяется четыре области видимости:
Локальная (англ. Local)
Собственная область внутри инструкции def .
Нелокальная (англ. Enclosed)
Область в пределах вышестоящей инструкции def .
Глобальная (англ. Global)
Область за пределами всех инструкций def - глобальная для всего модуля.
Встроенная (англ. Built-in).
Локальная и нелокальная области видимости являются относительными, глобальная и встроенная - абсолютными.
идентификатор может называться локальным, глобальным и т.д., если имеет соответствующую область видимости;
функции образуют локальную область видимости, а модули – глобальную;
чем ближе область к концу списка, тем более она открыта (ее содержимое доступно для более закрытых областей видимости; например, глобальные идентификаторы и предопределенные имена могут быть доступны в локальной области видимости функции, но не наоборот).
В Листинге 5.1.6 приведен пример четырех областей видимости.
Схема разрешения имен в языке Python называется правилом LEGB (Local, Enclosed, Global, Built-in) 6: когда внутри функции выполняется обращение к неизвестному имени, интерпретатор пытается отыскать его в четырех областях видимости по очереди до первого нахождения.
В Листингах 5.1.7 (а-д) приведены некоторые случае выполнения LEGB-правила.
По умолчанию, идентификаторы из другой области видимости доступны только для чтения, а, при попытке присвоения, функция создает локальный идентификатор.
Если необходимо изменять в функции переменные более закрытой области видимости, существует 3 способа:
использовать инструкцию global : сообщая, что функция будет изменять один или более глобальных идентификаторов;
использовать инструкцию nonlocal : сообщая, что вложенная функция будет изменять один или более идентификаторов внешних функций;
передать мутирующий аргумент в качестве параметра функции.
В Листингах 5.1.8, 5.1.9 и 5.1.10 приведены примеры использования ключевых слов global , nonlocal , а также передачи мутирующего аргумента.
Листинг 5.1.8 - Использование global позволяет менять значение глобальной переменной внутри функции | скачать ¶
Листинг 5.1.9 - Использование nonlocal позволяет менять значение нелокальной переменной внутри вложенной функции | скачать ¶
К изменению переменных из другой области видимости необходимо относиться крайне осторожно и прибегать только в случае крайней необходимости.
В большинстве случаев необходимо придерживаться концепции изолированного доступа через области видимости.
В связи с тем, что мутирующие аргументы могут быть изменены внутри функции, стоит аккуратно использовать их в качестве значений ключевых аргументов по умолчанию, которые создаются при инициализации функции (Листинг 5.1.11).
5.1.3.3. Возврат нескольких значений¶
Часто из функции необходимо вернуть несколько значений (например, в Паскале, для этого используются выходные параметры с ключевым словом var ). Одним из лучших способов для этого в Python является возврат кортежа с несколькими значениями (Листинг 5.1.12).
Прочие способы (например, изменение глобальных переменных) не рекомендуются 7.
5.1.3.4. Рекурсия¶
Рекурсия - вызов функции внутри самой себя, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия)
Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причем без явных повторений частей программы и использования циклов.
Не рекомендуется использовать рекурсию, если такая функция может привести или приводит к большой глубине рекурсии - лучше заменить ее циклической конструкцией. Рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека (англ. англ. Stack Overflow) вызовов.
В Листинге 5.1.13 приведен пример реализации рекурсивной функции.
5.1.3.5. Строки документации¶
Документирование кода - важный аспект, от которого зависит читаемость и быстрота понимания кода всеми участниками команды разработки.
Python предоставляет возможность добавить документацию (описание) к любой функции, используя строки документирования - это обычные строки тройных кавычках """ , которые следуют сразу за строкой с инструкцией def перед программным кодом функции и воспринимаются транслятором специальным образом.
Соглашения по документированию функций содержатся в документе PEP 257.
Верно оформленная строка документации является краткой справкой по функции, которую можно увидеть, вызвав метод __doc__ , или функцию help() .
В Листинге 5.1.14 приведен пример написания документации к функции.
5.1.4. Анонимные функции¶
Python поддерживает синтаксис, позволяющий определять анонимные функции (лямбда-функции или лямбда-выражения):
часть parameters является необязательной, и если она присутствует, то обычно представляет собой простой список имен переменных, разделенных запятыми (позиционных аргументов);
выражение expression не может содержать условных инструкций или циклов (условные выражения - допустимы), а также не может содержать инструкцию return ;
результатом лямбда-выражения является анонимная функция.
Когда лямбда-функция вызывается, она возвращает результат вычисления выражения expression .
Пример записи лямбда-функции приведен в Листинге 5.1.15.
5.1.5. Побочный эффект¶
Побочный эффект (англ. Side Effect) - любые действия программы, изменяющие среду выполнения (англ. Execution Environment).
К побочным эффектам выполнения функции можно отнести:
изменение данных в памяти;
чтение/запись файла или устройства;
самостоятельную реакцию на исключительные ситуации;
Часто функции с побочным эффектом при вызове несколько раз с одними и теми же аргументами в качестве результата возвращают разные значения. Пример - стандартная функция генерации случайного числа.
Создавая функцию, необходимо избегать побочных эффектов - такие функции легче тестируются и не содержат скрытых действий. Один из примеров такой функции - функция solve_equation() в Листинге 5.1.12 .
Естественно, что полностью избежать побочных эффектов невозможно. В таких случаях необходимо локализовать участки кода с побочным эффектом в отдельные функции (Листинге 5.1.16).
Решая задачу, необходимо следить чтобы каждая проектируемая функция выполняла минимальную, логически полную задачу.
Например, если необходимо вычислить сумму и среднее значение элементов списка, правильнее будет создать 2 функции для каждого вычисления, а не одну; при этом ввод и вывод значений также оформить в виде отдельных функций.
В Python функцию можно вызывать саму из себя. Это называется рекурсией. В качестве примера рекурсивной функции я приведу вычисление числа в степени n (n – целое число).
И, далее, можно ее вызвать так:
Теперь подробнее разберемся как она работает. Для начала заметим, что
то есть, для вычисления значения на текущем n-м шаге достаточно взять значение на предыдущем n-1-м шаге и умножить его на x. Эта формула, по сути, отражает принцип рекурсии. В нашем случае она будет выглядеть так:
Далее, запуск функции осуществляется с аргументами 2 и 3: pow(2, 3). Она помещается в стек вызова функций, в котором хранится порядок вызова различных функций. Далее, выполняется тело функции. Проверяется первое условие. Оно оказывается ложным, так как 3 == 0 дает false. Поэтому идет переход на else и прежде чем выполнить оператор return, снова вызывается та же функция pow(2, 2).
Выполнение функции pow(2, 3) останавливается, в стек помещается вторая функция pow(2, 2) и она запускается. Снова проверяется первое условие, оно ложно, переходим по else к оператору return и опять вызываем функцию pow(2, 1).
Здесь снова все повторяется, в стек помещается очередной вызов функции и по условию вызывается следующая функция pow(2, 0).
Теперь первое условие становится истинным и функция pow(2,0) возвращает значение 1 и рекурсия не идет дальше вглубь – она останавливается. Функция pow(2.0) завершается, она удаляется из стека вызовов и управление передается функции pow(2, 1). Но она частично уже выполнена. Поэтому, берется значение 1 от pow(2, 0), результат умножается на x=2 и величина 2 возвращается функцией pow(2, 1).
Функция pow(2,1) также удаляется из стека, управление переходит к вышестоящей функции pow(2,2) и здесь мы уже имеем результат умножения x*x, то есть, 2*2 = 4. Далее, возвращаемся к самой верхней функции pow(2,3), здесь 2*4=8 и этот результат становится результатом вычисления рекурсивной функции.
Функции с произвольным числом аргументов
Для начала вспомним, что когда мы говорили о кортежах, то указывали на такую работу оператора присваивания:
Здесь x и y принимают значения 1 и 2 соответственно. Но когда этих значений было больше, чем переменных:
то возникала ошибка. Так вот, смотрите, если поставить оператор *, например, перед y, то ошибки не возникнет:
и переменная x = 1, а y = [2, 3, 4]. То есть, во вторую переменную будут записаны все оставшиеся значения в виде списка. Или же, можно сделать так:
Тогда первые три значения будут помещены в x:
а последнее в y: y = 4. То же самое работает и со списками:
И вообще с любыми перечисляемыми типами данных. То есть, оператор * упаковывает оставшиеся значения в список. Правда, мы не можем упаковывать уже упакованные данные, например, так:
произойдет ошибка, но вот так:
Этот же оператор может выполнять и обратную операцию – распаковывать списки в набор данных. Смотрите, предположим, мы описываем, что счетчик в цикле for должен пробегать диапазон от -5 до 5 с шагом 1. Как вы уже знаете, это делается так:
Далее, мы хотим представить этот диапазон с помощью списка:
и передать его функции range. Если записать просто a:
То возникнет ошибка, т.к. функция ожидает числа, а не список. Но, записав * перед переменной a, произойдет распаковка списка в набор из двух чисел: -5 и 6:
- Если выполняется присвоение данных переменной с оператором *, то данные упаковываются. Например, *y, x = 1,2,3.
- Если выполняется передача списка с указанием оператора *, то происходит его распаковка. Например, range(*[-5,6]).
Этот оператор можно использовать для объявления функций с произвольным числом аргументов:
Смотрите, у нас args становится кортежем с переданными значениями при вызове функции. Значит, мы спокойно можем перебрать все значения кортежа, например, в цикле for:
В результате получили функцию с произвольным числом аргументов. Где это может пригодиться? Например, реализовать универсальную функцию для вычисления суммы переданных элементов:
А что если мы хотим передавать функции неограниченное количество именованных аргументов? Вот так:
В этом случае аргумент у функции следует записать с двумя звездочками:
И при ее вызове мы видим, что kwargs – это словарь. Как перебирать элементы словаря мы уже знаем, например, можно сделать так:
и далее, выполняем определенные действия в зависимости от значений именованных аргументов.
Но, если мы теперь попытаемся вызвать функцию вот так:
то возникнет ошибка, т.к. первые три аргумента не именованные. Для такого варианта вызовов функцию myFunc следует записать так:
Причем, вот эти неименованные аргументы должны всегда следовать перед именованными. Или же можно сделать так:
Все эти комбинации вполне допустимы, главное чтобы их порядок был именно таким: сначала фактические параметры, затем необязательный список args, затем формальные параметры и потом список этих параметров.
Анонимные или лямбда-функции
В Python существуют так называемые анонимные функции (они же лямбда-функции). Что это такое? Давайте для начала рассмотрим такой пример:
У нас имеется функция showElements, которая отображает из списка lst только те элементы, для которых функция func возвращает значение True. Далее, мы создаем вспомогательную функцию __odd, которая возвращает True для нечетных значений. И идет вызов showElements для списка a и селектора в виде функции __odd.
Но что если мы захотим изменить селектор и выбирать, например, все четные значения? Нужно создавать новую функцию и затем указывать ссылку на нее? Это как то не очень удобно. Вот здесь нам на помощь приходят лямбда-функции. Их можно объявить в любом месте программы по следующему синтаксису:
lambda arg1, arg2, …: выражение
и, затем, вызвать ее:
То есть, в анонимных функциях можно писать после двоеточий любой оператор, но только один. Несколько нельзя. И кроме того, результат работы этого оператора автоматически возвращается лямбда-функцией.
В нашем случае мы можем записать такую функцию сразу в качестве второго аргумента:
Видите, как это удобно, понятно и наглядно. Мы сразу видим как будет выбирать значения функция showElements.
Если анонимная функция не принимает никаких аргументов, то она записывается так:
Вот такие интересные и полезные возможности в объявлении функций существуют в языке Python.
Задания для самоподготовки
1. Написать рекурсивную функцию для вычисления факториала числа n:
2. Написать функцию для вычисления среднего арифметического переданных ей значений в виде аргументов:
arg1, arg2, …, argN
3. Реализовать функцию сортировки выбранных элементов по возрастанию: элементы передаются функции в виде списка и выбираются они с помощью функции-селектора, указанной в качестве второго параметра. Привести примеры вызова функции сортировки с разными видами селекторов. Селекторы реализовать в виде лямбда-функций.
Видео по теме
© 2022 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта
Рекурсия в Python
Взгляните на картинки ниже и вы поймете, что уже встречались с рекурсией в реальной жизни.
В программировании под рекурсией понимается такая функция, которая вызывает саму себя.
Но если вы напишите функцию,которая будет вызывать саму себя бесконечное количество раз, получите ошибку Recursionerror: maximum recursion depth exceeded. Попробуйте запустить у себя на компьютере следующую программу.
Поэтому для того, чтобы написать рекурсивную функцию, у вас должно быть условие выхода. То есть условие, от выполнения которого будет зависеть, нужно ли вызывать функцию вновь. Попробуйте запустить программу ниже.
Условие выхода называют также базовым случаем - самым простым решением какой-нибудь задачи.
Нахождение факториала с помощью рекурсии
Например, базовым случаем (самым простым случаем) нахождения факториала, является 1! или 0!. Это значение гораздо легче найти, чем например 7! (факториал 7).
Но рекурсии кроме базового случая должен присутствовать рекурсивный случай или шаг рекурсии - это способ сведения задачи к более простой. Например, 5! = 1*2*3*4*5 = 4!*5. То есть, чтобы найти факториал пяти, достаточно знать факториал четырех и умножить это на 5. Тогда в общем виде рекурентная формула нахождения факториала будет выглядеть следующим образом:
А код реализации будет следующим:
Нахождение чисел Фибоначчи
Числа Фибоначчи представляют собой рекурентный ряд чисел - это значит, что в этом ряду должны быть обязательно первые члены ряда (обычно это 0 и 1), а все остальные числа находятся от предыдущих путем сложения двух чисел стоящих перед текущим.
В итоге получаем такой ряд: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и т.д.
У каждого числа в этом ряду есть свой порядковый номер, начинается нумерация с единицы. И давайте обозначим за F(n) - n-ое число Фибоначчи. И тогда,чтобы найти пятое число Фибоначчи нужно сложить два предыдущих к нему F(5) = F(4)+F(4). А общая формула нахождения будет выглядеть следующим образом:
Ниже приведена реализация этой формулы в Python. Более подробно о том, как реализован этот алгоритм, смотрите в видео.
Проверить строку на палиндром(рекурсия)
Палиндром - слово или фраза, которые одинаково читаются слева направо и справа налево.
Строка, состоящая из одного символа, по умолчанию является палиндромом. Это наш базовый или самый простой случай. Также за палиндром мы будет принимать и пустую строку.
А для всех остальных строк мы будет брать первый и последний символ, если они совпадают, то рекурсивно будет проверять строку без этих символов, а в противном случае строка не является палиндромом.
Ниже представлена рекурсивная функция, которая реализует проверку на палиндром.
Читайте также: