Какво е рекурсивна функция?
Функцията се обажда отново и отново, докато удовлетвори рекурсивно условие. Рекурсионната функция разгражда проблема на по-малки проблеми и извиква собствената си логика за решаване на по-малкия проблем. Тази техника е известна като разделяне и завладяване. Използва се в математиката и в областта на компютърните науки.
Рекурсивната функция включва основен случай (или терминален случай) и рекурсивен случай. В основния случай можете да разгледате основния проблем за решаване и рекурсивният случай разделя проблема на по-малки части, докато достигне ниво, където той може да бъде решен лесно. Рекурсивният случай може да върне резултат или може да се обади отново, за да раздели допълнително проблема. Всеки път, когато проблемът се разпада на по-малък проблем, функцията, която се нарича рекурсивно, запазва състоянието на повикването и очаквайте резултата от себе си след разрушаване на проблема.
Рекурсивна функция в Python
Концепцията за рекурсия остава същата в Python. Функцията призовава себе си да разбие проблема на по-малки проблеми. Най-простият пример, за който можем да мислим за рекурсия, е намирането на фактор на число.
Да речем, че трябва да намерим фабриката на числото 5 => 5! (Нашият проблем)
Да намерим 5! проблемът може да бъде разбит на по-малки 5! => 5 x 4!
И така, за да получите 5! Трябва да намерим 4! и го умножете с 5.
Нека продължим да разделяме проблема
5! = 4! х 5
4! = 3! x 4
3! = 3 х 2!
2! = 2 х 1!
1! = 1
Когато достигне най-малкия къс, т.е. получавайки фактор от 1, можем да върнем резултата като
Нека вземем пример за псевдокод: -
Алгоритъм за факториал
Нека видим алгоритъма за факториал:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Функционални обаждания
Да предположим, че намираме фактория от 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Крайният резултат ще бъде 120, където започнахме изпълнението на функцията. Рекурсионната ни функция ще спре, когато числото е толкова намалено, че резултатът може да бъде получен.
- Първият разговор, който получава фабричен 5, ще доведе до рекурсивно състояние, при което той ще бъде добавен към стека, а друго повикване ще бъде извършено след намаляване на числото до 4.
- Тази рекурсия ще продължи да се обажда и да разбие проблема на по-малки парчета, докато достигне базовото състояние.
- Основното условие тук е, когато числото е 1.
- Всяка рекурсивна функция има собствено рекурсивно състояние и основно условие.
Плюсовете и минусите на рекурсивната функция на Python
- Изпълнението на рекурсия е така, че да не прави никакви изчисления, докато не достигне базово състояние.
- При достигане на базови условия може да ви липсва памет.
- В голям проблем, при който може да има милион стъпки или можем да кажем милион рекурсии за извършване на програмата, може да се стигне до грешка в паметта или грешка в сегментацията.
- 1000000! = 1000000 * 999999! =?
- Рекурсията е различна от итерацията, която не се увеличава като итеративен метод.
- Различните езици имат различни оптимизации за рекурсия.
- В много езици итеративният метод би се получил по-добре от рекурсията.
- Всеки език има някои ограничения за дълбочината на рекурсия, с които може да се сблъскате, когато решавате големи проблеми.
- Понякога е трудно да се разберат сложните проблеми с рекурсията, докато с итерацията е доста проста.
Някои плюсове
- В някои случаи рекурсията е удобен и по-бърз начин за използване.
- Много полезен при преминаването на дървото и двоичното търсене.
Python Code - Рекурсия срещу итерация
Разбрахме какво е рекурсия и как тя работи в Python, тъй като знаем, че всички езици имат различна реализация на рекурсия за памет и изчислителни оптимизации. Може да има случай, при който повторението да бъде по-бързо от рекурсията.
Тук бихме сравнили рекурсията и метода на итерация, за да видим как Python се представя в двата случая.
1. Рекурсионен код за фактор
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Факторен проблем при използване на итерация (циклично)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Печат на резултатите
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
изход:
Както виждаме и двете дават еднакъв изход, както сме написали една и съща логика. Тук не можем да видим разлика в изпълнението.
Нека добавим времеви код, за да получим повече информация за изпълнението на рекурсия и итерация в Python.
Ще импортираме библиотеката „време“ и ще проверим колко време са необходими рекурсия и итерация, за да върнем резултата.
4. Код с изчисление на времето
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Ще правим многократни екзекуции с различна стойност за фактория и ще видим резултатите. По-долу резултатите могат да варират от машина до машина. Използвахме MacBook Pro 16 GB RAM i7.
Използваме Python 3.7 за изпълнение
Случай 1: - Фактор на 6:
Случай 2: Фактор на 50:
Случай 3: Фактор на 100:
Случай 4: Фактор на 500:
Случай 5: Фактор на 1000:
Анализирахме и двата метода в различен проблем. Освен това и двамата са се представили сходно, с изключение на случай 4
В случай 5 получихме грешка, докато го правихме с рекурсия.
Python получи ограничение на максималната дълбочина, на която можете да преминете с рекурсия, но същия проблем успях да го реша с итерация.
Python има ограничения срещу проблема с преливането. Python не е оптимизиран за рекурсия на опашката и неконтролирана рекурсия причинява препълване на стека.
Функцията „sys.getrecursionlimit ()“ ще ви каже границата за рекурсия.
Ограничението за рекурсия може да бъде променено, но не се препоръчва, може да бъде опасно.
Заключение - рекурсивна функция на Python
- Рекурсията е удобно решение за някои проблеми като обиколка на дървета и други проблеми.
- Python не е функционален език за програмиране и можем да видим, че стекът на рекурсия не е толкова оптимизиран в сравнение с итерацията.
- Трябва да използваме итерацията в нашия алгоритъм, тъй като е по-оптимизирана в Python и ви дава по-добра скорост.
Препоръчителни статии
Това е ръководство за рекурсивна функция в Python. Тук обсъждаме какво е рекурсивна функция, рекурсивна функция в Python, алгоритъм за факториал и др. Можете също да прегледате и другите ни предложени статии, за да научите повече -
- Факториал в Python
- Spark Shell Commands
- Най-добрите компилатори на C
- Видове алгоритми
- Факторна програма в JavaScript
- Ръководство за списъка на командите на Unix Shell
- Видове форми в реагиране с примери