Оё шумо ягон бор дар як давраи ба назар беохир дучор шудаед, ки дар он мушкилот ба порчаҳои хурдтар тақсим мешавад?
Агар ин тавр бошад, шумо шояд ба ҷаҳони ҷолиби рекурсия омадаед. Гарчанде ки фаҳмидани он душвор ба назар мерасад, хавотир нашав! Дар ин паём, мо ба як саёҳати ҷолиб меравем, то дар бораи намудҳои рекурсияҳо маълумот гирем.
Пас, вақте ки мо равишҳои сершумори рекурсивиро меомӯзем, даст кашед. Барои ворид шудан ба олами ҷолиби рекурсия омода шавед ва қобилияти назарраси онро дар ҳалли масъалаҳои мураккаб мушоҳида кунед.
Рекурсияҳо маҳз кадомҳоянд?
Ба ибораи асосӣ, рекурсия як усули пурқудрати барномасозӣ мебошад, ки функсияеро дар бар мегирад, ки ҳангоми иҷро худро даъват мекунад. Ин ба оина нигоҳ кардан ва дидани тасвир дар дохили тасвир аст, ки дар натиҷа як давраи худшиносӣ ба вуҷуд меояд.
Мо метавонем масъалаҳои калонро бо истифода аз рекурсия тавассути тақсим кардани онҳо ба зерпроблемаҳои хурдтар ва идорашаванда ҳал кунем.
Ин ба якҷоя кардани ҷигса монанд аст, ки дар он як порча ба қисмҳои дигар пайваст мешавад, то тасвири пурраро ба даст орад. Рекурсия ба мо имкон медиҳад, ки масъалаҳоро ба таври шево ва муассир тавассути такрори як маҷмӯи дастурҳо бо воридоти гуногун ҳал кунем.
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
Ба натиҷа расидан
Рекурсия консепсияи ҷолиб дар барномасозӣ аст. Он ба мо имкон медиҳад, ки мушкилоти мураккабро ба таври рекурсивӣ ва худшиносӣ ҳал кунем.
Он усули мушаххаси фикр кардан ва ҳалли мушкилотро пешниҳод мекунад ва онҳоро ба қисмҳои хурдтар ва идорашаванда тақсим мекунад. Бо вуҷуди ин, ҳангоми кор бо рекурсия муҳим аст, ки ба баъзе нуктаҳо диққат диҳед.
Шумо бояд ҳолатҳои асосиро муайян кунед, ки имкон медиҳанд рекурсия ба охир расад. Агар онҳо мавҷуд набошанд, функсия метавонад то абад худро даъват кунад.
Дуюм, дар асоси сенарияи мавҷуда, интихоби навъи мувофиқи рекурсия метавонад ба ҳалли муассиртар ва шево оварда расонад. Кӯшиш кунед, ки он чизеро, ки барои мушкилот дар даст беҳтар аст, пайдо кунед. Ҳангоми кор бо умқи азими рекурсия, аз хатарҳои эҳтимолӣ, аз қабили пур шудани стек огоҳ бошед.
Дин ва мазҳаб