Рекурсивная функция в Python
Когда мы думаем о повторении задачи, мы обычно думаем о циклах for и while. Эти конструкции позволяют нам выполнять итерацию по списку, коллекции и т.д.
Однако есть еще одна форма повторения задачи, но немного в другой манере. Вызывая функцию внутри себя, чтобы решить меньший экземпляр той же проблемы, мы выполняем рекурсию в Python.
Эти функции вызывают сами себя до тех пор, пока проблема не будет решена, практически разделяя исходную проблему на множество более мелких экземпляров самой себя – например, принятие небольших кусочков большего куска пищи.
Конечная цель – съесть всю тарелку с блюдом, вы делаете это, откусывая кусочек снова и снова. Каждый укус – это рекурсивное действие, после которого вы предпринимаете то же действие в следующий раз. Вы делаете это для каждого укуса, оценивая, что вам следует взять еще один, чтобы достичь цели, пока на вашей тарелке не останется еды.
Что такое рекурсия?
Как сказано во введении, рекурсия включает в себя процесс, вызывающий себя в определении. Рекурсивная функция обычно состоит из двух компонентов:
- Базовый случай, который является условием, определяющим, когда рекурсивная функция должна остановиться.
- Призыв к себе.
Давайте посмотрим на небольшой пример, чтобы продемонстрировать оба компонента:
Базовый случай для нас – если оставшаяся переменная равна 0, то есть сколько оставшихся строк «привет» мы должны напечатать. Функция просто возвращается.
После оператора печати мы снова вызываем hi_recursive, но с уменьшенным оставшимся значением. Это важно! Если мы не уменьшим оставшееся значение, функция будет работать бесконечно. Обычно, когда рекурсивная функция вызывает сама себя, параметры меняются, чтобы быть ближе к базовому случаю.
Давайте визуализируем, как это работает, когда мы вызываем hi_recursive(3):
После того, как функция напечатает ‘hi’, она вызывает себя с меньшим значением, чтобы оставаться, пока не достигнет 0. При нуле функция возвращается туда, где она была вызвана в hi_recursive(1), которая возвращается туда, где она была вызвана в hi_recursive(2 ) и в конечном итоге возвращается туда, где он был вызван в hi_recursive(3).
Зачем использовать?
Все обходы можно обрабатывать с помощью циклов. Тем не менее, некоторые проблемы часто легче решить с помощью рекурсии, а не итераций. Обычный вариант использования рекурсии – обход дерева.
При использовании рекурсии обычно легче думать о переходе по узлам и листьям дерева. Несмотря на то, что и циклы, и рекурсия проходят по дереву, они имеют разные цели – циклы предназначены для повторения задачи, тогда как рекурсия предназначена для разбиения большой задачи на более мелкие.
Рекурсия с деревьями, например, хорошо разветвляется, потому что мы можем обрабатывать все дерево, обрабатывая меньшие части дерева по отдельности.
Примеры
Лучший способ освоить рекурсию или любую концепцию программирования – это попрактиковаться. Создать рекурсивные функции просто: обязательно включите базовый случай и вызовите функцию так, чтобы она приближалась к базовому.
Сумма списка
Python включает функцию суммирования для списков. Реализация Python по умолчанию, CPython, использует неопределенный цикл for в C для создания этих функций. Посмотрим, как это сделать с помощью рекурсии:
Базовый случай – пустой список – лучшая сумма для этого равна 0. Как только мы обработаем наш базовый случай, мы удаляем последний элемент списка. Наконец, мы вызываем функцию sum_recursive с сокращенным списком и добавляем полученное число к общей сумме.
В интерпретаторе Python и sum ([10, 5, 2]), и sum_recursive ([10, 5, 2]) должны дать вам 17.
Факториальные числа
Вы можете вспомнить, что факториал положительного целого числа – это произведение всех предшествующих ему целых чисел. Следующий пример проясняет ситуацию:
Восклицательный знак обозначает факториал, и мы видим, что умножаем 5 на произведение всех целых чисел от 4 до 1. Что, если кто-то введет 0? Широко известно и доказано, что 0! = 1. Теперь давайте создадим функцию, как показано ниже:
Мы учитываем случаи, когда вводится 1 или 0, а в противном случае мы умножаем текущее число на факториал числа, уменьшенного на 1.
Простая проверка в интерпретаторе Python покажет, что factorial (5) дает 120.
Последовательность Фибоначчи
Последовательность Фибоначчи – это последовательность, в которой каждое число является суммой следующих двух чисел. Эта последовательность предполагает, что числа Фибоначчи для 0 и 1 также равны 0 и 1. Таким образом, эквивалент Фибоначчи для 2 будет равен 1.
Посмотрим на последовательность и соответствующие ей натуральные числа:
Мы можем легко закодировать функцию на Python, чтобы определить эквивалент Фибоначчи для любого положительного целого числа, используя рекурсию:
Вы можете убедиться, что он работает должным образом, проверив, что значение fibonacci (6) равно 8.
Теперь я хотел бы, чтобы вы рассмотрели другую реализацию этой функции, в которой используется цикл for:
Если целое число меньше или равно 1, верните его. Теперь, когда наш базовый случай обработан, мы непрерывно добавляем первое число ко второму, сохраняя первое число во временной переменной перед его обновлением.
Вывод такой же, как и у первой функции fibonacci(). Эта версия быстрее, чем рекурсивная, поскольку реализации Python не оптимизированы для рекурсии, но превосходят императивное программирование. Однако решение не так легко читается, как наша первая попытка. В этом одна из самых сильных сторон рекурсии: элегантность. Некоторые программные решения наиболее естественно решаются с помощью рекурсии.
Заключение
Рекурсия позволяет нам разбить большую задачу на более мелкие, многократно вызывая себя. Рекурсивная функция в Python требует базового случая для остановки выполнения и вызова самой себя, который постепенно приводит функцию к базовому случаю.
Рекурсивные и лямбда-функции
В 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. Написать функцию для вычисления среднего арифметического переданных ей значений в виде аргументов:
3. Реализовать функцию сортировки выбранных элементов по возрастанию: элементы передаются функции в виде списка и выбираются они с помощью функции-селектора, указанной в качестве второго параметра. Привести примеры вызова функции сортировки с разными видами селекторов. Селекторы реализовать в виде лямбда-функций.
Видео по теме
#1. Первое знакомство с Python Установка на компьютер
#2. Варианты исполнения команд. Переходим в PyCharm
#3. Переменные, оператор присваивания, функции type и id
#4. Числовые типы, арифметические операции
#5. Математические функции и работа с модулем math
#6. Функции print() и input(). Преобразование строк в числа int() и float()
#7. Логический тип bool. Операторы сравнения и операторы and, or, not
#8. Введение в строки. Базовые операции над строками
#9. Знакомство с индексами и срезами строк
#11. Спецсимволы, экранирование символов, row-строки
#12. Форматирование строк: метод format и F-строки
#13. Списки — операторы и функции работы с ними
#14. Срезы списков и сравнение списков
#15. Основные методы списков
#16. Вложенные списки, многомерные списки
#17. Условный оператор if. Конструкция if-else
#18. Вложенные условия и множественный выбор. Конструкция if-elif-else
#19. Тернарный условный оператор. Вложенное тернарное условие
#21. Операторы циклов break, continue и else
#22. Оператор цикла for. Функция range()
#23. Примеры работы оператора цикла for. Функция enumerate()
#24. Итератор и итерируемые объекты. Функции iter() и next()
#25. Вложенные циклы. Примеры задач с вложенными циклами
#26. Треугольник Паскаля как пример работы вложенных циклов
#27. Генераторы списков (List comprehensions)
#28. Вложенные генераторы списков
#29. Введение в словари (dict). Базовые операции над словарями
#30. Методы словаря, перебор элементов словаря в цикле
#31. Кортежи (tuple) и их методы
#32. Множества (set) и их методы
#33. Операции над множествами, сравнение множеств
#34. Генераторы множеств и генераторы словарей
#35. Функции: первое знакомство, определение def и их вызов
#36. Оператор return в функциях. Функциональное программирование
#37. Алгоритм Евклида для нахождения НОД
#38. Именованные аргументы. Фактические и формальные параметры
#39. Функции с произвольным числом параметров *args и **kwargs
#40. Операторы * и ** для упаковки и распаковки коллекций
#42. Анонимные (lambda) функции
#43. Области видимости переменных. Ключевые слова global и nonlocal
#45. Введение в декораторы функций
#46. Декораторы с параметрами. Сохранение свойств декорируемых функций
#47. Импорт стандартных модулей. Команды import и from
#48. Импорт собственных модулей
#49. Установка сторонних модулей (pip install). Пакетная установка
#50. Пакеты (package) в Python. Вложенные пакеты
#51. Функция open. Чтение данных из файла
#52. Исключение FileNotFoundError и менеджер контекста (with) для файлов
#53. Запись данных в файл в текстовом и бинарном режимах
#55. Функция-генератор. Оператор yield
#56. Функция map. Примеры ее использования
#57. Функция filter для отбора значений итерируемых объектов
#58. Функция zip. Примеры использования
#59. Сортировка с помощью метода sort и функции sorted
#60. Аргумент key для сортировки коллекций по ключу
#61. Функции isinstance и type для проверки типов данных
#62. Функции all и any. Примеры их использования
#63. Расширенное представление чисел. Системы счисления
#64. Битовые операции И, ИЛИ, НЕ, XOR. Сдвиговые операторы
#65. Модуль random стандартной библиотеки
© 2022 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта