Самые сложные задачи в Python можно разбить на более простые подзадачи. Рекурсия помогает достичь этого, следовательно, делает код чистым и аккуратным. В этом руководстве будут представлены рекурсия, преимущества рекурсии и способы ее использования в программировании на Python.
Что такое рекурсия?
Рекурсия — это метод решения проблемы с решениями меньших экземпляров той же проблемы. Этот подход может быть применен ко многим типам задач в программировании.
Преимущества использования рекурсии
Некоторые из преимуществ использования рекурсии:
- Рекурсия добавляет простоты при написании кода, что облегчает отладку.
- Рекурсия сокращает время, затрачиваемое алгоритмом на выполнение, в зависимости от длины ввода.
- Рекурсия также предпочтительна при решении очень сложных задач, особенно задач на древовидных структурах, потому что она работает лучше.
Введение в рекурсивную функцию Python
Хотя рекурсия кажется сложной процедурой, она не так уж сложна. С точки зрения непрофессионала, предположим, что у вас есть два прямоугольника A и B. Если вы сложите их вместе, они образуют прямоугольник C. Это само по себе рекурсивная процедура. Мы использовали меньшие экземпляры прямоугольника, чтобы определить себя, и если бы мы должны были написать функцию Python, это было бы следующим образом:
|
1
2
|
def rectangle(a,b):
return a+b
|
Поскольку рекурсивная функция вызывает себя сама, должно быть правило или точка останова, в которой процесс или цикл завершатся. Такое состояние известно как базовое условие. Базовое условие является обязательным требованием в каждой рекурсивной программе, иначе процедура приведет к бесконечному циклу.
Второе требование — это рекурсивный случай, когда функция вызывает себя.
Давайте посмотрим на пример:
В этом примере вы напишите факториальную функцию, которая принимает целое число (положительное) в качестве входных данных. Факториал числа получается умножением числа на все натуральные числа ниже него. Например, factorial(3) = 3 x 2 x 1 , factorial(2) = 2 x 1 и factorial(0) = 1 .
Первое, что нужно сделать, это определить наш базовый случай, который будет факториальным (0) = 1.
Как вы можете видеть выше, существует связь между каждым последовательным факториальным сценарием. Вы должны заметить, что факториал (4) = 4 х факториал (3). Аналогично, факториал (5) = 5 х факториал (4).
Вторая часть будет писать функцию, которая вызывает себя.
Теперь, когда мы упростили это, результирующая функция будет:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
def factorial(n):
if(n == 0):
#Define our base case?
return 1
else:
return n*factorial(n-1)
print(factorial(5))
#result
# 120
|
Решение, если n==0 :
|
01
02
03
04
05
06
07
08
09
10
11
12
|
def factorial(n):
if(n == 0):
#Define our base case?
return 1
else:
return n*factorial(n-1)
print(factorial(0))
#result
# 0
|
Теперь, когда вы знаете, как писать рекурсивные функции, давайте рассмотрим несколько примеров, которые укрепят ваше понимание рекурсии.
Пример 1: Фибоначчи
В последовательности Фибоначчи каждое число является суммой двух предыдущих чисел, таких как: 1 + 1 = 2; 1 + 2 = 3; 2 + 3 = 5; 3 + 5 = 8. Последовательность Фибоначчи применяется во многих областях, и наиболее распространенным является прогнозирование ценовых действий на фондовом рынке трейдерами форекс.
Последовательность Фибоначчи начинается с 0 и 1. Первое число в последовательности Фибоначчи 0, второе число 1, а третье слагаемое в последовательности 0 + 1 = 1. Четвертое 1 + 1 = 2 и т. Д. ,
Чтобы создать рекурсивную функцию, вам нужно иметь два базовых варианта, то есть 0 и 1. Затем вы можете перевести шаблон добавления в другой случай.
Результирующая функция будет:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
def fibonacci(n):
if(n == 1):
#define Base case 1
return 0+1
elif(n == 2):
#define Base case 1
return 1+2
else:
return fibonacci(n) + fibonacci(n-1)
print(fibonacci(5))
#result
#
|
Пример 2: реверсирование строки
В этом примере вы напишите функцию, которая принимает строку в качестве входных данных, а затем возвращает обратную строку.
Первое, что нужно сделать, это определить наш базовый случай, который проверит, равна ли строка 0 и, если так, вернет саму строку.
Второй шаг заключается в рекурсивном вызове функции reverse, чтобы разрезать часть строки, исключая первый символ, и затем объединять первый символ с концом нарезанной строки.
Результирующая функция как показано ниже:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
def reverse(a):
if len(a) == 0:
return a
else:
return reverse(a[1:]) + a[0]
print(reverse(«Python is a very easy language to learn»))
# result
#nrael ot egaugnal ysae yrev a si nohtyP
|
Пример 3: сумма элементов
В этом примере вы напишите функцию, которая принимает массив в качестве входных данных, а затем возвращает сумму элементов в списке.
Первое, что нужно сделать, это определить наш базовый случай, который проверит, равен ли размер списка нулю, и вернет 0, если True.
Второй шаг возвращает элемент и вызов функции sum () минус один элемент списка.
Решение, как показано ниже:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
def sum_of_numbers(l):
if len(l) == 1:
return 0
else:
return l[0] + sum(l[1:])
a =[5,7,3,8,10]
print(sum(a))
# result
# 33
|
Решение для пустого списка показано ниже:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
def sum_of_numbers(l):
if len(l) == 1:
return 0
else:
return l[0] + sum(l[1:])
b =[]
print(sum(b))
# result
# 0
|
Вывод
В этом руководстве рассказывается, что необходимо использовать рекурсии для решения сложных программ на Python. Также важно отметить, что рекурсия имеет свои ограничения:
- Рекурсия отнимает много места в стеке, поэтому обслуживание программы выполняется немного медленнее.
- Функции рекурсии требуют больше места и времени для выполнения.
Помните, не стесняйтесь посмотреть, что у нас есть в наличии для продажи и для изучения на рынке Envato , и, пожалуйста, задавайте любые вопросы и оставляйте ценные отзывы, используя канал ниже.