Что такое рекурсия в питоне

Рекурсия в Python

Рекурсия — одна из фундаментальных концепций информатики, она важна как для программистов, так и для специалистов по обработке данных. Мало того, что многие алгоритмы сортировки и поиска рекурсивны, но каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это отмечает, что рекурсия является ключевой концепцией, которую необходимо пересмотреть перед любым собеседованием по кодированию.

Сегодня мы поможем вам освежить свои навыки рекурсивного программирования на Python и рассмотрим 6 практических задач, чтобы получить практический опыт.

Что такое рекурсия?

Рекурсия — это концепция в информатике, когда функция вызывает саму себя и выполняет цикл до тех пор, пока не достигнет желаемого конечного условия. Он основан на математической концепции рекурсивных определений, которая определяет элементы в наборе с точки зрения других элементов в наборе.

Каждая рекурсивная реализация имеет базовый случай, когда желаемое состояние было достигнуто, и рекурсивный случай, когда желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг.

Поведение в рекурсивном случае перед вызовом рекурсивной функции, внутренний самовызов, повторяется на каждом шаге. Поэтому рекурсивные структуры полезны, когда вы можете решить более серьёзную проблему (базовый случай), выполнив повторяющиеся подзадачи (рекурсивный случай), которые постепенно перемещают программу к базовому случаю.

Это приводит к поведению, аналогичному циклам for или while, за исключением того, что рекурсия приближается к целевому условию, в то время как for циклы выполняются заданное количество раз, а while циклы выполняются до тех пор, пока условие больше не будет выполняться.

Другими словами, рекурсия декларативна, потому что вы устанавливаете состояние, которого хотите достичь, а for/ while циклы являются итеративными, потому что вам нужно установить количество повторений.

Рекурсивные решения лучше всего подходят, когда проблема имеет чёткие подзадачи, которые необходимо повторить, и если вы не уверены, сколько раз вам нужно будет выполнить цикл с итеративным решением.

Например, если вы хотите создать программу-функцию факториала, которая находит факториал неизвестного числа.

Прямая против косвенной рекурсии

До сих пор мы обсуждали только прямую рекурсию, когда рекурсивная функция явно вызывает себя на своём рекурсивном шаге. Существует также косвенная рекурсия, когда рекурсивный вызов удаляется из функции, но всё ещё выполняется в результате исходного рекурсивного шага.

Например, functionAзвонки functionB, которые потом звонят function Aснова.

Плюсы и минусы рекурсии в Python

Все языки программирования поддерживают рекурсию, однако не все одинаково оптимизированы.

Итерация часто является предпочтительной в Python и считается более «питонической» из-за встроенных оптимизаций. Как правило, рекурсивные решения предпочтительнее итеративных решений при больших вычислениях, поскольку рекурсия часто приводит к меньшему количеству кода и более высокой производительности при масштабировании.

Плюсы

Минусы

Я не добавил удобочитаемости ни в один из столбцов, поскольку некоторые разработчики считают рекурсию более понятной, в то время как другие находят вложенное поведение запутанным. В конечном счёте, это индивидуально для каждой проблемы и разработчика.

Рекурсия в Python

Теперь давайте более подробно рассмотрим рекурсивные функции в Python.

Ниже приведён пример программы, которая рекурсивно печатает шаблон: 10 5 0 5 10.

Источник

Рекурсия в Python

Что такое рекурсия?

Простой пример рекурсии, из реального мира, это два зеркала, которые стоят друг напротив друга. Отражение любого объекта между двух зеркал и будет называться рекурсией.

В предыдущих примерах с функциями, мы уже знаем что одна функция может вызвать другую функцию. Функция так же может вызывать саму себя. Такие типы функций, называются рекурсивными функциями. Самый лучший метод разъяснения, это конечно же примеры. Ниже приведен пример функции с рекурсией, которая находит факториал числа.

Факториал — это произведение всех числа от 1 до конечного числа. К примеру, факториал цифры 6 (обозначение факториала 6!), 1*2*3*4*5*6 = 720.

Пример рекурсивной функции

В приведенном примере, мы видим, что функция factorialnum(), вызывает саму себя, поэтому она и является рекурсивной функцией. Логика работы этой функции заключается в том, что она каждый раз вызывает саму себя, уменьшая наше конечное число. То есть, функция вызывает саму себя, при этом умножает число на факториал, который ниже самого числа до тех пор, пока она не станет равным единице. Ниже приведен пример, пошагового разбора.

На изображении ниже, приведен пример, на котором изображен процесс всего происходящего в самом коде.

