Դուք երբևէ հայտնվել եք անվերջ թվացող ցիկլի մեջ, որտեղ խնդիրը շարունակում է ճյուղավորվել ավելի փոքր բեկորների:
Եթե այո, ապա դուք կարող եք հայտնվել ռեկուրսիայի հրապուրիչ աշխարհում: Թեև դա կարող է դժվար լինել հասկանալը, մի անհանգստացեք: Այս գրառման մեջ մենք կանցնենք հետաքրքիր ճամփորդության՝ ծանոթանալու ռեկուրսիաների տեսակներին:
Այսպիսով, կապվեք, երբ մենք ուսումնասիրում ենք բազմաթիվ ռեկուրսիվ մոտեցումներ: Պատրաստվեք մտնելու ռեկուրսիայի հետաքրքրաշարժ տիրույթ և դիտարկեք նրա ուշագրավ կարողությունը բարդ հարցեր լուծելու գործում:
Ի՞նչ են իրականում ռեկուրսիաները:
Հիմնական բառերով, ռեկուրսիան հզոր ծրագրավորման տեխնիկա է, որը ներառում է կատարման ընթացքում իրեն կանչող ֆունկցիա: Դա նման է հայելու մեջ նայելուն և պատկերի ներսում պատկեր տեսնելուն, ինչը հանգեցնում է ինքնատեղեկացման ցիկլին:
Մենք կարող ենք լուծել մեծ խնդիրները՝ օգտագործելով ռեկուրսիա՝ դրանք բաժանելով ավելի փոքր, ավելի կառավարելի ենթախնդիրների:
Դա նման է ոլորահատ սղոց հավաքելուն, որտեղ մի կտորը միանում է մյուս մասերին՝ ամբողջական պատկեր ստեղծելու համար: Recursion-ը թույլ է տալիս մեզ լուծել հարցերը նրբագեղ և արդյունավետ կերպով՝ կրկնելով հրահանգների նույն փաթեթը տարբեր մուտքերով:
1-Ուղիղ ռեկուրսիա
Ուղղակի ռեկուրսիան ռեկուրսիայի ամենահիմնական տեսակն է, որում ֆունկցիան ուղղակիորեն կանչում է իրեն։ Դա ենթադրում է խնդրահարույց խնդիրը ավելի փոքր ենթախնդիրների բաժանում, մինչև բազային գործը ձեռք բերվի, ինչը հանգեցնում է դադարեցման:
Ռեկուրսիվ ֆունկցիան իրեն կանչում է տարբեր մուտքերով, ինչը հնարավորություն է տալիս կրկնել հրահանգների նույն փաթեթի կատարումը: Յուրաքանչյուր կոչ հիմնվում է նախորդի վրա՝ աստիճանաբար մոտենալով բազային գործին, որը հանգեցնում է ռեկուրսիային ավարտին:
Եկեք ստուգենք այս օրինակը:
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Արդյունք:
5
4
3
2
1
2-Անուղղակի ռեկուրսիա
Անուղղակի ռեկուրսիան ավելացնում է ինտրիգային շրջադարձ ռեկուրսիվ ճանապարհին: Ի տարբերություն ուղղակի ռեկուրսիայի, որը ներառում է իրեն բացահայտորեն կանչող ֆունկցիա, անուղղակի ռեկուրսիան ներառում է ֆունկցիայի կանչերի շղթա։
Մի ֆունկցիան կանչում է մյուսին, որն այնուհետև կարող է կանչել սկզբնական ֆունկցիան կամ ցանկացած այլ ֆունկցիա, որը վերջապես վերադառնում է բնօրինակին: Ֆունկցիոնալ զանգերի այս փոխկապակցված ցանցը ստեղծում է մի հուզիչ պար, որում մի քանի գործառույթներ համագործակցում են խնդիրը շտկելու համար:
Example:
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-Գծային ռեկուրսիա
Մտածեք ուղիղ ճանապարհով ուղևորություն՝ քայլ առ քայլ, մինչև հասնեք ձեր նպատակին: Այս հաջորդական տեխնիկան մարմնավորվում է գծային ռեկուրսիայով, որի դեպքում ֆունկցիան կատարում է մեկ ռեկուրսիվ կանչ յուրաքանչյուր ֆունկցիայի կրկնության մեջ:
Յուրաքանչյուր ռեկուրսիվ զանգի դեպքում ռեկուրսիվ գործընթացն ավելի է մոտենում բազային գործին` նվազեցնելով թողարկման չափը: Այն ընթանում է պարզ և գծային ձևով, ենթախնդիրները մեկ առ մեկ լուծելով մինչև վերջնական պատասխանի հասնելը:
Example:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Արդյունք:
120
4-Ծառի հետադարձ
Երբ ֆունկցիան ճյուղավորվում է մի քանի ռեկուրսիվ կանչերի, մենք մտնում ենք ծառի ռեկուրսիայի աշխարհ: Ծառի ռեկուրսիայում ֆունկցիան առաջացնում է բազմաթիվ ռեկուրսիվ կանչեր, որոնցից յուրաքանչյուրը լուծում է առանձին ենթախնդիր, ճիշտ ինչպես ծառի ճյուղերը։
Այս ճյուղավորվող կառուցվածքը թույլ է տալիս միաժամանակ ուսումնասիրել մի քանի երթուղիներ՝ արդյունավետորեն բաժանելով բարդ խնդիրները փոքր, փոխկապակցված բաղադրիչների:
Example:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Արդյունք:
8
5-Ներկուրսիա
Nested recursion-ը ռեկուրսիվ տիեզերքին ավելացնում է բարդության հետաքրքիր աստիճան: Ռեկուրսիայի այս ձևում ֆունկցիան ներառում է ռեկուրսիվ կանչ՝ որպես արգումենտ մեկ այլ ռեկուրսիվ կանչի մեջ:
Ներքին ռեկուրսիվ կանչը գործում է մի արժեքի վրա, որը կախված է արտաքին ռեկուրսիվ զանգից: Բարդությունն աճում է յուրաքանչյուր ներդիր կանչի հետ՝ հասնելով ինտրիգային ինտրիգային օրինաչափության՝ տեղադրված ռեկուրսիվ զանգերի:
Example:
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-Պոչի հետադարձ
Tail recursion-ը ռեկուրսիվ ալգորիթմների օպտիմալացման տեխնիկա է, որը կարող է բարելավել դրանց կատարումը: Ռեկուրսիվ կանչը հայտնվում է որպես պոչի ռեկուրսիայով ֆունկցիայի վերջնական գործողություն՝ կատարելով:
Քանի որ ռեկուրսիվ կանչից հետո չկան չմարված գործողություններ, կոմպիլյատորը կամ թարգմանիչը կարող է պարզեցնել ռեկուրսիան՝ այն փոխարինելով պարզ ցատկով:
Օպտիմալացման այս մոտեցումը, որը հայտնի է որպես պոչի զանգի օպտիմալացում, նվազեցնում է յուրաքանչյուր ռեկուրսիվ զանգի պահանջը՝ ստեկի շրջանակը պահպանելու համար, ինչը հանգեցնում է արագության և հիշողության ավելի ցածր օգտագործման:
Example:
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-Ոչ պոչային ռեկուրսիա
Ի տարբերություն պոչի ռեկուրսիայի, ոչ պոչային ռեկուրսիան ներառում է լրացուցիչ գործողություններ, որոնք կատարվում են ֆունկցիայի ներսում ռեկուրսիվ զանգից հետո: Նախքան որևէ այլ գործողություն կատարելը, յուրաքանչյուր ռեկուրսիվ զանգ պետք է ավարտվի և վերադառնա:
Որպես հետևանք, մինչև բազային գործի հասնելը և ռեկուրսիան ավարտվի, պահպանվում է չմարված գործողությունների փաթեթը: Ոչ պոչային ռեկուրսիան հաճախ օգտագործում է ավելի շատ հիշողություն և ավելի քիչ արդյունավետ է, քան պոչային ռեկուրսիան, բայց այն դեռևս օգտակար գործիք է տարբեր խնդիրների լուծման համար:
Example:
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
Փաթեթավորեք
Ռեկուրսիան ինտրիգային հասկացություն է ծրագրավորման մեջ: Այն թույլ է տալիս մեզ լուծել բարդ խնդիրները ռեկուրսիվ, ինքնահղման եղանակով:
Այն առաջարկում է խնդիրների մասին մտածելու և լուծելու հստակ մեթոդ՝ դրանք բաժանելով ավելի փոքր, ավելի կառավարելի մասերի: Այնուամենայնիվ, ռեկուրսիայի հետ աշխատելիս կարևոր է ուշադրություն դարձնել որոշ կետերի վրա:
Դուք պետք է բացահայտեք համապատասխան բազային դեպքեր, որոնք թույլ են տալիս ավարտել ռեկուրսիան: Եթե դրանք չկան, գործառույթը կարող է շարունակել իրեն ընդմիշտ զանգահարել:
Երկրորդ, ելնելով առկա սցենարից, ռեկուրսիայի համապատասխան տեսակի ընտրությունը կարող է հանգեցնել ավելի արդյունավետ և էլեգանտ լուծումների: Փորձեք գտնել, թե որն է լավագույնը ձեռքի խնդրի համար: Հսկայական ռեկուրսիայի խորությունների հետ աշխատելիս պետք է տեղյակ լինել պոտենցիալ վտանգների մասին, ինչպիսիք են կույտերի արտահոսքը:
Թողնել գրառում