что такое рекурсия в питоне
Рекурсия в Python
Что такое рекурсия?
Простой пример рекурсии, из реального мира, это два зеркала, которые стоят друг напротив друга. Отражение любого объекта между двух зеркал и будет называться рекурсией.
В предыдущих примерах с функциями, мы уже знаем что одна функция может вызвать другую функцию. Функция так же может вызывать саму себя. Такие типы функций, называются рекурсивными функциями. Самый лучший метод разъяснения, это конечно же примеры. Ниже приведен пример функции с рекурсией, которая находит факториал числа.
Факториал — это произведение всех числа от 1 до конечного числа. К примеру, факториал цифры 6 (обозначение факториала 6!), 1*2*3*4*5*6 = 720.
Пример рекурсивной функции
В приведенном примере, мы видим, что функция factorialnum(), вызывает саму себя, поэтому она и является рекурсивной функцией. Логика работы этой функции заключается в том, что она каждый раз вызывает саму себя, уменьшая наше конечное число. То есть, функция вызывает саму себя, при этом умножает число на факториал, который ниже самого числа до тех пор, пока она не станет равным единице. Ниже приведен пример, пошагового разбора.
На изображении ниже, приведен пример, на котором изображен процесс всего происходящего в самом коде.
Важно запомнить! При изучении цикла while, мы с вами обсуждали бесконечный цикл. Точно так же, при отсутствии условия, которая останавливает рекурсию, функция будет бесконечно вызывать саму себя. Если мне не изменяет память, то Python ограничивает глубину рекурсии по умолчанию до 1000, при пересечении этого предела, выйдет ошибка RecursionError.
Рассмотрим функцию с таким условием:
Преимущества рекурсии
Недостаток рекурсии
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.
Что такое рекурсия в питоне
Напомним, что в математике факториал числа 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
Вступление
Эти функции вызывают себя до тех пор, пока проблема не будет решена, практически разделяя исходную задачу на множество меньших экземпляров самой себя – например, принимая небольшие кусочки большего куска пищи.
Конечная цель состоит в том, чтобы съесть всю тарелку горячих карманов, вы делаете это, откусывая снова и снова. Каждый укус-это рекурсивное действие, после которого вы выполняете то же самое действие в следующий раз. Вы делаете это для каждого укуса, оценивая, что вам нужно взять еще один, чтобы достичь цели, пока на вашей тарелке не останется горячих карманов.
Что такое Рекурсия?
Как указано во введении, рекурсия включает в себя процесс, вызывающий себя в определении. Рекурсивная функция обычно имеет два компонента:
Давайте рассмотрим небольшой пример, чтобы продемонстрировать оба компонента:
Базовый случай для нас – это если оставшаяся переменная равна 0 то есть сколько оставшихся строк «привет» мы должны напечатать. Функция просто возвращается.
Давайте визуализируем, как это работает, когда мы вызываем hi_recursive(3) :
Почему бы не использовать петлю?
Весь обход может быть обработан с помощью петель. Тем не менее, некоторые проблемы часто легче решаются с помощью рекурсии, а не итерации. Распространенным случаем использования рекурсии является обход дерева:
При использовании рекурсии обычно легче думать о прохождении через узлы и листья дерева. Несмотря на то, что циклы и рекурсия пересекают дерево, они имеют разные цели – циклы предназначены для повторения задачи, в то время как рекурсия предназначена для разбиения большой задачи на более мелкие задачи.
Рекурсия с деревьями, например, хорошо разветвляется, потому что мы можем обрабатывать все дерево, обрабатывая меньшие части дерева по отдельности.
Примеры
Лучший способ освоиться с рекурсией или любой другой концепцией программирования-это практиковать ее. Создание рекурсивных функций очень просто: обязательно включите свой базовый случай и вызовите функцию таким образом, чтобы она приблизилась к базовому случаю.
Сумма списка
Python включает в себя функцию sum для списков. Реализация Python по умолчанию, CPython, использует неопределенный цикл for-loop в C для создания этих функций (исходный код здесь для тех, кто заинтересован). Давайте посмотрим, как это сделать с помощью рекурсии:
Факториальные числа
Вы можете вспомнить, что факториал положительного целого числа является произведением всех целых чисел, предшествующих ему. Следующий пример сделает это более ясным:
Последовательность Фибоначчи
A Последовательность Фибоначчи – это та, где каждое число является суммой следующих двух чисел. Эта последовательность делает предположение, что числа Фибоначчи для 0 и 1 также равны 0 и 1. Таким образом, эквивалент Фибоначчи для 2 будет равен 1.
Давайте посмотрим последовательность и соответствующие им натуральные числа:
Мы можем легко закодировать функцию в Python для определения эквивалента фибоначчи для любого положительного целого числа с помощью рекурсии:
Теперь я хотел бы, чтобы вы рассмотрели другую реализацию этой функции, которая использует цикл for:
Если целое число меньше или равно 1, то верните его. Теперь, когда наш базовый случай решен. Мы постоянно добавляем первое число со вторым, сохраняя первое число в переменной temp перед его обновлением.
Вывод
Рекурсия позволяет разбить большую задачу на более мелкие задачи, многократно вызывая саму себя. Рекурсивная функция требует, чтобы базовый случай прекратил выполнение, и вызов самой себя, который постепенно приводит функцию к базовому случаю. Он обычно используется в деревьях, но другие функции могут быть написаны с помощью рекурсии, чтобы обеспечить элегантные решения.