КОДЕКС
7 примеров понимания функций рекурсии в Python
Мы исследуем рекурсивные функции и примеры, которые можно эффективно использовать.
Рекурсионные функции - это функции, которые повторно используют себя. Его общая цель - помочь решить сложные проблемы, которые могут занять много времени. Написание кода как рекурсивной функции на самом деле не так уж сложно. Однако важная задача ИТ-специалиста - изучить этот инструмент поближе, чтобы знать, где его использовать.
Почему это важно?
Для тех, кто занимается кодированием в целом, задачи, которые нужно автоматизировать, должны выполняться наилучшим образом. На этом этапе простота и ясность могут оправдать самые лучшие ожидания. И использовать рекурсивные функции, как правило, проще, чем использовать циклы ‘for’ или ‘while’.
В этой статье мы не остановимся только на определениях или теоретических знаниях. Мы также включим примеры, которые обеспечат лучшее понимание функций рекурсии. Многие математические функции, такие как факториал или сумма всех предыдущих чисел, являются хорошими примерами этого.
Итак, начнем!
Пример-1: Факториал
Факториалы упрощают организацию последовательных операций в математике. Изучите приведенное ниже обычно определяемое факторное уравнение:
n! = n * (n-1)!
Здесь у нас есть функция, которая постоянно уменьшается и должна где-то останавливаться. Однако мы можем добиться этого с помощью другого уравнения. Итак, чтобы конкретизировать:
(n-1)!=(n-1)*(n-2)!
Базовый вариант
Хотя это дает тот же результат, мы определяем место, где нам нужно остановиться, чтобы этот процесс не продолжался непрерывно. Базовый случай представляет эту точку. Если значение «n» в факториале равно нулю, рекурсия теперь достигает конечной точки и перестает повторяться после этой точки.
Итак, рекурсивная функция обычно имеет следующую структуру:
def recursive_function(parameters):
if base_case_condition(parameters):
return base_case_value
recursive_function(modified_parameters)
Теперь давайте посмотрим, как написать факториальную функцию как функцию в Python:
def factorial(x):
if x == 0:
return 1
else:
return x * factorial(x-1)
Если мы хотим увидеть тот же факторный процесс в другой итеративной ситуации:
def factorial(n):
if n < 2:
return 1
return n * factorial(n-1)
«Базовый вариант» обозначается значком «если» в обоих случаях. И до этого момента функция рекурсии продолжает работать.
Пример-2: Расчет числа Фибоначчи (до 1000)
Расчет числа Фибоначчи может быть решен следующим образом в простой функции, созданной в первую очередь с помощью рекурсии.
def fibonacci(n):
if n <= 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
Однако при использовании этого кода для нескольких чисел может возникнуть проблема со временем. Может быть, вы немного напрягите свою машину. Это потому, что предыдущие пересчитываются при получении каждого числа Фибоначчи. Фибоначчи (4) и фибоначчи (3) для фибоначчи (5), фибоначчи (3) и фибоначчи (2) для фибоначчи (4), фибоначчи (2) и фибоначчи (1) для фибоначчи (3). Итак: «Процессор перегружен», и вы пытаетесь перейти от более сложного к менее сложному.
В качестве альтернативы мы можем разработать решение с итеративной функцией следующим образом, и мы предпочитаем сделать его проще, чем менее сложным:
def fib_faster(n, past=1, current=1):
if n <= 2:
return current
else:
return fib_faster(n-1, current, past+current)
С помощью параметра n мы определяем, сколько операций будет выполнено для поиска следующего члена. Вам понадобится 1 семестр на 3 семестр, 2 раза на 4 семестр, 3 раза на 5 семестр. Поскольку первые два условия принимаются с самого начала, всегда будет +2 условия.
Примечание. Python имеет предел глубины 1000 для рекурсивных функций. Это означает, что у вас есть ограничение на сумму сроков. Вы больше не сможете вернуться. Просто путь к F1000 (тысячный член fibonacci_number) :)
Пример-3: Нахождение суммы до самого числа
Как мы говорили в начале, рекурсия снова вызывает сама себя. Здесь мы также попытаемся вывести все числа перед числом, которое мы обозначим n, как сумму. Итак, давайте настроим функцию ниже и получим сумму чисел до 10:
def print_sum(number):
if number==1:
return 1
else:
return number+print_sum(number-1)
print(print_sum(10))
output:
55
Пример-4: Отображение символов в слове от начала до конца
Мы определим функцию, которая считывает одни и те же символы в слове один за другим слева направо и печатает None с точкой base_case в конце слова. Для этого мы будем использовать функцию len ().
def print_character(word, length):
if length == len(word)-1:
print(word[length])
else:
print(word[length])
print_character(word, length + 1)
word = "Python"
print(print_character(word, 0))
output:
P
y
t
h
o
n
None
Пример-5: Добавление элементов числового массива
Чтобы получить сумму списков и элементов, вызовем каждый из них в обратном порядке и создадим функцию sum_list.
def sum_list(lst,length):
if length==0:
return lst[0]
else:
return lst[length]+sum_list(lst,length-1)
lst=[1,2,3,4,5]
print(sum_list(lst,len(lst)-1))
output:
15
Пример 6: Вычисление положительных делителей числа
Мы напишем функцию, которая выражает числа путем деления их на их делители. Число, которое мы укажем в функции, будет разделено на цифры от 1 до самого числа. Однако нам не нужна оставшаяся часть этого раздела. Для этого, если мы возьмем 12, например, мы ожидаем возврата 1,2,3,4,6,12. В конце функция вернет само число. В этом случае функция:
def positive_divisor(number,i):
if number%i==0:
print(i)
elif number==i:
return number
return positive_divisor(number,i+1)
print(positive_divisor(63,1))
output:
1
3
7
9
21
63
Пример-7: Возврат подмножеств набора списков
Это, пожалуй, самый сложный пример. Возвращает различные комбинации элементов, составляющих список, в соответствии с определением подмножеств в предметных наборах, которые также известны в математике. По этой причине необходимо кодировать две разные ключевые функции.
Во-первых: с помощью функции «Добавить элементы» мы позаботимся о том, чтобы определенные элементы или элементы внутреннего списка были добавлены к существующему списку. Для этого нам нужен добавляемый элемент и список.
Во-вторых: с помощью функции «Показать подмножества» мы продолжим чередовать различные списки, включая добавление элементов, до тех пор, пока не будет достигнута точка базового случая.
Итак, сначала для функции «add_elements»:
def add_elements(e, lst): # adds the element to each list in the lst
if lst == []:
return []
else:
return [lst[0] + [e]] + add_elements(e, lst[1:])
print(add_elements('add',[['a'],['d'],['d']]))
output:
[['a', 'add'], ['d', 'add'], ['d', 'add']]
Теперь давайте перечислим подмножества нашего набора примеров, объединив нашу функцию, показывающую подмножества, с указанной выше функцией.
Примечание. Пустой набор - это подмножество каждого набора. Поэтому это важный совет для базового случая.
Мы представим пустой набор с помощью [].
Итак, base_case равен: lst == []
С формулой → 2 * * количество элементов
def show_subsets(lst):
if len(lst) == 0:
return [[]]
else:
return show_subsets(lst[:-1]) + add_elements(lst[-1], show_subsets(lst[:-1]))
print(sorted(show_subsets(["x","y","z"])))
output:
[[], ['x'], ['x', 'y'], ['x', 'y', 'z'], ['x', 'z'], ['y'], ['y', 'z'], ['z']]
Заключение
Мы рассмотрели 7 различных примеров, чтобы лучше понять функции рекурсии в Python. Целью этой статьи было включить применимые функции. Я надеюсь, что стало легче понять идеальные функции для вычислений, многие из которых знакомы тем, кто уже занимается математикой.
Спасибо за чтение!
использованная литература
(1): Источник изображения, использованного в созданном изображении: https://commons.wikimedia.org/wiki/File:FibonacciSpiral.svg