Важно запомнить! При изучении цикла while, мы с вами обсуждали бесконечный цикл. Точно так же, при отсутствии условия, которая останавливает рекурсию, функция будет бесконечно вызывать саму себя. Если мне не изменяет память, то Python ограничивает глубину рекурсии по умолчанию до 1000, при пересечении этого предела, выйдет ошибка RecursionError.

Рассмотрим функцию с таким условием:

Преимущества рекурсии

Недостаток рекурсии

Источник

Как работает рекурсия в 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() с использованием рекурсии.

Здесь рекурсивный код функции меньше и прост для понимания. Так что использование рекурсии в этом случае имеет смысл.

Базовый случай

При определении рекурсивной функции должен быть хотя бы один базовый случай, для которого нам известен результат. Затем каждый последующий вызов рекурсивной функции должен приближать ее к базовому случаю.

Это необходимо для того, чтобы в конечном итоге рекурсивные вызовы прекратились. В противном случае функция никогда не завершится и мы получим ошибку нехватки памяти.

Вы можете проверить это поведение в обоих приведенных выше примерах. Аргументы вызова рекурсивной функции становятся все ближе к базовому случаю.

Источник

BestProg

Рекурсия в Python. Примеры решения задач

Содержание

Поиск на других ресурсах:

1. Понятие рекурсии. Рекурсивные функции

Рекурсия — это способ организации циклического процесса путем вызова рекурсивной функции. Рекурсивная функция — это функция, которая содержит код вызова самой себя с целью организации циклического процесса. С помощью рекурсивных функций можно с минимальным объемом кода решать некоторые задачи, обойдя использование (объявление) лишних структур данных. Рекурсию можно рассматривать как альтернативу циклам и итерациям.

2. Примеры решения задач на рекурсию

Вытащив первый элемент из списка с помощью среза, можно передать этот новосозданный список в следующий рекурсивный вызов функции.

Результат выполнения программы

Результат выполнения программы

Если нужно, чтобы рекурсивная функция обрабатывала вложенные списки, то в теле функции нужно реализовать цикл обхода элементов списка. Затем этот элемент нужно проверять, является ли он списком по образцу

Результат выполнения программы

Ряд Фибоначчи содержит числа, в которых следующее число определяется как сумма двух предыдущих чисел:

Нижеприведенная рекурсивная функция формирует ряд Фибоначчи в виде списка для заданного максимального значения в списке.

Результат выполнения программы

В примере приводится функция ReverseNumber() представления числа в обратном порядке. Например, для числа 12345 результат будет 54321.

Результат выполнения функции

Результат выполнения программы

Каждый рекурсивный вызов функции рассматривает список как две составляющие:

Результат выполнения программы

В данном примере, с целью сравнения, реализованы 2 функции, которые конвертируют целое число из десятичной системы исчисления в его аналог в двоичной системе исчисления:

Источник

Пример рекурсии Python

Рекурсия означает возврат назад. Это действие или процедура повторного возврата или повторения функций. Как только функция выполнена и завершена, она запускается автоматически с самого начала. Функция продолжает вызывать себя.

Использование рекурсии

Это математическая концепция, используемая в программировании. Рекурсия — замечательное решение проблем во многих языках программирования. Процесс рекурсии используется, когда нам нужен список результирующих значений до тех пор, пока не будет превышен предел, который мы предоставили в функции, либо в форме вызова функции. При использовании рекурсии сложная функция представляет собой разделение на небольшие подпроцессы. По сравнению с вложенной итерацией, такой как if-else, создание последовательности проще. Рекурсивные функции просты и понятны. Они не делают код запутанным и сложным. С другой стороны, эти функции создают проблему для отладки кода.

Функция рекурсии Python

Разработчики должны быть очень осторожны при обращении с функцией рекурсии, потому что есть вероятность проскальзывания при написании функции, которая никогда не заканчивается или не завершается. Но если код используется с умом, это очень элегантный подход в кодировании. Рекурсия декларативна, потому что мы вводим точку или состояние, которое является пунктом назначения или пиком, которого мы хотим достичь. Мы используем циклы for / while, чтобы упомянуть о необходимых нам здесь ограничениях. Синтаксис рекурсии бывает двух типов. Один без if-else. Другой — с оператором if-else.

Синтаксис

Это простой синтаксис, но функция рекурсии должна использовать условие, чтобы остановить себя.

Вот оператор if, содержащий применяемые условия.

