Дали некогаш сте биле фатени во навидум бескраен циклус каде што проблемот постојано се разгранува во помали фрагменти?
Ако е така, можеби сте наишле на воодушевувачкиот свет на рекурзија. Иако може да изгледа како предизвик да се разбере, не грижете се! Во овој пост, ќе одиме на интересно патување за да дознаеме за видовите на рекурзии.
Затоа, прицврстете се додека истражуваме бројни рекурзивни пристапи. Подгответе се да влезете во фасцинантното царство на рекурзијата и да ја набљудувате неговата извонредна способност во решавањето комплицирани прашања.
Што точно се рекурзии?
Со основни зборови, рекурзијата е моќна програмска техника која вклучува функција која се повикува себеси за време на извршувањето. Тоа е како да зјапате во огледало и да видите слика во сликата, што резултира со авто-референтен циклус.
Можеме да се справиме со големите проблеми со помош на рекурзија, со тоа што ќе ги делиме на помали, подпроблеми со поголема управливост.
Тоа е слично на составувањето на сложувалка, каде што едно парче се поврзува со други делови за да се добие целосна слика. Рекурзијата ни овозможува да ги решиме проблемите на елегантен и ефикасен начин со повторување на истиот сет на инструкции со различни влезови.
1-Директна рекурзија
Директната рекурзија е најосновниот тип на рекурзија, во која функцијата директно се повикува себеси. Тоа подразбира поделба на проблематичниот проблем на помали потпроблеми додека не се постигне основен случај, што доведува до прекинување.
Рекурзивната функција се повикува себеси со различни влезови, што овозможува извршување на истиот сет на инструкции да се повторува. Секое повикување се надоврзува на претходното, постепено се приближува до основната буква што предизвикува рекурзија да заврши.
Ајде да го провериме овој пример.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
излез:
5
4
3
2
1
2-Индиректна рекурзија
Индиректната рекурзија додава интригантен пресврт на рекурзивната патека. За разлика од директната рекурзија, која вклучува функција која експлицитно се повикува себеси, индиректната рекурзија вклучува синџир на повици на функции.
Една функција повикува друга, која потоа може да ја повика оригиналната функција или која било друга функција што конечно се враќа на оригиналот. Оваа меѓусебно поврзана мрежа од повици на функции создава возбудлив танц во кој неколку функции соработуваат за да го решат проблемот.
Пример:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
излез:
A: 3
B: 2
A: 1
3-Линеарна рекурзија
Размислете за патување по права рута, чекор по чекор, додека не стигнете до целта. Оваа секвенцијална техника е отелотворена со линеарна рекурзија, во која функцијата извршува еден рекурзивен повик во секоја итерација на функцијата.
Со секој рекурзивен повик, рекурзивниот процес се приближува до основната големина со намалување на големината на изданието. Се одвива на јасен и линеарен начин, решавајќи ги потпроблемите еден по еден додека не се постигне конечниот одговор.
Пример:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
излез:
120
4-Рекурзија на дрвото
Кога функцијата се разгранува во неколку рекурзивни повици, влегуваме во светот на рекурзијата на дрвото. Функција во рекурзијата на дрвото генерира многу рекурзивни повици, од кои секој решава посебен потпроблем, исто како што прават гранките на дрвото.
Оваа структура на разгранување овозможува симултано истражување на неколку правци, ефикасно разложувајќи ги комплицираните прашања на помали, меѓусебно поврзани компоненти.
Пример:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
излез:
8
5-вгнездена рекурзија
Вгнездената рекурзија додава возбудлив степен на сложеност на рекурзивниот универзум. Во оваа форма на рекурзија, функцијата вклучува рекурзивен повик како аргумент во друг рекурзивен повик.
Внатрешниот рекурзивен повик делува на вредност која зависи од надворешниот рекурзивен повик. Комплексноста расте со секое вгнездено повикување, кулминирајќи со интригантна шема на вгнездени рекурзивни повици.
Пример:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Резултатот е:
91
6-опашка рекурзија
Рекурзијата на опашката е техника за оптимизација за рекурзивни алгоритми што може да ги подобри нивните перформанси. Рекурзивниот повик се појавува како последно дејство на функција со рекурзија на опашката, правење.
Бидејќи нема извонредни операции по рекурзивниот повик, компајлерот или толкувачот може да ја поедностават рекурзијата со тоа што ќе ја заменат со едноставен скок.
Овој пристап за оптимизација, познат како оптимизација на опашки повик, го намалува барањето за секој рекурзивен повик да ја задржи рамката на стек, што резултира со зголемена брзина и помала употреба на меморијата.
Пример:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Излез:
120
7-Не-опашка рекурзија
За разлика од опашката рекурзија, рекурзијата без опашка вклучува дополнителни активности извршени по рекурзивниот повик во рамките на функцијата. Пред да се извршат повеќе дејства, секој рекурзивен повик мора да заврши и да се врати.
Како последица на тоа, сè додека не се достигне основната форма и рекурзијата не заврши, се одржува куп од извонредни операции. Рекурзијата без опашка често користи повеќе меморија и е помалку ефикасна од рекурзијата на опашката, но сепак е корисна алатка за справување со различни прашања.
Пример:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
излез:
15
Заврши
Рекурзијата е интригантен концепт во програмирањето. Ни овозможува да се справиме со комплицираните проблеми на рекурзивен, самореферентен начин.
Нуди посебен метод на размислување и решавање на проблемите, разложувајќи ги на помали, податливи делови. Меѓутоа, кога работите со рекурзија, важно е да се користи, обрнете внимание на некои точки.
Треба да идентификувате соодветни основни случаи кои овозможуваат завршување на рекурзијата. Ако тие не се присутни, функцијата може да продолжи да се повикува засекогаш.
Второ, врз основа на прифатеното сценарио, изборот на соодветен вид на рекурзија може да доведе до поефикасни и поелегантни решенија. Обидете се да најдете што најдобро функционира за проблемот во раката. Кога работите со огромни длабочини на рекурзија, внимавајте на потенцијалните опасности како што е прелевање на оџакот.
Оставете Одговор