Гол ялгаа – Рекурс ба давталт
Recursion болон Iteration-ийг програмчлалын асуудлыг шийдвэрлэхэд ашиглаж болно. Рекурс эсвэл давталт ашиглан асуудлыг шийдвэрлэх арга нь тухайн асуудлыг шийдвэрлэх аргаас хамаарна. Рекурс ба давталт хоёрын гол ялгаа нь рекурс нь нэг функц доторх функцийг дуудах механизм бөгөөд давталт нь өгөгдсөн нөхцөл үнэн болтол олон тооны зааврыг дахин дахин гүйцэтгэх явдал юм. Рекурс болон давталт нь алгоритм боловсруулах, програм хангамж бүтээх гол арга техник юм.
Recursion гэж юу вэ?
Функц дотроо өөрийгөө дуудах үед үүнийг Рекурс гэж нэрлэдэг. Хоёр төрлийн рекурс байдаг. Эдгээр нь хязгааргүй рекурс ба хязгааргүй рекурс юм. Хязгаарлагдмал рекурс нь төгсгөлийн нөхцөлтэй байдаг. Хязгааргүй рекурсид дуусгавар болох нөхцөл байхгүй.
Рекурсийг факториал тооцоолох програмыг ашиглан тайлбарлаж болно.
n!=n(n-1)!, хэрэв n>0
n!=1, хэрэв n=0 бол;
3(3!=321)-ийн факториалыг тооцоолохын тулд доорх кодыг үзнэ үү.
intmain () {
int утга=фактор (3);
printf(“Факториал %d\n”, утга);
0 буцах;
}
хүчин зүйлийн (интерн) {
хэрэв(n==0) {
буцах 1;
}
өөр {
буцах n факториал(n-1);
}
}
Факторийн (3)-ыг дуудах үед тухайн функц факториал (2)-г дуудна. Факториал (2) гэж дуудах үед тухайн функц факториал (1) гэж дуудна. Дараа нь факториал (1) хүчин зүйл (0) гэж дуудна. факториал (0) нь 1-ийг буцаана. Дээрх программын “if блок” дахь n==0 нөхцөл нь үндсэн нөхцөл юм. Үүнтэй адилаар хүчин зүйлийн функцийг дахин дахин дууддаг.
Рекурсив функцууд нь стектэй холбоотой. Си хэл дээр үндсэн програм нь олон функцтэй байж болно. Тэгэхээр үндсэн () нь дууддаг функц бөгөөд үндсэн програмаар дуудагдсан функц нь дуудагдсан функц юм. Функцийг дуудах үед удирдлага дуудагдсан функцэд өгөгдөнө. Функцийн гүйцэтгэл дууссаны дараа удирдлага үндсэн горим руу буцна. Дараа нь үндсэн хөтөлбөр үргэлжилнэ. Тиймээс, энэ нь гүйцэтгэлийг үргэлжлүүлэхийн тулд идэвхжүүлэх бичлэг эсвэл стек фрейм үүсгэдэг.
Зураг 01: Рекурс
Дээрх программ дээр үндсэнээс факториал (3) руу залгахад дуудлагын стек дотор идэвхжүүлэлтийн бичлэг үүсгэдэг. Дараа нь стекийн дээд талд факториал (2) стекийн хүрээ үүсдэг гэх мэт. Идэвхжүүлэлтийн бүртгэл нь локал хувьсагчийн талаарх мэдээллийг хадгалдаг. Функцийг дуудах бүрт стекийн дээд талд локал хувьсагчийн шинэ багц үүсдэг. Эдгээр стек хүрээ нь хурдыг удаашруулж чаддаг. Рекурсын нэгэн адил функц өөрийгөө дууддаг. Рекурсив функцийн цагийн нарийн төвөгтэй байдлыг хэдэн удаа олдог, функцийг дууддаг. Нэг функцийн дуудлагын цагийн нарийн төвөгтэй байдал нь O(1) юм. n тооны рекурсив дуудлагын хувьд цагийн нарийн төвөгтэй байдал нь O(n).
Давталт гэж юу вэ?
Давталт нь өгөгдсөн нөхцөл үнэн болтол дахин дахин давтагдах зааврын блок юм. Давталтыг "for loop", "do-while loop" эсвэл "while loop" ашиглан хийж болно. “for loop” синтакс дараах байдалтай байна.
(эхлүүлэх; нөхцөл; өөрчлөх) {
// мэдэгдэл;
}
Зураг 02: “for давталтын урсгалын диаграмм”
Эхлэх алхмыг эхлээд гүйцэтгэнэ. Энэ алхам нь давталтын хяналтын хувьсагчдыг зарлах, эхлүүлэх явдал юм. Хэрэв нөхцөл үнэн бол буржгар хаалт доторх хэллэгүүд биелнэ. Эдгээр мэдэгдлүүд нь нөхцөл үнэн болтол гүйцэтгэгдэнэ. Хэрэв нөхцөл худал бол удирдлага нь "for давталт"-ын дараа дараагийн мэдэгдэл рүү шилжинэ. Давталтын доторх мэдэгдлүүдийг гүйцэтгэсний дараа удирдлага нь өөрчлөх хэсэг рүү шилждэг. Энэ нь давталтын хяналтын хувьсагчийг шинэчлэх явдал юм. Дараа нь нөхцөл байдлыг дахин шалгана. Хэрэв нөхцөл үнэн бол буржгар хаалт доторх хэллэгүүд ажиллана. Ингэснээр "for давталт" давтагдана.
“while loop”-д нөхцөл үнэн болтол давталт доторх хэллэгүүд ажиллана.
байхад (нөхцөл){
//мэдэгдэл
}
“do-while” гогцоонд давталтын төгсгөлд нөхцөлийг шалгана. Тиймээс давталт дор хаяж нэг удаа ажиллана.
хийх{
//мэдэгдэл
} байхад(нөхцөл)
Давталт ("for давталт") ашиглан 3 (3!)-ын факториалыг олох программ дараах байдалтай байна.
int main(){
intn=3, факториал=1;
inti;
for(i=1; i<=n; i++){
фактор=хүчин зүйлi;
}
printf(“Факториал %d\n”, хүчин зүйл);
0 буцах;
}
Рекурс болон давталтын хооронд ямар төстэй зүйл байдаг вэ?
- Хоёулаа асуудлыг шийдэх арга техник.
- Даалгаврыг рекурс эсвэл давталтаар шийдэж болно.
Рекурс болон давталт хоёрын ялгаа юу вэ?
Recursion ба Давталт |
|
| Recursion нь ижил функц доторх функцийг дуудах арга юм. | Давталт нь өгөгдсөн нөхцөл үнэн болтол давтагдах зааврын блок юм. |
| Сансар огторгуйн нарийн төвөгтэй байдал | |
| Рекурсив програмын орон зайн нарийн төвөгтэй байдал нь давталтаас өндөр байна. | Сансар огторгуйн нарийн төвөгтэй байдал нь давталтын хувьд бага байна. |
| Хурд | |
| Recursion гүйцэтгэл удаан байна. | Ер нь давталт нь рекурсаас хурдан байдаг. |
| Нөхцөл | |
| Хэрэв дуусгавар болгох нөхцөл байхгүй бол хязгааргүй рекурс байж болно. | Хэрэв нөхцөл хэзээ ч худал болохгүй бол энэ нь хязгааргүй давталт болно. |
| Стек | |
| Recursion-д функцийг дуудах үед стекийг локал хувьсагчдыг хадгалахад ашигладаг. | Давталтанд стек ашиглагдахгүй. |
| Код унших чадвар | |
| Рекурсив програм илүү уншигдах боломжтой. | Дахин давтагдах программ нь рекурсив программаас уншихад хэцүү. |
Хураангуй – Рекурс ба давталт
Энэ нийтлэлд рекурс болон давталт хоёрын ялгааг авч үзсэн. Програмчлалын асуудлыг шийдвэрлэхэд хоёуланг нь ашиглаж болно. Рекурс ба давталт хоёрын ялгаа нь рекурс нь нэг функц доторх функцийг дуудаж, өгөгдсөн нөхцөл үнэн болтол командын багцыг дахин дахин гүйцэтгэх механизм юм. Хэрэв асуудлыг рекурсив хэлбэрээр шийдвэрлэх боломжтой бол давталт ашиглан шийдэж болно.
Recursion ба Давталтын PDF хувилбарыг татаж авах
Та энэ нийтлэлийн PDF хувилбарыг татаж аваад офлайн зорилгоор ашиглах боломжтой. PDF хувилбарыг эндээс татаж авна уу Рекурс ба давталтын ялгаа
