что такое рекурсия 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.
Что такое рекурсия 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
Apr 4, 2019 · 10 min read
Цикл — это фундаментальный инструмент в программировании. Существует множество различных типов циклов, но почти все они выполнят одну базовую функцию: повторение определённых действий над данными, для их анализа или управления ими. Рекурсия, так же распространённый способ анализировать и манипулировать данными, как и цикл, но как правило, менее понятный и часто более запутанный. Почти все рекурсивные функции можно переписать в циклы, и наоборот. Тем не менее, каждый тип функции имеет свои преимущества и недостатки, и сегодня вы узнаете, в каких случаях применять тот или иной метод. В статье мы разберём следующие вопросы:
Начнём с м етода, который кажется более простым из этих двух.
Циклы for
Цикл for используют для перебора последовательности данных (списка, кортежа, словаря, набора или строки). При достижении конца последовательности цикл завершается.
Например, вам нужно сложить числа от 1 до 5 и получить их сумму. Конечно, вы можете просто суммировать 1+2+3+4+5. Но, создать функцию намного удобнее, потому что вы сможете использовать её повторно, причём подставляя любые значения, даже если они не известны заранее.
Это будет выглядеть примерно так:
Для работы такого цикла, нам нужно хранить список всех чисел, чтобы мы могли перебирать элементы и складывать их в итоговое значение.
Вот как это выглядит в коде:
Запустив код, мы увидим, что все числа на своих местах и нам возвращается их сумма.
Рекурсия
Если функция вызывает сама себя, то это является признаком рекурсии. Одно из важнейших отличий рекурсии от цикла, это способ завершения рекурсивной функции. В приведённом выше примере цикл for завершается в конце последовательности, в которой он выполняется. А вот рекурсивная функция может продолжаться бесконечно, потому что она может не иметь последовательности данных. Вместо этого у рекурсивной функции есть так называемое базовое условие. Базовое условие определяет, когда цикл должен завершится.
Давайте попробуем решить предыдущую задачу рекурсивным способом. Визуально это выглядит так:
Каждый раз функция либо вызывает себя с новыми входными данными, либо возвращает значение.
Вот как это выглядит в коде:
Как видите мы передаём два значения: начальное и итоговое. При первом вызове функции итоговое значение равно 0, а начальное 5. Мы проверяем, является ли начальное число 0. Если нет, то вызываем функцию снова, но на этот раз мы меняем входное значение на 5–1 и 0+5, и повторяем этот процесс до тех пор, пока n не будет равно 0. После выполнения этого условия мы возвращаем итоговое значение (15).
Вычисление сложного процента рекурсией и циклом FOR
Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:
Формула расчёта сложного процента:
Так мы можем рассчитать всю сумму сразу. Но вместо этого, для расчёта мы используем цикл или рекурсию. В таком случае переменная времени (nt) будет обрабатываться в итерациях.
Давайте сразу создадим переменные, в которых будем хранить исходные числа и используем их в обоих методах:
Расчёт по сложной процентной ставке итеративно
Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.
Так выглядит код:
Единственное различие между этим и предыдущим примерами заключается в том, что мы делаем на несколько вычислений больше во время каждой итерации. Также увеличилось число итераций с 5 до 120.
Результат наших вычислений:
Расчёт по сложной процентной ставке рекурсивным способом
В предыдущем примере последовательность данных равна 120, что отражает количество раз, когда основная сумма пересчитывается. Цикл прерывается по завершении последовательности. Рекурсивный метод позволяет нам поступить схожим образом, т.е. инициализировать счётчик и задать два условия.
Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.
В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.
Здесь происходит тоже самое, только начальное значение теперь 120
Здесь мы либо снова вызываем функцию, либо возвращаем обновлённую общую сумму. Каждый раз вызывая функцию, значение счётчика уменьшается на 1. Возврат общей суммы происходит, когда счётчик равен 0.
Когда использовать рекурсию
Выбор между рекурсивным и итеративным методом может в значительной степени зависеть от языка, который вы используете, или от задачи, которую вы намерены решить. Например, в JavaScript рекурсия может привести к ошибкам stack frame errors, когда предел стека уже достигнут, а базовое условие ещё не выполнено. В таком случае, итеративный подход будет работать лучше.
Рассмотренный выше случай является хорошим примером того, когда рекурсия работает намного лучше, чем цикл.
Давайте представим, что помимо тех чисел, которые мы использовали в предыдущем примере, нам нужно учитывать и другие данные. Например, мы можем отслеживать то, как регулярные платежи влияют на срок кредита. Возможно, мы захотим остановить цикл до завершения последовательности. Если общее количество раз, когда начисляются проценты по кредиту равно 120, то и длина списка равна 120. Но, если сумма кредита будет равна 0 уже после 100 итераций, то в конце списка останется 20 неиспользуемых и ненужных элементов списка. Проблема дальнейшего усложнения сценария цикла заключается в том, что значения переменных, таких как сумма кредита, зависит от значения той же переменной на предыдущей итерации. Дело не в том, что это сложно реализовать, а в том, что это грязно.
Визуализация данной проблемы:
Рекурсивные структуры данных
Именно в таких случаях рекурсивные структуры данных особенно полезны. Структуру можно назвать рекурсивной, если её можно определить в терминах меньшей версии самой себя. Список является примером рекурсивной структуры данных.
Например, возьмём такой список:
Теперь, сделаем на его основе два меньших списка:
Если вывести оба списка, то мы увидим следующее:
Благодаря рекурсивным функциям и рекурсивными структурам данных мы можем изменить весь список или меньшую часть большего списка за раз. Итеративный подход решения подобной проблемы, позволяет изменить только одно значение в одном индексе за раз.
Пример того, как это сделать:
Сохранив маленькие части большого списка, мы можем вызвать ту же функцию (рекурсия) и отправить ей эти части (рекурсивная структура данных).
Вот как это работает на примере с вычислением сложного процента:
Наша функция в основном состоит из операторов if и else. Мы можем усложнить эту структуру если понадобится, но она и в таком виде делает всё что нам нужно. В итоге, мы хотим вернуть окончательные данные, которые покажут нам сумму кредита и размер текущего платежа на каждой итерации, когда начисляется процент.
Визуализация процессов рекурсивной функции:
При каждом рекурсивном вызове мы будем брать первый элемент массива из списка. Затем мы изменим значения этого элемента и снова вызовем функцию, но на этот раз передадим ей в качестве параметров array[:1] и array[1:]. На картинке видно, что, достигнув середины списка, мы будем иметь две его части одинакового размера. А уже к концу мы полностью переберём и модифицируем все элементы первого списка, и добавим их во второй список. Далее мы шаг за шагом реализуем эту функцию в коде.
Шаг 1: создаём массив
На данном этапе, наш массив имеет длину равную числу раз, когда начисляется процент. Каждый элемент содержит одинаковые данные, которые мы будем изменять рекурсивно.
Шаг 2: создаём функцию и базовое условие
Базовое условие будет учитывать два возможных сценария. Либо счётчик достигнул конца последовательности ( len(inputArr) == 0 ), либо мы погасили кредит раньше ( inputArr[-1][‘principal amount’] ).
Шаг 3: создаём выражение else и определяем переменные current, inputArray и outputArray
Шаг 4: если массив outputArray пуст, то берём первый элемент из массива входных данных и помещаем его в массив выходных данных без изменений.
Теперь оба массива выглядят как на картинке, которую вы видели выше, в момент первого вызова рекурсивной функции.
Шаг 5: если массив выходных данных не пуст, то изменяем все значения текущего элемента.
Шаг 6: добавляем переменную newCurrent к массиву outputArray
Шаг 7: вызываем рекурсивную функцию с новыми параметрами
Мы закончили! Так выглядит код целиком:
Чтобы убедиться, что код работает так, как мы задумали, давайте увеличим сумму платежа.
Если изменить сумму платежа на 2000, то при выводе должны получиться такие данные:
Такой код возвращает более чистый результат, чем при использовании цикла. Если бы мы использовали итеративный подход, то нам пришлось бы перебрать все 120 элементов, большинство из которых были бы бесполезны/пусты.
Заключение
На первый взгляд рекурсия может показаться сложной. Но в некоторых случаях, рекурсивный метод невероятно эффективен, если всё сделать правильно. Тем не менее, иногда лучше использовать циклы. Понимание обоих методов и умение эффективно их использовать поможет вам в работе и будет преимуществом на собеседовании.
Рекурсия в Python
Что такое рекурсия?
Простой пример рекурсии, из реального мира, это два зеркала, которые стоят друг напротив друга. Отражение любого объекта между двух зеркал и будет называться рекурсией.
В предыдущих примерах с функциями, мы уже знаем что одна функция может вызвать другую функцию. Функция так же может вызывать саму себя. Такие типы функций, называются рекурсивными функциями. Самый лучший метод разъяснения, это конечно же примеры. Ниже приведен пример функции с рекурсией, которая находит факториал числа.
Факториал — это произведение всех числа от 1 до конечного числа. К примеру, факториал цифры 6 (обозначение факториала 6!), 1*2*3*4*5*6 = 720.
Пример рекурсивной функции
В приведенном примере, мы видим, что функция factorialnum(), вызывает саму себя, поэтому она и является рекурсивной функцией. Логика работы этой функции заключается в том, что она каждый раз вызывает саму себя, уменьшая наше конечное число. То есть, функция вызывает саму себя, при этом умножает число на факториал, который ниже самого числа до тех пор, пока она не станет равным единице. Ниже приведен пример, пошагового разбора.
На изображении ниже, приведен пример, на котором изображен процесс всего происходящего в самом коде.
Важно запомнить! При изучении цикла while, мы с вами обсуждали бесконечный цикл. Точно так же, при отсутствии условия, которая останавливает рекурсию, функция будет бесконечно вызывать саму себя. Если мне не изменяет память, то Python ограничивает глубину рекурсии по умолчанию до 1000, при пересечении этого предела, выйдет ошибка RecursionError.
Рассмотрим функцию с таким условием: