Рекурс

Альваа юмны тодорхойлолтыг хэлж, цээжлэх шиг амархан юм байхгүй байх. Тэр тусмаа Рекурсив функц. Тодорхойлолт нь их энгийн "Өөрөө өөрийгөө дууддаг функцыг Рекурсив функц гэнээ" гэж. Рекурс бол маш хүчтэй техник, for давталтаар хийж болдог бүх алгоритмыг Рекурсээр хийж болно, харин Рекурсив функцын хийж байгаа зарим хүнд алгоритмыг for давталтаар хийх боломжгүй (Яг ч тийм бишилдээ, гэхдээ ядаж л маш хэцүү).

Бид 10 жилдээ математик дээр ч Рекуррэнт дараалал, функц хангалттай үзэж бодсон болохоор би илүү дутуу доторхойлолт хэлэлгүйгээр рекурсив програм бичихэд хэрэг болох ойлголт, анхааруулгуудыг бичие.

Дараах асуултыг өөртөө тавиад бодож үзээрэй.

- Рекурсив функц нь өөрөө өөрийгөө дуудна гэж юу гэсэн үг вэ?

Бид ямар нэгэн N-р түвшний бодлогыг бодохын тулд тухайн функцээр өөрөөр нь N-1 түвшний бодлогыг бодуулж байгаа учраас өөрийг нь дуудаж байгаа юм. Энэ үйлдэлийг РЕКУРСИВ ДУУДАЛТ гэж нэрлэе.

- Тэгвэл хэзээ өөрийгөө дуудахаа болих вэ?

Бид тухайн бодлогын хамгийн доод түвшин мөн хамгийн суурь баталгаатай хариуг мэдэж байгаа үедээ тухайн хариуг суурь хариу болгож буцаагаад дээшээ илгээснээр Рекурсив дуудалт зогсож тухайн түвшин болгондоо хариугаа олох боломжийг олгодог.

Тэгэхээр бидэнд буцах утга буюу Рекурсив дуудалтыг зогсоох үйлдэл хэрэгтэй.

- Тэгвэл Рекурсив дуудалт зогссны дараа юу хийх вэ?

Эндээс эхлэн Рекурсив буцах үйлдэл хийгдэнэ. Факториал олох Рекурсив функц N-н факториалыг олохын тулд N-1-н факториалыг олохыг шаардаж fac(N-1)-г дууддаг. Бид fac(N-1)-г олцон гэж үзье. Тэгвэл бид N-н факториалыг олж чадна гэсэн үг. Бид N-н факториалыг олж чадна гэдэг чинь N+1-г ч олж чадна гэсэн үг. Энэ үйлдэлийг л РЕКУРСИВ БУЦАЛТ гэж байгаа юм.

Тэгвэл Рекурив Функц-д дараахь 3-н зүйл зайлшгүй хэрэгтэй.

1. Рекурсив Дуудалт

2. Рекурсив Дуудалт Зогсоох

3. Рекурсив Буцалт

Тэгэхээр бид Ганц Рекурсив Функцээр хоёр зүйл хийж чадаж байгаа биз!. Рекурсив Дуудалт хийх үед нь ямар нэг үйлдэл хийж болно, мөн Рекурсив Буцаад явж байхад нь дахин өөр үйлдэл хийж чадахнээ. Рекурсив ийм л боломж олгож байгаа учраас Дуудалт, Буцалт хоёрыг нь ашиглаад уран гоё бодолт, алгоритмууд хийгдэж байгаа юм.

Одоо энгийн for цикл-тэй харьцуулж Рекурсив функц хэрхэн бичихийг үзүүлэх гэж оролдоё. Эндээс Рекурсив дуудалт болон буцалтыг ойлгохыг хичээгээрэй.

Энгийн цикл:

for(int i=0; i<n; i++){
   Энд юу дуртайгаа хий
}

Энгийн циклийг Рекурсив функцээр бичвэл:

void FOR(int i, int n) {
    if(i==n) return; // Рекурсив Зогсов
    // Энд юу дуртайгаа хий
    FOR(i+1, n); // Рекурсив Дуудалт
}

Урвуу цикл (өөр олигтой нэр санаанд ордоггүй, Буцах for цикл гэсэн ч болно.)

for(int i = n-1; i >= 0; i -= 1) {
    // Энд юу дуртайгаа хий
}

