Рекурсия — это способ организации циклического процесса путем вызова рекурсивной функции. Рекурсивная функция — это функция, которая содержит код вызова самой себя с целью организации циклического процесса. С помощью рекурсивных функций можно с минимальным объемом кода решать некоторые задачи, обойдя использование (объявление) лишних структур данных. Рекурсию можно рассматривать как альтернативу циклам и итерациям.
2. Примеры решения задач на рекурсию
2.1. Функция CalcSumNumbers() . Вычислить сумму элементов набора чисел
В примере реализована рекурсивная функция CalcSumNumbers() , которая осуществляет суммирование чисел во входящем списке. В работе функции входящий список A разделяется на 2 части:
- первый элемент списка A[0] ;
- все остальные элементы списка кроме первого. Эти элементы выделяются при помощи среза A[1:] .
Вытащив первый элемент из списка с помощью среза, можно передать этот новосозданный список в следующий рекурсивный вызов функции.
Python с нуля. Урок 3 | Функции
# Рекурсивная функция — возвращает сумму чисел во входящем наборе def CalcSumNumbers(A): if A == []: # если набор пуст, возвратить 0 return 0 else: # Вычислить сумму — прибавить первый элемент набора summ = CalcSumNumbers(A[1:]) # рекурсивный вызов этой же функции # Прибавить к общей сумме первый элемент summ = summ + A[0] return summ # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ 2, 3, 8, 11, 4, 6 ] # 2. Вызвать функцию summ = CalcSumNumbers(L) # 3. Распечатать сумму print(«summ color: #333300;»>⇑
2.2. Функция CalcSumNegativeNumbers(). Вычислить количество отрицательных чисел в наборе
По предыдущим примеру (п. 4.1) реализуется функция CalcSumNegativeNumbers(), которая вычисляет количество отрицательных чисел в списке (наборе). Опять же, из входного списка выделяется первый элемент и все другие элементы.
# Рекурсивная функция — возвращает количество отрицательных чисел в списке def CalcSumNegativeNumbers(A): if A == []: # если набор пуст, вернуть 0 return 0 else: # Вычислить количество, перейти к дальнейшей обработке # без без первого элемента count = CalcSumNegativeNumbers(A[1:]) # рекурсивный вызов этой же функции # Увеличить на 1 при условии, что текущее число отрицательно if A[0]return count # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ -2, 3, 8, -11, -4, 6 ] # 2. Вызвать функцию n = CalcSumNegativeNumbers(L) # 3. Распечатать сумму print(«n color: #333300;»>⇑
2.3. Функция CalcSumNumbers(). Вычисление суммы чисел с поддержкой вложенных списков
Если нужно, чтобы рекурсивная функция обрабатывала вложенные списки, то в теле функции нужно реализовать цикл обхода элементов списка. Затем этот элемент нужно проверять, является ли он списком по образцу
if not isinstance(t, list): .
здесь t – элемент, который проверяется с помощью функции isinstance() .
# Рекурсивная функция — возвращает сумму чисел, обрабатывает вложенные списки def CalcSumNumbers(A): summ = 0 # здесь нужно реализовать обход в цикле for t in A: # Обрабатывается элемент t if not isinstance(t, list): # проверить, есть ли t списком summ = summ + t # если t — не список, то прибавить его к сумме else: # получить сумму из следующих рекурсивных вызовов summ = summ + CalcSumNumbers(t) return summ # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ -2, 3, 8, 11, [-4, 6, [ 2, [-5, 4] ] ] ] # 2. Вызвать функцию summ = CalcSumNumbers(L) # 3. Распечатать сумму print(«summ color: #333300;»>⇑
2.4. Функция GetFibonacciList(). Возврат ряда Фибоначчи
Ряд Фибоначчи содержит числа, в которых следующее число определяется как сумма двух предыдущих чисел:
41 Рекурсия в Python. Рекурсивная функция Часть 1
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, .
Нижеприведенная рекурсивная функция формирует ряд Фибоначчи в виде списка для заданного максимального значения в списке.
2.5. Функция ReverseNumber() . Реверсирование числа
В примере приводится функция ReverseNumber() представления числа в обратном порядке. Например, для числа 12345 результат будет 54321.
Функция получает входным параметром целое число number . Функция возвращает целое реверсированное число.
# Рекурсия. Реверсирование числа import math # Рекурсивная Функция def ReverseNumber (num): # 1. Проверка, корректно ли число if num0), то обработать его # 3.1. Определить порядок числа (количество цифр в числе) n_digit = 0 # порядок числа num2 = num # копия num while num2>0: n_digit = n_digit+1 num2 = num2//10 # 3.2. Взять последнюю цифру из числа t = num%10 # 123456 => 6 # 3.3. Умножить последнюю цифру на 10^n_digit res = t * int (math.pow(10, n_digit-1)) # 3.4. Вернуть сумму с вызовом рекурсивной функции return res + ReverseNumber(num//10) # Демонстрация использования функции num = 1234000567 rnum = ReverseNumber(num) # rnum = 7650004321 print ( «rnum color: #333300;»>⇑
2.6. Функция Power(x, y) . Возведение числа x в степень y
Рекурсивная функция Power(x, y) возвращает результат возведения действительного числа x в целую степень y . Предварительно предполагается, что значение y>0 .
# Рекурсия. Возведение числа x в степень y # Рекурсивная функция def Power (x, y): if y>0: return x * Power(x, y-1) else : return 1 # Демонстрация использования функции Power() x = 3 y = 4 res = Power(x, y) print ( «res color: #333300;»>⇑
2.7. Функция GetMaxList() . Определение максимального элемента списка
В примере реализована функция GetMaxList() , которая вычисляет максимальный элемент списка. Вся работа функции разделена на 2 части:
- выполнение действий, если в списке два и более чисел;
- выполнение действий, если список заканчивается, то есть рассматривается последний элемент.
Каждый рекурсивный вызов функции рассматривает список как две составляющие:
- первый элемент списка (элемент с индексом 0);
- следующие за первым элементы списка (элементы с индексами 1, 2, и т.д.).
# Рекурсивная функция. Определить максимальный элемент списка def GetMaxList (L): if len (L)>1: # Получить максимум из следующих рекурсивных вызовов Max = GetMaxList(L[1:]) # Сравнить максимум с первым элементом списка if L[0]⇑
2.8. Функция Convert_10_to_2() . Перевод из десятичной системи исчисления в двоичную
В данном примере, с целью сравнения, реализованы 2 функции, которые конвертируют целое число из десятичной системы исчисления в его аналог в двоичной системе исчисления:
- Convert_10_to_2_R() — это рекурсивная функция конвертирования числа;
- Convert_10_to_2() — не рекурсивная функция.
Для обеспечения решении задачи, в нерекурсивной версии Convert_10_to_2() вводится дополнительная переменная k , которая определяет порядок полученного двоичного числа. Для того, чтобы сохранять этот порядок k в рекурсивной версии функции Convert_10_to_2_R() , нужно его передавать в эту функцию вторым параметром.
import math # Рекурсивная функция. Перевод числа из 10-й системы исчисления в двоичную. # Функция возвращает результат в виде числа: 13 => 1101. # Параметры: # — n — число в десятичной системе исчисления; # — k — текущий порядок (количество цифр) числа в двоичной системе. def Convert_10_to_2_R (n, k): if n>0: t = n%2 return Convert_10_to_2_R(n//2, k+1) + int (t*math.pow(10,k)) else : return 0 # Не рекусивная функция перевода def Convert_10_to_2 (n): summ = 0 # сумма чисел: 5 => 100 + 0 + 1 => 101 k = 0 # порядок числа в двоичной системе исчисления while n>0: t = n%2 summ = summ + int (t*math.pow(10,k)) k = k+1 n = n//2 return summ # Демонстрация использования функций res1 = Convert_10_to_2_R(126, 0) # Вызов рекурсивной функции res2 = Convert_10_to_2(126) # Вызов нерекурсивной функции print ( «res1 color: #800080;»>print ( «res2 color: #333300;»>⇑
Связанные темы
- Понятие функции. Общая форма. Примеры объявления и использования функций
- Передача аргументов в функцию. Изменение аргументов в теле функции
Источник: www.bestprog.net
Как работает рекурсия в python?
Когда функция вызывает сама себя, она называется рекурсивной функцией. В этом руководстве мы узнаем, как написать функцию рекурсии Python.
Что такое рекурсия в Python?
Когда функция определена таким образом, что она вызывает сама себя, она называется рекурсивной функцией. Это явление называется рекурсией. Python поддерживает рекурсивные функции.
Рекурсия очень похожа на цикл, в котором функция вызывается на каждой итерации. Вот почему мы всегда можем использовать циклы как замену функции рекурсии Python.
Но некоторые программисты предпочитают рекурсию циклам. В основном это вопрос выбора, и вы можете использовать циклы или рекурсию.
Примеры
Следующий код возвращает сумму первых n натуральных чисел, используя рекурсивную функцию python.
def sum_n(n): if n== 0: return 0 else: return n + sum_n(n-1)
Это печатает сумму первых 100 натуральных чисел и первых 500 натуральных чисел
print(sum_n(100)) print(sum_n(500))
C:/Users/TutorialsPoint1/~.py 5050 125250
1. Факториал целого числа
Факториал целого числа вычисляется путем умножения целых чисел от 1 до этого числа.
Например, факториал 10 будет 1 * 2 * 3…. * 10.
Давайте посмотрим, как мы можем написать факториальную функцию с помощью цикла for.
def factorial(n): result = 1 for i in range(1, n + 1): result = result * i return result print(f’Factorial of 10 = ‘) print(f’Factorial of 5 = ‘)
Давайте посмотрим, как мы можем изменить функцию factorial() для использования рекурсии.
def factorial(n): if n == 1: return 1 else: return n * factorial(n — 1) print(f’Factorial of 10 = ‘) print(f’Factorial of 5 = ‘)
На изображении ниже показано выполнение рекурсивной функции.
2. Ряд Фибоначчи
Ряд Фибоначчи — это последовательность чисел, каждое из которых представляет собой сумму двух предыдущих чисел. Например — 1, 1, 2, 3, 5, 8, 13, 21 и так далее.
Давайте посмотрим на функцию для возврата чисел ряда Фибоначчи с помощью циклов.
def fibonacci(n): «»» Returns Fibonacci Number at nth position using loop»»» if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range(1, n): num = i1 + i2 i1 = i2 i2 = num return num for i in range(10): print(fibonacci(i), end=» «) # Output: 0 1 1 2 3 5 8 13 21 34
Вот реализация функции fibonacci() с использованием рекурсии.
def fibonacci(n): «»» Returns Fibonacci Number at nth position using recursion»»» if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n — 1) + fibonacci(n — 2) for i in range(10): print(fibonacci(i), end=» «) # Output: 0 1 1 2 3 5 8 13 21 34
Здесь рекурсивный код функции меньше и прост для понимания. Так что использование рекурсии в этом случае имеет смысл.
Базовый случай
При определении рекурсивной функции должен быть хотя бы один базовый случай, для которого нам известен результат. Затем каждый последующий вызов рекурсивной функции должен приближать ее к базовому случаю.
Это необходимо для того, чтобы в конечном итоге рекурсивные вызовы прекратились. В противном случае функция никогда не завершится и мы получим ошибку нехватки памяти.
Вы можете проверить это поведение в обоих приведенных выше примерах. Аргументы вызова рекурсивной функции становятся все ближе к базовому случаю.
Преимущества
- Иногда рекурсия уменьшает количество строк кода.
- Код выглядит просто.
- Если мы знаем базовый случай, тогда использовать в функции проще.
Недостатки
- Если не реализовано должным образом, функция никогда не завершится.
- Понимание рекурсии вызывает большую путаницу по сравнению с циклами.
Источник: pythononline.ru
Рекурсия в Python
Если бы я хотел узнать сумму чисел от 1 до n, где n — натуральное число, я мог бы посчитать вручную 1 + 2 + 3 + 4 + . + (несколько часов спустя) + n. А можно просто написать цикл for :
n = 0 for i in range (1, n+1): n += i
Или использовать рекурсию:
def recursion(n): if n == 1: return 1 return n + recursion(n — 1)
У рекурсии есть несколько преимуществ в сравнении с первыми двумя методами. Рекурсия занимает меньше времени, чем выписывание 1 + 2 + 3 на сумму от 1 до 3.
Для recusion(4) рекурсия может работать в обратную сторону:
Вызов функций: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
Принимая во внимание, что цикл [for] работает строго вперед: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Иногда рекурсивное решение проще, чем итеративное решение. Это очевидно при реализации обращения связанного списка.
Как и когда происходит рекурсия
Рекурсия появляется когда вызов функции повторно вызывает ту же функцию до завершения первоначального вызова функции. Например, рассмотрим известное математическое выражение x! (т.е. факториал). Факториал определяется для всех неотрицательных целых чисел следующим образом:
Если число равно 0, то будет 1.
В противном случае ответом будет то, что число умножается на факториал на единицу меньше этого числа.
В Python наивная реализация факториала может быть определена как функция следующим образом:
def factorial(n): if n == 0: return 1 else: return n * factorial(n — 1)
Иногда функции рекурсии трудно понять, поэтому давайте рассмотрим поэтапно.
Рассмотрим выражение factorial(3) . Эта и все остальные вызовы функций создают новую среду. Среда представляет собой таблицу, которая сопоставляет идентификаторы (например, n, factorial, print и т.д.) с их соответствующими значениями.
В любой момент времени вы можете получить доступ к текущей среде с помощью locals() . В первом вызове функции единственная локальная переменная, которая определяется n = 3 .Поэтому locals() будет показывать . Так как n == 3 , возвращаемое значение становится n * factorial(n — 1) .
На следующем этапе ситуация может немного запутаться. Глядя на наше новое выражение, мы уже знаем, что такое n . Однако мы еще не знаем, что такое factorial(n — 1) .
Во-первых, n — 1 принимает значение 2 .Затем 2 передаётся factorial как значение для n . Поскольку это новый вызов функции, создаётся вторая среда для хранения нового n .
Пусть A — первое окружение, а B — второе окружение. A всё ещё существует и равен , однако B (что равно ) является текущей средой. Если посмотреть на тело функции, возвращаемое значение, опять же, n * factorial(n — 1) .
Не определяя это выражение, заменим его на исходное выражение return . Делая это, мы мысленно отбрасываем B , поэтому не забудьте заменить n соответственно (т.е. ссылки на B n заменены на n — 1) который использует A n ). Теперь исходное обратное выражение становится n * ((n — 1) * factorial((n — 1) — 1)) . Подумайте, почему так?
Теперь давайте определим factorial((n — 1) — 1)) . Так как A n == 3 , мы пропускаем 1 через factorial . Поэтому мы создаем новую среду C, которая равна . Мы снова возвращаем значение n * factorial(n — 1) . Итак, заменим исходный factorial((n — 1) — 1)) выражения return аналогично тому, как раньше мы скорректировали исходное выражение return. Исходное выражение теперь n * ((n — 1) * ((n — 2) * factorial((n — 2) — 1))) .
Почти закончили. Теперь нам нужно оценить factorial((n — 2) — 1) . На этот раз мы пропустим через 0 . Следовательно, должно получиться 1 .
Теперь давайте проведём нашу последнюю замену. Исходное выражение return теперь n * ((n — 1) * ((n — 2) * 1)) . Напомню, что исходное выражение возврата оценивается под A , выражение становится 3 * ((3 — 1) * ((3 — 2) * 1)) . Здесь получается 6.
Чтобы убедиться, что это правильный ответ, вспомните, что 3! == 3 * 2 * 1 == 6 . Прежде чем читать дальше, убедитесь, что вы полностью понимаете концепцию среды и то, как они применяются к рекурсии.
Утверждение, if n == 0: return 1 , называется базовым случаем. Потому что это не рекурсия. Базовый случай необходим, без него вы столкнетесь с бесконечной рекурсией. С учетом сказанного, если у вас есть хотя бы один базовый случай, у вас может быть столько случаев, сколько вы хотите. Например, можно записать факториал таким образом:
def factorial(n): if n == 0: return 1 elif n == 1: return 1 else: return n * factorial(n — 1)
У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в подробности, потому что это редкий случай, и его трудно мысленно обрабатывать.
Вы также можете иметь «параллельные» рекурсивные вызовы функций. Например, рассмотрим последовательность Фибоначчи, которая определяется следующим образом:
- Если число равно 0, то ответ равен 0.
- Если число равно 1, то ответ равен 1.
В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.