Шта је рекурзивна функција?
Функција себе позива изнова и изнова док не задовољи рекурзивно стање. Рекурзијска функција разбија проблем на мање проблеме и позива своју логику да реши мањи проблем. Ова техника је позната као подјела и побједа. Користи се у математици и пољу рачунарске науке.
Рекурзивна функција укључује базни случај (или терминални случај) и рекурзивни случај. У основном случају можете размотрити главни проблем који треба решити и рекурзивни случај дели проблем на мање делове све док не достигне ниво на коме се може лако решити. Рекурзивни случај може вратити резултат или ће се поново позвати да додатно раздели проблем. Сваки пут када се проблем распада на мањи проблем, функција која се зове рекурзивно спрема стање позива и очекује резултат од себе након разбијања проблема.
Рекурзивна функција у Питхону
Концепт рекурзије остаје исти у Питхону. Функција позива себе да разбије проблем на мање проблеме. Најједноставнији пример који бисмо могли помислити о рецесији било би проналажење фактора из броја.
Рецимо да морамо пронаћи фактороријум броја 5 => 5! (Наш проблем)
Да нађем 5! проблем се може разбити на мање 5! => 5 к 4!
Дакле, да добијем 5! Морамо пронаћи 4! и помножите га са 5.
Наставите да поделимо проблем
5! = 4! к 5
4! = 3! к 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.
- Свака рекурзивна функција има своје рекурзивно стање и основно стање.
Предности и недостаци рекурзивне функције Питхона
- Извођење рекурзије је тако да неће вршити никакве калкулације док не достигне основно стање.
- Ако достигнете основне услове, можда ће вам понестати меморије.
- У великом проблему у којем може бити милион корака или може се рећи милион рекурзија да бисте направили програм може довести до грешке у меморији или грешке сегментације.
- 1000000! = 1000000 * 999999! =?
- Рекурзија је другачија од итерације која се не повећава као итеративна метода.
- Различити језици имају различите оптимизације за рекурзију.
- У многим језицима би итеративни метод био бољи од рекурзије.
- Сваки језик има одређена ограничења у односу на дубину рекурзије са којима можете да се суочите приликом решавања великих проблема.
- Понекад је тешко разумети сложене проблеме са рекурзијом, док је итерација прилично једноставна.
Неке предности
- У неким случајевима, рекурзија је погодан и бржи начин за коришћење.
- Веома корисно за пролазак кроз дрво и бинарну претрагу.
Питхон Цоде - Рекурзија вс Итерација
Разумели смо шта је рекурзија и како то функционише у Питхон-у, јер знамо да сви језици имају различиту примену рекурзије за меморију и рачунске оптимизације. Може постојати случај у којем би итерација била бржа од рекурзије.
Овде бисмо упоредили и методу рекурзије и итерације да бисмо видели како функционише Питхон у оба случаја.
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))
Излаз:
Као што видимо да обе дају исти излаз као што смо написали исту логику. Овде не можемо видети никакву разлику у извршењу.
Додајмо мало времена да добијемо више информација о извођењу рекурзије и итерације у Питхон-у.
Увезићемо библиотеку „времена“ и проверити колико времена и понављања треба да се врати резултат.
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))
Учинићемо поновљена погубљења са другачијом вредностју за факторе и видети резултате. Резултати доле могу варирати од машине до машине. Користили смо МацБоок Про 16 ГБ РАМ и7.
За извршавање користимо Питхон 3.7
Случај 1: - Фактор 6:
Случај 2: Фактор 50:
Случај 3: Фактор 100:
Случај 4: Фактор о 500:
Случај 5: Фактор о 1000:
Анализирали смо обе методе у различитом проблему. Штавише, оба су урадила слично, осим случаја 4.
У случају 5 добили смо грешку док то радимо са рекурзијом.
Питхон је добио ограничење на максималну дубину са којом можете ићи рекурзијом, али исти проблем сам успео да решим итерацијом.
Питхон има ограничења за проблем прелива. Питхон није оптимизован за рекурзију репа, а неконтролисана рекурзија узрокује преливање снопа.
"Сис.гетрецурсионлимит ()" функција ће вам рећи границу за рекурзију.
Граница рекурзије се може мењати, али не препоручује се да би могла бити опасна.
Закључак - рекурзивна функција Питхон-а
- Рекурзија је практично решење за неке проблеме попут преласка дрвећа и других проблема.
- Питхон није функционалан програмски језик и можемо видети да рекурзијски низ није толико оптимизован у поређењу са итерацијом.
- Требали бисмо користити итерацију у нашем алгоритму јер је она оптимизованија у Питхон-у и омогућава вам бољу брзину.
Препоручени чланци
Ово је водич за рекурзивну функцију на Питхон-у. Овде смо расправљали о томе шта су рекурзивна функција, рекурзивна функција у Питхон-у, алгоритам за факторације итд. Такође можете проћи и кроз друге наше предложене чланке да бисте сазнали више -
- Факторориал у Питхон-у
- Команде искричавих граната
- Бест Ц Цомпилерс
- Врсте алгоритама
- Факторски програм у ЈаваСцрипт-у
- Водич до листе команди Уник Схелл-а
- Врсте облика у реакцији са примерима