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

21.09.202222.09.2022 admin 0 Comments

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

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

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

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

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

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

Источник

Пример рекурсии 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» — это статья, в которой освещаются наиболее часто используемые примеры рекурсивных функций. Кратко объясняются оба подхода к выполнению этой функции. В последнем мы попытались проиллюстрировать разницу между хвостовой и нехвостовой рекурсивными функциями на примере. Надеемся, что это руководство будет дополнительным для использования рекурсивной функции в любой области.

Источник

BestProg

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

Содержание

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

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

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

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

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