Асуудал жижиг хэсгүүдэд хуваагдаж байдаг эцэс төгсгөлгүй мэт санагдах мөчлөгт та хэзээ нэгэн цагт баригдаж байсан уу?
Хэрэв тийм бол та рекурсын сэтгэл татам ертөнцтэй танилцсан байж магадгүй юм. Хэдийгээр ойлгоход хэцүү мэт санагдаж болох ч санаа зовох хэрэггүй! Энэ нийтлэлд бид рекурсын төрлүүдийг судлах сонирхолтой аялал хийх болно.
Тиймээс бид олон тооны рекурсив хандлагуудыг судлахдаа тэврэлтээ аваарай. Сонирхолтой рекурсын талбарт ороход бэлтгэж, төвөгтэй асуудлыг шийдвэрлэх түүний гайхалтай чадварыг ажиглаарай.
Рекурсууд яг юу вэ?
Үндсэн үгээр хэлбэл, рекурс нь гүйцэтгэх явцад өөрийгөө дууддаг функцийг агуулсан хүчирхэг програмчлалын техник юм. Энэ нь толинд ширтэх, дүрс доторх дүрсийг харахтай адил бөгөөд үүний үр дүнд өөрийгөө лавлах мөчлөг үүсдэг.
Бид рекурсын тусламжтайгаар том асуудлуудыг жижиг, илүү удирдах боломжтой дэд асуудлуудад хуваах замаар шийдвэрлэх боломжтой.
Энэ нь эвлүүлдэг хөрөөтэй төстэй бөгөөд нэг хэсэг нь бусад хэсгүүдтэй холбогдож бүрэн дүр зургийг гаргадаг. Рекурс нь янз бүрийн оролттой ижил багц зааврыг давтах замаар асуудлыг гоёмсог, үр дүнтэй шийдвэрлэх боломжийг олгодог.
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-Сүүлийн рекурс
Tail recursion нь рекурсив алгоритмуудыг оновчтой болгох арга бөгөөд тэдгээрийн гүйцэтгэлийг сайжруулдаг. Рекурсив дуудлага нь сүүлний рекурс хийх, хийх функцийн эцсийн үйлдэл болж харагдана.
Рекурсив дуудлагын дараах онцгой үйлдлүүд байхгүй тул хөрвүүлэгч эсвэл тайлбарлагч нь энгийн үсрэлтээр солих замаар рекурсийг хялбарчилж чадна.
Сүүлт дуудлагын оновчлол гэгддэг энэхүү оновчлолын арга нь рекурсив дуудлага бүрт стек фрейм хадгалах шаардлагыг бууруулж, хурдыг сайжруулж, санах ойн хэрэглээг бууруулдаг.
Жишээ нь:
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
Дуусгах
Рекурс нь програмчлалын сонирхолтой ойлголт юм. Энэ нь бидэнд ээдрээтэй асуудлуудыг рекурсив, өөртөө лавлагаатай байдлаар шийдвэрлэх боломжийг олгодог.
Энэ нь асуудлыг эргэцүүлэн бодох, шийдвэрлэх тодорхой аргыг санал болгож, тэдгээрийг илүү жижиг, удирдах боломжтой хэсгүүдэд хуваадаг. Гэхдээ рекурстай ажиллахдаа зарим зүйлд анхаарлаа хандуулах нь чухал юм.
Та рекурсийг дуусгах боломжтой тохирох үндсэн тохиолдлуудыг тодорхойлох хэрэгтэй. Хэрэв тэдгээр нь байхгүй бол функц нь өөрийгөө үүрд дуудаж болно.
Хоёрдугаарт, одоо байгаа хувилбар дээр үндэслэн тохирох төрлийн рекурсийг сонгох нь илүү үр дүнтэй, гоёмсог шийдлүүдэд хүргэдэг. Гарт байгаа асуудалд юу хамгийн сайн тохирохыг олохыг хичээ. Өргөн уудам рекурсын гүнтэй ажиллахдаа стек халих зэрэг болзошгүй аюулаас болгоомжил.
хариу үлдээх