Урвуу циклийн Рекурсив функц

void ROF(int i, int n) {
    if(i==n) return; // Рекурсив зогсов
    ROF(i+1, n); // Рекурсив Дуудалт
    // Энд юу дуртайгаа хий
}

За хө тэгэхээр дээрх 2 Рекурсив Функцын ялгааг харж байна уу? Урвуу циклийг яаж хийж байгаа гэхээр Рекурсивийг буцах үед нь хийж байгаа байх нь. Бүр дэлгэрэнгүй болгох үүднээс N-с 1 хүртэл хэвлэдэх Рекурсив функцыг дэлгэрэнгүй тайлбарлая.

void rec(int i, int n){
    if(n+1==i)return;//Рекурсив Зогсов
    rec(i+1, n);//Рекурсив дуудалт
    printf("%d ", i);//Рекурсив Буцах үед хэвлээд байхнээ.
}

Дээрх функц дараах алхамаар ажиллаж байна.

01|ДУУДАЛТ rec1 i=1
02|    ДУУДАЛТ rec2 i=2
03|        ДУУДАЛТ rec3 i=3
04|            ДУУДАЛТ rec4 i=4
05|                ДУУДАЛТ rec5 i=5
06|                    ДУУДАЛТ function6 with i=6
07|                        i Рекурсив зогсоох нөхцөлийг хангасан тул Буцаад явна
08|                    БУЦАЛТ rec5
09|                    print 5
10|                БУЦАЛТ rec4
11|                print 4
12|            БУЦАЛТ rec3
13|            print 3
14|        БУЦАЛТ rec2
15|        print 2
16|    БУЦАЛТ rec1
17|    print 1
18|дуусав!

За ер нь ойлгомжтой байх гэж бодож байна.
Бид C++ дээр факториал олох функцыг дараах байдлаар бичдэг.

int fac(int n){
   if(n==0)return 1;
   return fac(n-1)*n;
}

Бүр дэлгэрэнгүй бичвэл дараах байдлаар бичнэ гэсэн үг.

int fac(int n){
   int ret = 1;//Тухайн n-н факториалыг хадгална
   if(n==0)return ret;//Буцах нөхцөл
   ret = fac(n-1)*n;//Рекурсив дуудалт
   return ret;//Рекурсив буцах үйлдэл маань ердөөл n-н факториалыг л буцаах үйлдэл байна6
}

Одоо ийм зүйлийг ойлгосон байх. Рекурсив дуудалтын өмнө хийгдэж байгаа үйлдэл мэдээж Рекурсив дуудалтын өмнө хийгдэнэ, хари Рекурсив дуудалтын доор хийгдэж байгаа үйлдэлийг Рекурсив буцаад явах замдаа хийдэг байхнээ.
Одоо арай жаахан ахисан түвшинд Рекурсын ойлголтуудаас бичвэл, Рекурс нь санах ойд дуудагдах болгондоо мод үүсгэж байдаг. Жишээ нь бидний дээр бичсэн Факториал олох функц бол шууд шулуун мод үүсгэж байгаа. Харин фибаночи дараалал олох Рекурсив функц санах ойд хэрхэн ажиллахыг харъя.

int fib(int n){
    if(n<1)return 1;
    return fib(n-1)+fib(n-2);
}

Дээрх кодыг бүр энгийнээр бичвэл:

int fib(int n){
    int ret = 1;
    if(n<1)return ret;//Буцах нөхцөл
    ret = fib(n-1);//Рекурсив дуудалт
    ret += fib(n-2);//Рекурсив дуудалт, энэ нь санах ойд үүсгэгдэж байгаа модонд нэмж салаа үүсгэж байна.
    return ret;//Буцалт
}

N=5 үйд дээрх функцын санах ойд үүсгэсэн мод дараах байдалтай:

Тэгэхээр Факториал олох функц санах ойд шууд шулуун мод л үүсгэж байгаа байх нь. Ингэж санах ойд шинэ салаа үүсгэж байна гэдэг нь бид Рекурсив Буцах үйлдэлийг ганц биш янзаар тодорхойлж чадах нээ. Энэ бол Рекурсын хамгийн том давуу тал. Дараагийн постоор Рекурсиваар бодох дасгал, мөн бодолтуудыг тавина.