Мәселе кішігірім фрагменттерге тармақталатын, аяқталмайтын сияқты көрінетін циклге тап болдыңыз ба?
Олай болса, сіз қызықты рекурсия әлеміне тап болған боларсыз. Түсіну қиын болып көрінгенімен, уайымдамаңыз! Бұл постта біз рекурсия түрлерімен танысу үшін қызықты саяхатқа шығамыз.
Біз көптеген рекурсивті тәсілдерді зерттеген кезде, бекітіңіз. Рекурсияның қызықты саласына кіруге дайындалыңыз және оның күрделі мәселелерді шешудегі тамаша қабілетін байқаңыз.
Рекурсиялар дегеніміз не?
Негізгі сөзбен айтқанда, рекурсия - орындау кезінде өзін шақыратын функцияны қамтитын қуатты бағдарламалау әдісі. Бұл айнаға қарап, кескіннің ішіндегі кескінді көру сияқты, нәтижесінде өздігінен сілтеме жасау циклі пайда болады.
Біз үлкен мәселелерді рекурсия арқылы оларды кішірек, басқарылатын ішкі мәселелерге бөлу арқылы шеше аламыз.
Бұл толық суретті шығару үшін бір бөлік басқа бөліктермен байланысатын джигсоны біріктіруге ұқсас. Рекурсия әртүрлі кірістермен бірдей нұсқаулар жинағын қайталау арқылы мәселелерді талғампаз және тиімді түрде шешуге мүмкіндік береді.
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
Орау
Рекурсия - бағдарламалаудағы қызықты түсінік. Ол бізге күрделі мәселелерді рекурсивті, өзіндік сілтеме арқылы шешуге мүмкіндік береді.
Ол проблемалар туралы ойлаудың және шешудің нақты әдісін ұсынады, оларды кішірек, басқарылатын бөліктерге бөледі. Алайда, рекурсиямен жұмыс істегенде, кейбір нүктелерге назар аударуды пайдалану өте маңызды.
Рекурсияның аяқталуына мүмкіндік беретін қолайлы негізгі жағдайларды анықтауыңыз керек. Егер олар жоқ болса, функция өзін мәңгілікке шақыра беруі мүмкін.
Екіншіден, қолда бар сценарий негізінде рекурсияның сәйкес түрін таңдау тиімдірек және талғампаз шешімдерге әкелуі мүмкін. Қолыңыздағы мәселеге не қолайлы екенін табуға тырысыңыз. Кең рекурсия тереңдіктерімен жұмыс істегенде, стектің толып кетуі сияқты ықтимал қауіптерден хабардар болыңыз.
пікір қалдыру