Часть ’if’ содержит такое условие, которое завершает функцию рекурсии, когда условие удовлетворяется; в другом случае функция продолжает вызывать себя. Каждая реализация рекурсивной функции имеет базовый случай, который завершается, когда условие выполняется, и рекурсивный случай, когда желаемая точка не достигается, и функция использует другой рекурсивный шаг. Рассмотрим здесь простой синтаксис; мы использовали функцию. Он имеет базовый регистр в части «if» и рекурсивный случай в части «else».

В базовом случае значение будет возвращено всякий раз, когда выполняется условие.

Случай с рекурсией

Тогда как в случае рекурсии рекурсивная функция снова вызывается с другими конкретными значениями. Это руководство будет включать в себя примеры, поясняющие работу функции рекурсии. Инструмент SPYDER используется для выполнения программ.

Пример 1

В этом примере рассматривается вычисление чисел таким образом, чтобы они отображались в обратном порядке. Функция принимает в качестве аргумента число при вызове функции. Это число затем передается через операторы if-else.

Это базовый вариант. Если число равно 0, это означает, что значение будет возвращено само без каких-либо операций, и функция будет завершена.

В то время как функция обратного отсчета является рекурсивной частью, в другой части тела if.

Вызов функции обеспечивается числом 4. Значит, это не ноль. Часть ’if’ будет игнорироваться, а часть else будет отсчитывать числа от 4 до нуля. И результаты будут отображены. Выполните код; мы получим результат.

Пример 2

Чтобы вычислить в качестве входных данных сумму последовательности от 1 до заданного числа, выбирается цикл for с функцией range ().

For index in range ( n+ 1 ) :
Total + = index

Результат возвращается; это простая функция без каких-либо условий непосредственного завершения. Ответ отображается в консоли вывода. Это сумма суммы от единицы до данного числа.

К этой простой функции мы теперь применяем процедуру рекурсии.

Эта функция будет вызывать сама себя до тех пор, пока число не станет больше нуля. Теперь вы можете видеть, что функция рекурсии краткая и легко читаемая.

Ответ для обоих подходов одинаков. Разница только в случае использования функции рекурсии вместо цикла FOR.

Пример 3

Мы хотим вычислить ряд Фибоначчи с точностью до указанных чисел. Эти серии выглядят как 0,1,1,2,3,5,8 и так далее. Эти серии формируются путем добавления предыдущего числа к текущему значению. Мы используем рекурсивную функцию и оператор if-else для создания этой серии.

If n 1 :
Return n
Else:
Return ( recursive_fib ( n- 1 ) + recursive_fib ( n- 2 ) )

Внутри рекурсивной функции часть else будет иметь рекурсивный вызов. Вызов выполняется дважды, имея дело с оператором вычитания. Предоставленный здесь предел равен 9. Снова оператор if-else используется для обеспечения доступности положительного числа, потому что, если пользователь вводит отрицательное значение, отображается сообщение об ошибке. Причина в том, что ряд Фибоначчи применяется к положительным числам. В то время как для положительного значения функция продолжается. Для процесса печати здесь используется цикл for.

В появившейся консоли вы можете увидеть отображаемую серию. Серию можно продолжить, указав большее число в качестве ввода в коде.

Пример 4

С помощью рекурсивной функции довольно легко вычислить факториал любого числа. Факториал — это число, кратное всем числам в последовательности, пока число не будет использовано в качестве входных данных в коде.

Оператор if-else будет работать вместе для завершения рекурсивной функции.

Допустимость ввода требуется, так как число, введенное для ввода, должно быть положительным, потому что факториал всегда является положительным числом, а не отрицательным. Результатом является целое число, поэтому мы не будем использовать цикл for для печати.

Результирующая консоль отобразит номер после успешного выполнения кода.

Хвостовая рекурсия

Хвостовая рекурсия — это тип, который использует рекурсивный вызов как последнюю процедуру / действие в любом программном коде. Давайте сначала рассмотрим простую рекурсивную функцию. Эта функция вычисляет факториал 5 чисел в обоих примерах, но по-разному.

Это похоже на стандартный факториальный пример; она известна как нерекурсивная функция.

Ответ будет 120. Теперь воспользуемся хвостовой рекурсией. Эта функция включает еще один аргумент в параметре функции. Если n равно 0, то возвращается последнее окончательное значение вычисленного факториала.

Вы можете заметить, что ответ в обоих случаях один и тот же, но использование различается.

Заключение

«Пример рекурсии python» — это статья, в которой освещаются наиболее часто используемые примеры рекурсивных функций. Кратко объясняются оба подхода к выполнению этой функции. В последнем мы попытались проиллюстрировать разницу между хвостовой и нехвостовой рекурсивными функциями на примере. Надеемся, что это руководство будет дополнительным для использования рекурсивной функции в любой области.

Источник