Сиз качандыр бир көйгөй майда фрагменттерге бөлүнүүчү, бүтпөгөн циклге туш болдуңуз беле?
Эгер ошондой болсо, сиз рекурсиянын кызыктуу дүйнөсүнө туш болушуңуз мүмкүн. Түшүнүү кыйын болуп көрүнгөнү менен, кабатыр болбоңуз! Бул постто биз рекурсиялардын түрлөрү менен таанышуу үчүн кызыктуу саякатка чыгабыз.
Ошентип, биз көптөгөн рекурсивдүү ыкмаларды изилдеп жатканыбызда бекем болуңуз. Рекурсиянын кызыктуу чөйрөсүнө кирүүгө даярданыңыз жана анын татаал маселелерди чечүүдө укмуштуудай жөндөмүн байкаңыз.
Рекурсиялар деген эмне?
Негизги сөз менен айтканда, рекурсия - бул аткаруу учурунда өзүн чакырган функцияны камтыган күчтүү программалоо ыкмасы. Бул күзгүгө тиктеп, сүрөттөлүштүн ичиндеги сүрөттү көрүү сыяктуу, натыйжада өзүнө шилтеме жасоо цикли пайда болот.
Биз рекурсиянын жардамы менен чоң маселелерди чече алабыз, аларды кичине, башкарылуучу чакан көйгөйлөргө бөлүү аркылуу.
Бул бир бөлүктүн башка бөлүктөр менен байланышып, толук сүрөттү чыгаруу үчүн жигсаны чогултууга окшош. Рекурсия ар кандай киргизүүлөр менен бир эле нускамаларды кайталоо аркылуу маселелерди саркеч жана эффективдүү чечүүгө мүмкүндүк берет.
1-Түз рекурсия
Түз рекурсия рекурсиянын эң негизги түрү болуп саналат, мында функция өзүн түз чакырат. Бул көйгөйлүү көйгөйдү негизги абалга жеткенге чейин кичине кичи проблемаларга бөлүүнү талап кылат, бул токтотууга алып келет.
Рекурсивдүү функция өзүн ар кандай киргизүүлөр менен чакырып, ошол эле нускамалардын кайталанышына мүмкүндүк берет. Ар бир чакырык мурункуга негизделет, акырындык менен рекурсия аяктайт.
Келгиле, бул мисалды карап көрөлү.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Output:
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)
Output:
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)
Output:
120
4-Дарак рекурсиясы
Функция бир нече рекурсивдүү чакырууларга бутактанганда, биз дарак рекурсиясынын дүйнөсүнө киребиз. Дарактын рекурсиясындагы функция көптөгөн рекурсивдүү чакырыктарды жаратат, алардын ар бири дарактын бутактары сыяктуу өзүнчө чакан маселени чечет.
Бул тармакташкан структура татаал маселелерди майда, өз ара байланышкан компоненттерге натыйжалуу бөлүп, бир нече маршруттарды бир эле учурда иликтөөгө мүмкүндүк берет.
мисал:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Output:
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)
Output:
15
Киришүү
Рекурсия - программалоодогу кызыктуу түшүнүк. Ал бизге татаал маселелерди рекурсивдүү, өз алдынча референциялуу түрдө чечүүгө мүмкүндүк берет.
Ал көйгөйлөр жөнүндө ойлонуунун жана чечүүнүн өзгөчө ыкмасын сунуштайт, аларды майда, башкара турган бөлүктөргө бөлөт. Бирок рекурсия менен иштөөдө кээ бир пункттарга көңүл бурууну колдонуу маанилүү.
Сиз рекурсиянын бүтүшүнө мүмкүндүк берүүчү ылайыктуу базалык учурларды аныкташыңыз керек. Эгерде алар жок болсо, функция өзүн түбөлүккө чакыра бериши мүмкүн.
Экинчиден, учурдагы сценарийдин негизинде рекурсиянын ылайыктуу түрүн тандоо натыйжалуураак жана көрктүү чечимдерге алып келиши мүмкүн. Колдогу көйгөйгө эмне ылайыктуу экенин табууга аракет кылыңыз. Кеңири рекурсия тереңдиктери менен иштөөдө стектин толуп кетиши сыяктуу потенциалдуу коркунучтардан кабардар болуңуз.
Таштап Жооп