Желите да научите све о рекурзији у програмирању? Овај водич о рекурзији у Питхон-у ће вам помоћи да почнете.
Рекурзија је супер корисна техника за решавање проблема коју можете додати у алатни оквир вашег програмера. Иако је у почетку често тешко замотати главу, рекурзија вам може помоћи да дођете до елегантнијих решења за сложене проблеме.
У овом туторијалу ћемо применити први приступ учењу рекурзије користећи Питхон. Посебно ћемо покрити:
- Основе рекурзије
- Рекурзивне функције и како оне функционишу
- Питхон имплементација рекурзивних функција
- Разлике између итеративног и рекурзивног приступа решавању проблема
Хајде да почнемо!
Преглед садржаја
Шта је рекурзија?
Рекурзија је техника програмирања у којој се функција више пута позива да би решила проблем.
У својој суштини, рекурзија је приступ решавању проблема који укључује разбијање сложеног проблема на мање, идентичне подпроблеме. У суштини, омогућава вам да решите проблем у смислу једноставнијих верзија самог себе.
Дакле, како да имплементирамо рекурзију у коду? Да бисмо то урадили, хајде да разумемо како функционишу рекурзивне функције.
Разумевање рекурзивних функција
Дефинишемо рекурзивну функцију која сама себе позива у оквиру своје дефиниције. Сваки рекурзивни позив представља мању или једноставнију верзију оригиналног проблема.
Да би се осигурало да се рекурзија на крају заврши, рекурзивне функције морају укључити један или више основних случајева—услова под којима функција престаје да се позива и враћа резултат.
Хајде да ово даље разложимо. Рекурзивна функција се састоји од:
- Основни случај: Основни случај је услов (или услови) који одређују када рекурзија треба да се заустави. Када се испуни основни случај, функција враћа резултат без даљих рекурзивних позива. Основни случај је неопходан да би се спречила бесконачна рекурзија.
- Рекурзивни случај: Рекурзивни случај дефинише како да се проблем разбије на мање подпроблеме. У овом делу функције, функција позива саму себе са модификованим улазима. Сваки рекурзивни позив је, дакле, корак ка достизању основног случаја.
Затим, хајде да разговарамо о томе шта се дешава када позовете рекурзивну функцију.
Како рекурзија функционише испод хаубе
Када се функција позове, запис контекста њеног извршавања се ставља на стек позива. Овај запис укључује информације о аргументима функције, локалним варијаблама и локацији коју треба вратити када функција заврши извршавање.
У случају рекурзивних функција, када функција сама себе позове, нови запис се гура у стек позива, ефективно суспендујући извршавање тренутне функције. Стек омогућава Питхон-у да прати све позиве функција на чекању, укључујући и оне из рекурзивних позива.
Док се не постигне основни случај, рекурзија се наставља. Када основни случај врати резултат, позиви функција се решавају један по један — при чему свака функција враћа свој резултат на претходни ниво стека позива. Овај процес се наставља све док се почетни позив функције не заврши.
Имплементација рекурзије у Питхон-у
У овом одељку ћемо истражити три једноставна примера рекурзије:
За сваки пример ћемо навести проблем, обезбедити Питхон рекурзивну имплементацију, а затим објаснити како рекурзивна имплементација функционише.
#1. Факторско израчунавање помоћу рекурзије
Проблем: Израчунајте факторијел ненегативног целог броја н, означеног са н!. Математички, факторијел броја н је производ свих позитивних целих бројева од 1 до н.
Факторски прорачун је погодан за рекурзију, као што је приказано:
Ево рекурзивне функције за израчунавање факторијела датог броја н:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Хајде да израчунамо 5! користећи факториал() функцију:
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
Сада да видимо како функција функционише:
- Имамо основни случај који проверава да ли је н једнако 0 или 1. Ако је услов испуњен, функције враћају 1. Подсетите се да је 0! је 1, а тако је и 1!.
- Ако је н веће од 1, израчунавамо н! множењем н факторијелом од н-1. Ово се изражава као н * факторијел(н – 1).
- Функција наставља да упућује рекурзивне позиве са опадајућим вредностима од н све док не достигне основни случај.
#2. Фибоначијеви бројеви са рекурзијом
Проблем: Пронађите појам на н-том индексу у Фибоначијев низ. Фибоначијев низ је дефинисан на следећи начин: Ф(0) = 0, Ф(1) = 1 и Ф(н) = Ф(н-1) + Ф(н-2) за н >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Покренимо функцију:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Ево како функција функционише:
- Почнимо са разговором о основним случајевима. Ако је н 0, враћа 0. А ако је н 1, враћа 1. Подсетимо се Ф(0) = 0 и Ф(1) = 1.
- У рекурзивном случају, ако је н веће од 1, функција израчунава Ф(н) додавањем Ф(н-1) и Ф(н-2) чланова. Ово се изражава као фибонацциСек(н – 1) + фибонацциСек(н – 2).
- Функција наставља да упућује рекурзивне позиве са опадајућим вредностима од н све док не достигне основне случајеве.
#3. Рекурзивна имплементација бинарног претраживања
Проблем: Имплементирајте алгоритам бинарног претраживања користећи рекурзију да бисте пронашли позицију циљног елемента у сортираној листи.
Ево рекурзивне имплементације бинарне претраге:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
Функција бинариСеарцх наставља да дели интервал претраге на пола са сваким рекурзивним позивом све док не пронађе циљ или не утврди да циљ није на листи.
Ево примера покретања функције:
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96] target = 37 idx = binarySearch(arr, target, 0, len(arr)-1) print(idx) # Output: 4
Хајде да разложимо шта функција ради:
- У имплементацији рекурзивне бинарне претраге, имамо два основна случаја. Прво, ако лов постане већи од високог, то значи да циљни елемент није на листи. Дакле, враћамо -1 да означимо да циљ није пронађен.
- Други основни случај проверава да ли је елемент у средњем индексу у средини тренутног интервала претраге једнак циљу. Ако се поклапају, враћамо средину индекса, што показује да смо пронашли циљ.
- У рекурзивном случају, ако је средњи елемент већи од циља, рекурзивно претражујемо леву половину низа позивањем бинариСеарцх(арр, таргет, лов, мид – 1). Ако је средњи елемент мањи од циља, тражимо десну половину позивањем бинариСеарцх(арр, таргет, мид + 1, хигх).
Рекурзивни наспрам итеративног приступа
Итеративни приступ – коришћење петљи – је још један уобичајени приступ решавању проблема. Дакле, како се разликује од рекурзије? Хајде да сазнамо.
Прво, упоређујемо рекурзивна и итеративна решења заједничког проблема: израчунавање факторијела броја.
Ево рекурзивне имплементације факторског израчунавања:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Пошто знамо да је факторијел ненегативног броја производ свих бројева од 1 до н, можемо такође написати итеративну имплементацију користећи петље.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Обе ове имплементације дају идентичне резултате.
factorial_5 = factorialRec(5) print(factorial_5) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Али да ли је итеративни приступ пожељнији од рекурзије? Када постоји дубока рекурзија — са превише позива функција — можете наићи на грешке због прекорачења дубине рекурзије. Петља је боља опција за проблеме чија рекурзивна имплементација захтева превише позива функција да би се дошло до основног случаја.
Хајде да сумирамо разлике између итеративних и рекурзивних имплементација:
ФеатуреРецурсиве АппроацхИтеративе АппроацхСтруцтуреКористи рекурзивне позиве функција и ослања се на стек позива.Користи петље за итерацију без додатних позива функција.Основни случајеви Захтева експлицитне основне случајеве за заустављање рекурзије.Уобичајено користи услове петље за завршетак.Перформансе могу бити због мањег меморијског ефекта . Дубока рекурзија понекад може довести до грешака прекорачења стека. Генерално је ефикаснија меморија и мање склона грешкама прекорачења стека. Отклањање грешака може бити изазовно за отклањање грешака због вишеструких позива функција и угнежђених контекста извршавања. Обично је лакше отклонити грешке због једноставног линеарног тока извршења .Итеративни против рекурзивног приступа
Закључак
У овом чланку смо започели учењем шта је рекурзија и како да дефинишемо рекурзивне функције са основним случајевима и рекурзивним односима.
Затим смо написали неки Питхон код — рекурзивне имплементације уобичајених програмских проблема. Коначно, научили смо разлике између итеративног и рекурзивног приступа и предности и недостатке сваког од ових приступа.
Затим погледајте ову листу питања за Питхон интервју.