Rekursiya

Tasavvur qiling, katta papkaning ichida fayllar va yana boshqa papkalar bor. Ichki papkalarning ichida ham fayl hamda papkalar bo‘lishi mumkin. Barcha fayllarni sanash uchun har bir papka darajasi uchun alohida algoritm yozish noqulay: tashqi papkani tekshirish, uning ichki papkasini tekshirish va undan ham ichkaridagi papkani tekshirish aslida bir xil ish.

Bu muammoni quyidagicha ifodalash tabiiy:

1. joriy papkadagi fayllarni sanash;
2. har bir ichki papka uchun ayni shu jarayonni takrorlash;
3. ichki papka qolmaganda natijani qaytarish.

Algoritmning kichikroq ko‘rinishi yana o‘sha algoritm bilan yechilyapti. Rekursiya (recursion) — funksiya muammoning kichikroq yoki soddaroq nusxasini yechish uchun o‘zini bevosita yoki bilvosita chaqiradigan yondashuvdir.

FUNCTION COUNT_FILES(folder)
    total = folder ichidagi oddiy fayllar soni

    FOR har bir subfolder folder ichida
        total = total + COUNT_FILES(subfolder)

    RETURN total

Rekursiya “funksiya o‘zini chaqiradi” degan ta’rifdan kattaroq tushuncha. To‘g‘ri rekursiv yechimda:

• muammo bir xil shakldagi kichikroq qismlarga ajraladi;
• eng sodda holat qo‘shimcha chaqiruvsiz yechiladi;
• har bir chaqiruv shu sodda holatga yaqinlashadi;
• kichik qismlarning javoblari birlashib, dastlabki javobni hosil qiladi.

Shu shartlardan biri buzilsa, funksiya cheksiz chaqirilishi, noto‘g‘ri natija qaytarishi yoki xotiradagi chaqiruvlar steki to‘lib qolishi mumkin.

Ichma-ich qutilar analogiyasi

Bir-birining ichiga joylashtirilgan qutilarni ochayotganingizni tasavvur qiling. Har qutida yoki kichikroq quti, yoki izlanayotgan buyum bor. Jarayon quyidagicha:

katta qutini och
    o‘rta qutini och
        kichik qutini och
            buyumni top
        kichik qutini yop
    o‘rta qutini yop
katta qutini yop

Ichkariga kirishda har bir qutini qayerdan ochganingizni eslab qolish kerak. Eng ichki qutiga yetgach, tashqariga teskari tartibda qaytasiz. Rekursiv funksiya ham xuddi shunday ishlaydi: yangi chaqiruv boshlanganda oldingi chaqiruv vaqtincha kutadi; eng sodda holat natija qaytargach, kutib turgan chaqiruvlar oxirgisidan boshlab davom etadi.

Bu analogiyada buyum topilgan eng ichki quti base case, ya’ni tayanch holatdir. Qutilarni ichkariga qarab ochish rekursiv tushish, ularni teskari tartibda yopish esa natijalarni qaytarish bosqichidir.

Asosiy terminlar

Rekursiv funksiya

O‘z bajarilishi davomida o‘zining yangi chaqiruvini boshlaydigan funksiya rekursiv funksiya deyiladi. Yangi chaqiruv avvalgisining aynan o‘zi emas: uning parametr qiymatlari va lokal o‘zgaruvchilari alohida bo‘ladi.

Tayanch holat

Tayanch holat (base case) — javobi qo‘shimcha rekursiv chaqiruvsiz ma’lum bo‘lgan eng sodda holat. U rekursiyaning to‘xtash nuqtasidir.

Masalan, n dan 1 gacha bo‘lgan sonlar yig‘indisini hisoblashda n = 0 bo‘lsa, natija 0:

SUM(0) = 0

Rekursiv holat

Rekursiv holat (recursive case) — javob kichikroq muammoning javobi orqali ifodalanadigan holat:

SUM(n) = n + SUM(n - 1)

Bu yerda muammo n dan n - 1 ga kichrayadi. Faqat funksiya o‘zini chaqirishi yetarli emas; argument tayanch holatga tomon o‘zgarishi kerak.

Rekursiya chuqurligi

Bir vaqtda yakunlanmay turib qolgan rekursiv chaqiruvlar soni rekursiya chuqurligi (recursion depth) deyiladi. SUM(4) chaqiruvi SUM(3), SUM(2), SUM(1) va SUM(0)gacha tushsa, bir paytda bir nechta chaqiruv xotirada turadi.

Call stack va stack frame

Call stack — bajarilayotgan funksiyalar qayerga qaytishi va ularning vaqtinchalik holatini saqlaydigan xotira tuzilmasi. Har bir funksiya chaqiruvi uchun unda stack frame, ya’ni chaqiruv freymi yaratiladi. Freym odatda quyidagilarning bir qismini saqlaydi:

• parametr qiymatlari;
• lokal o‘zgaruvchilar;
• funksiya tugagach bajarilish qayerdan davom etishi;
• hisoblash uchun zarur boshqa xizmat ma’lumotlari.

Aniq tarkib dasturlash tili, kompilyator va ishlash muhitiga bog‘liq. Fundamental g‘oya shuki, har chaqiruvning holati boshqalaridan alohida saqlanadi.

Oddiy misol: yig‘indini rekursiv hisoblash

1 dan n gacha bo‘lgan sonlar yig‘indisini ko‘ramiz. Iterativ yechim takrorlash orqali yig‘ishi mumkin. Rekursiv fikrlashda esa:

1 + 2 + ... + n = n + (1 + 2 + ... + n - 1)

Qavs ichidagi qism ayni muammoning kichikroq nusxasi:

FUNCTION SUM(n)
    IF n = 0
        RETURN 0

    RETURN n + SUM(n - 1)

Bu algoritm n manfiy bo‘lmagan butun son deb qabul qiladi. Kirish talabi tekshirilmasa, manfiy n qiymati 0ga yaqinlashmay, undan uzoqlashishi mumkin.

Chaqiruvlar pastga tushishi

SUM(4) bajarilganda javob darhol tayyor bo‘lmaydi:

SUM(4)
= 4 + SUM(3)
= 4 + (3 + SUM(2))
= 4 + (3 + (2 + SUM(1)))
= 4 + (3 + (2 + (1 + SUM(0))))

SUM(0) tayanch holatga yetadi va 0 qaytaradi. Shu paytgacha oldingi chaqiruvlarning har biri natijani kutib turadi.

Natijalar yuqoriga qaytishi

Endi hisoblash teskari tartibda yakunlanadi:

SUM(0) = 0
SUM(1) = 1 + 0  = 1
SUM(2) = 2 + 1  = 3
SUM(3) = 3 + 3  = 6
SUM(4) = 4 + 6  = 10

Rekursiyaning ikki bosqichini ajratish muhim:

1. tushish — muammo kichrayib, yangi chaqiruvlar yaratiladi;
2. qaytish — tayanch holatdan olingan javoblar kutib turgan chaqiruvlarda ishlatiladi.

Boshlovchilar ko‘pincha faqat pastga tushishni ko‘radi va RETURNdan keyingi qiymatlar qanday yig‘ilishini tasavvur qilishda qiynaladi. Dry runni ikki bosqichda yozish bu chalkashlikni kamaytiradi.

Call stack ichida nima sodir bo‘ladi?

SUM(3) misolida har chaqiruv uchun soddalashtirilgan freym yaratiladi:

1. SUM(3) chaqirildi

Call stack:
+---------------------------+
| SUM(3): n=3, SUM(2) kutadi|
+---------------------------+

SUM(3) yakunlanishidan oldin SUM(2)ni chaqiradi:

2. SUM(2) chaqirildi

Call stack:
+---------------------------+
| SUM(2): n=2, SUM(1) kutadi| ← eng yuqori freym
+---------------------------+
| SUM(3): n=3, SUM(2) kutadi|
+---------------------------+

Keyin SUM(1) va SUM(0) qo‘shiladi:

+---------------------------+
| SUM(0): n=0               | ← birinchi yakunlanadi
+---------------------------+
| SUM(1): n=1, SUM(0) kutadi|
+---------------------------+
| SUM(2): n=2, SUM(1) kutadi|
+---------------------------+
| SUM(3): n=3, SUM(2) kutadi|
+---------------------------+

Stack LIFO — “oxirgi kirgan, birinchi chiqadi” tartibida ishlaydi. Shu sababli avval SUM(0), keyin SUM(1), SUM(2) va oxirida SUM(3) tugaydi.

Har bir chaqiruvdagi n alohida. Ichki chaqiruv nni o‘zgartirishi tashqi chaqiruvning freymidagi nni almashtirmaydi. Funksiya qanday parametr uzatishi va obyektlar reference orqali boshqarilishi tilga bog‘liq nozik tafsilotlarga ega, lekin alohida chaqiruv freymlari g‘oyasi saqlanadi.

Rekursiya nima sababdan kerak?

Har qanday rekursiv algoritmni “rekursiya chiroyli” degani uchun ishlatish kerak emas. Rekursiya muammoning o‘zi rekursiv tuzilishga ega bo‘lganda tabiiy ifoda beradi.

Masalan, daraxtning har bir node’i qiymat va yana kichik daraxtlarga olib boruvchi child reference’larini saqlaydi. “Daraxtni ko‘rib chiqish” quyidagicha ta’riflanadi:

joriy node’ni ko‘r
har bir child uchun uning kichik daraxtini ko‘r

Papka ichidagi papkalar, tashkilot bo‘limlari, HTML elementlari, arifmetik ifoda qismlari va divide-and-conquer algoritmlarida ham butun tuzilma o‘ziga o‘xshash kichik qismlardan iborat. Rekursiv funksiya shu tuzilmani kodda bevosita aks ettiradi.

Rekursiyaning kuchi — har bir darajada faqat joriy kichik muammo haqida fikrlash imkonidir. Funksiya kichikroq muammoni to‘g‘ri yechadi deb qabul qilib, joriy natijani undan qanday qurishni aniqlaymiz. Call stack qayerdan qaytish kerakligini o‘zi saqlaydi.

To‘g‘ri rekursiv yechimning uchta sharti

1. Tayanch holat mavjud bo‘lishi kerak

Tayanch holatsiz har bir chaqiruv yana yangisini yaratadi:

FUNCTION BROKEN(n)
    RETURN BROKEN(n - 1)

Bu funksiya qachon to‘xtashini bilmaydi.

2. Har bir qadam tayanch holatga yaqinlashishi kerak

Shartning mavjudligi yetarli emas:

FUNCTION ALSO_BROKEN(n)
    IF n = 0
        RETURN 0

    RETURN ALSO_BROKEN(n + 1)

Musbat n uchun qiymat 0dan tobora uzoqlashadi. Tayanch holat bor, lekin unga yetib bo‘lmaydi.

3. Kichik javobdan joriy javob to‘g‘ri qurilishi kerak

SUM(n) uchun kichik javob SUM(n - 1). Joriy n ham qo‘shilmasa, funksiya to‘xtashi mumkin, ammo natija noto‘g‘ri bo‘ladi:

FUNCTION WRONG_SUM(n)
    IF n = 0
        RETURN 0

    RETURN SUM(n - 1)    // n hisobga olinmadi

To‘xtash va to‘g‘rilik alohida talablar: algoritm tugashi uning to‘g‘ri javob berishini kafolatlamaydi.

Rekursiv algoritmni qanday loyihalash kerak?

Rekursiv yechim tuzishda quyidagi savollar yordam beradi:

1. Eng sodda, javobi darhol ma’lum kirish qaysi?
2. Katta muammoni ayni shakldagi qaysi kichik muammo orqali ifodalash mumkin?
3. Har bir chaqiruv muammo o‘lchamini haqiqatan kamaytiradimi?
4. Kichik muammoning javobidan joriy javob qanday olinadi?
5. Maksimal rekursiya chuqurligi qancha bo‘lishi mumkin?
6. Bir xil kichik muammolar takroran hisoblanadimi?

Masalan, linked listdagi node’lar sonini hisoblash:

• bo‘sh ro‘yxatning uzunligi 0;
• bo‘sh bo‘lmagan ro‘yxatning uzunligi 1 + qolgan ro‘yxat uzunligi;
• har chaqiruv nextga o‘tadi, demak oxirgi NULLga yaqinlashadi.

FUNCTION LENGTH(node)
    IF node = NULL
        RETURN 0

    RETURN 1 + LENGTH(node.next)

Bu ta’rif matematik va kod nuqtayi nazaridan sodda. Ammo juda uzun linked listda iterativ traversal call stackni ishlatmagani uchun amaliyroq bo‘lishi mumkin.

Rekursiya turlari

Turlarni yodlashdan ko‘ra, har chaqiruv qayerda va nechta yangi chaqiruv yaratishini tushunish muhim.

Bevosita rekursiya

Funksiya o‘zini to‘g‘ridan-to‘g‘ri chaqirsa, bu bevosita rekursiya (direct recursion):

FUNCTION COUNTDOWN(n)
    IF n = 0
        RETURN

    OUTPUT n
    COUNTDOWN(n - 1)

Fayl tizimi, linked list va daraxt traversalining sodda variantlari ko‘pincha shu ko‘rinishda yoziladi.

Bilvosita rekursiya

Bir funksiya ikkinchisini, ikkinchisi esa yana birinchisini chaqirsa, bilvosita rekursiya (indirect recursion) yuz beradi:

FUNCTION IS_EVEN(n)
    IF n = 0
        RETURN TRUE

    RETURN IS_ODD(n - 1)

FUNCTION IS_ODD(n)
    IF n = 0
        RETURN FALSE

    RETURN IS_EVEN(n - 1)

Bu ham call stackdan foydalanadi va umumiy chaqiruvlar zanjiri tayanch holatga yaqinlashishi kerak. Bilvosita rekursiyada cheksiz siklni ko‘rish qiyinroq, chunki o‘zini chaqirish bitta funksiya ichida ko‘rinmaydi.

Chiziqli rekursiya

Har bir chaqiruv ko‘pi bilan bitta keyingi rekursiv chaqiruv yaratsa, chiziqli rekursiya (linear recursion) deyiladi. SUM(n), countdown va linked list traversal shunday ishlaydi. Chaqiruvlar soni odatda kirish hajmiga mutanosib.

Daraxtsimon rekursiya

Har chaqiruv bir nechta rekursiv chaqiruv yaratsa, bajarilish rekursiya daraxti (recursion tree) hosil qiladi:

FUNCTION FIB(n)
    IF n <= 1
        RETURN n

    RETURN FIB(n - 1) + FIB(n - 2)

FIB(5) uchun chaqiruvlarning bir qismi:

                    FIB(5)
                  /        \
              FIB(4)      FIB(3)
             /     \      /     \
         FIB(3) FIB(2) FIB(2) FIB(1)
          /  \    / \    / \
         ...  ... ...    ...

Bu yerda FIB(3) va FIB(2) kabi bir xil kichik muammolar qayta-qayta hisoblanadi. Rekursiv yozuv qisqa bo‘lsa ham, sodda variantning vaqt murakkabligi eksponentsial darajada o‘sadi. Memoization bu takroriy hisoblarni kamaytirishi mumkin.

Tail recursion

Rekursiv chaqiruv funksiyaning eng oxirgi amali bo‘lsa va undan qaytgach boshqa hisob qolmasa, bu tail recursion, ya’ni oxirgi amal rekursiyasi deyiladi:

FUNCTION SUM_TAIL(n, accumulator)
    IF n = 0
        RETURN accumulator

    RETURN SUM_TAIL(n - 1, accumulator + n)

accumulator oraliq natijani olib yuradi. SUM(n)ning oldingi variantida esa ichki chaqiruv qaytgach n + ... amali bajarilishi kerak edi, shuning uchun u tail recursion emas.

Ayrim kompilyator yoki ishlash muhitlari tail call optimization orqali eski freymni qayta ishlatib, stack chuqurligini oshirmasligi mumkin. Lekin barcha dasturlash tillari va barcha holatlarda bu optimizatsiya bor deb bo‘lmaydi. Kafolat bo‘lmasa, tail recursion ham O(n) stack xotirasi va stack overflow xavfiga ega deb qaraladi.

Daraxt bo‘ylab rekursiv yurish

Rekursiya daraxtlar uchun ayniqsa tabiiy. Binary tree node’ida chap va o‘ng child bo‘lishi mumkin. Node’lar sonini hisoblash:

FUNCTION COUNT_NODES(node)
    IF node = NULL
        RETURN 0

    left_count = COUNT_NODES(node.left)
    right_count = COUNT_NODES(node.right)

    RETURN 1 + left_count + right_count

Masalan:

          A
         / \
        B   C
       / \
      D   E

Dry running mantiqiy ko‘rinishi:

COUNT_NODES(A)
    = 1 + COUNT_NODES(B) + COUNT_NODES(C)

COUNT_NODES(B)
    = 1 + COUNT_NODES(D) + COUNT_NODES(E)

Har bir NULL child
    = 0

Natija
    = A, B, C, D, E
    = 5 ta node

Har bir haqiqiy node bir marta ko‘riladi, shuning uchun vaqt O(n). Stack chuqurligi daraxt balandligi hga teng, yordamchi xotira O(h). Muvozanatlangan daraxtda h taxminan log n, bir tomonga cho‘zilgan daraxtda esa h = n bo‘lishi mumkin. Demak, bir xil O(n) vaqtli traversalning stack xotirasi daraxt shakliga qarab farq qiladi.

Divide and conquer

Bo‘lib yechish (divide and conquer) — muammoni kichikroq mustaqil qismlarga ajratish, har birini yechish va natijalarni birlashtirish yondashuvi. Rekursiya uni ifodalashning tabiiy usuli, ammo bu ikki tushuncha aynan bir narsa emas: rekursiya boshqaruv usuli, divide and conquer esa algoritm loyihalash strategiyasidir.

Binary search saralangan arrayning kerakli yarmini tanlab, qolgan yarmini tashlab yuboradi:

FUNCTION BINARY_SEARCH(array, target, left, right)
    IF left > right
        RETURN TOPILMADI

    middle = left + FLOOR((right - left) / 2)

    IF array[middle] = target
        RETURN middle

    IF target < array[middle]
        RETURN BINARY_SEARCH(array, target, left, middle - 1)

    RETURN BINARY_SEARCH(array, target, middle + 1, right)

Har chaqiruvda qidiriladigan oraliq taxminan yarmiga kamayadi. Shu sababli vaqt O(log n), rekursiv variantning stack xotirasi ham O(log n). Iterativ binary search xuddi shu vaqt bilan O(1) yordamchi xotira ishlata oladi.

Merge sort ham arrayni qismlarga rekursiv ajratadi, qismlarni saralaydi va ularni birlashtiradi. Bu yerda bir darajadagi umumiy birlashtirish ishi O(n), darajalar soni O(log n) bo‘lgani uchun umumiy vaqt O(n log n) bo‘ladi. Rekursiya daraxti vaqt murakkabligini ko‘rishga yordam beradi.

Backtracking

Orqaga qaytib qidirish (backtracking) mumkin bo‘lgan tanlovlardan birini sinaydi, undan kelib chiqadigan holatlarni rekursiv tekshiradi va yo‘l yaramasa oldingi holatga qaytib boshqa tanlovni sinaydi.

Labirintda yo‘l qidirishning soddalashtirilgan g‘oyasi:

FUNCTION FIND_PATH(cell)
    IF cell maqsad bo‘lsa
        RETURN TRUE

    cell ni tashrif buyurilgan deb belgilash

    FOR har bir ruxsat etilgan qo‘shni cell ichida
        IF qo‘shni hali tashrif buyurilmagan bo‘lsa
            IF FIND_PATH(qo‘shni) = TRUE
                RETURN TRUE

    joriy tanlovdan qaytish
    RETURN FALSE

Rekursiya bu yerda tanlovlar zanjirini call stackda saqlaydi. Sudoku, kombinatsiyalar, permutatsiyalar va yo‘l qidirish masalalarida shu model uchraydi. Mumkin bo‘lgan variantlar soni juda katta bo‘lishi mumkin, shuning uchun noto‘g‘ri yo‘llarni erta to‘xtatish — pruning — muhim.

Memoization va takroriy kichik muammolar

Rekursiya o‘zi avtomatik ravishda samarali emas. Agar bir xil parametrli chaqiruv ko‘p marta bajarilsa, natijani saqlab, keyingi safar qayta ishlatish mumkin. Bu memoization deyiladi.

Sodda Fibonacci:

FIB(5)
├── FIB(4)
│   ├── FIB(3)
│   └── FIB(2)
└── FIB(3)       ← yana hisoblanadi

Memoization bilan:

FUNCTION FIB(n, memo)
    IF n <= 1
        RETURN n

    IF memo ichida n mavjud bo‘lsa
        RETURN memo[n]

    memo[n] = FIB(n - 1, memo) + FIB(n - 2, memo)
    RETURN memo[n]

Har bir 0..n holat bir marta to‘liq hisoblanadi. Vaqt eksponentsial o‘sishdan O(n)ga tushadi. Buning evaziga memo jadvali O(n) xotira oladi; call stack ham O(n) chuqurlikka yetishi mumkin.

Memoization rekursiyaning turi emas, takroriy hisobni cache orqali kamaytirish usulidir. U faqat bir xil kichik muammolar qayta uchraganda foyda beradi. Har holat noyob bo‘lsa, memo jadvali ortiqcha xotira sarflashi mumkin.

Vaqt murakkabligini qanday hisoblash kerak?

Rekursiv algoritm murakkabligini faqat kodda bitta yoki ikkita rekursiv chaqiruv borligiga qarab aytib bo‘lmaydi. Quyidagilarni aniqlash kerak:

1. har chaqiruv nechta yangi chaqiruv yaratadi;
2. muammo o‘lchami har safar qanchaga kamayadi;
3. rekursiv chaqiruvlardan tashqari har darajada qancha ish bajariladi;
4. bir xil kichik muammolar qayta hisoblanadimi.

Bitta chaqiruv va n - 1

T(n) = T(n - 1) + O(1)

SUM(n) har darajada bitta chaqiruv va doimiy ish bajaradi. n taxminan bir birlikdan kamayib 0ga yetadi, demak n ta daraja bor. Umumiy vaqt O(n).

Bitta chaqiruv va yarmiga kamayish

T(n) = T(n / 2) + O(1)

Binary searchda maydon har safar yarmiga kamayadi. n ni necha marta ikkiga bo‘lganda 1 qolsa, shuncha daraja hosil bo‘ladi — O(log n).

Ikkita chaqiruv va takroriy ish

Sodda Fibonacci taxminan quyidagi o‘sishga ega:

T(n) = T(n - 1) + T(n - 2) + O(1)

Chaqiruvlar daraxt shaklida ko‘payadi va bir xil holatlar takrorlanadi. Vaqt eksponentsial, odatda yuqori chegara sifatida O(2^n) deb sodda ifodalanadi. Bu aniq 2^n ta amal bajariladi degani emas; o‘sishning juda tezligini ko‘rsatadigan yuqori bahodir.

Har darajada chiziqli ish

Merge sortda ikki yarim muammo yechiladi va natijalarni birlashtirish O(n) ish talab qiladi:

T(n) = 2T(n / 2) + O(n)

Rekursiya daraxtining har darajasida jami O(n) ish, darajalar soni esa O(log n). Natija O(n log n).

Xotira murakkabligini qanday hisoblash kerak?

Rekursiyada vaqt davomida yaratilgan barcha chaqiruvlarni emas, bir vaqtda stackda turgan maksimal freymlar sonini hisoblash kerak.

Sodda Fibonacci juda ko‘p chaqiruv yaratadi, lekin ularning hammasi bir paytda stackda turmaydi. Bir tarmoq yakunlangach, uning freymlari chiqariladi va keyingi tarmoq bajariladi. Maksimal chuqurlik O(n), shuning uchun stack xotirasi O(n); vaqt esa eksponentsial bo‘lishi mumkin.

Umumiy chaqiruvlar soni → vaqtga ta’sir qiladi
Maksimal faol chaqiruvlar chuqurligi → stack xotirasiga ta’sir qiladi

Har bir freym ichida katta ma’lumot nusxalansa, faqat chuqurlikni aytish yetmaydi. Masalan, har darajada hajmi nga bog‘liq yangi array yaratilsa, umumiy yordamchi xotira kattaroq bo‘ladi. Parametr sifatida obyekt reference’i uzatiladimi yoki butun ma’lumot nusxalanadimi — bu til va implementatsiyaga bog‘liq.

Murakkablik jadvali

Jadval muayyan klassik implementatsiyalarni nazarda tutadi. Masalan, merge sortning birlashtirish uchun ishlatadigan qo‘shimcha xotirasi ma’lumot turi va implementatsiyaga qarab O(n) bo‘lishi mumkin; jadvaldagi stack qiymati butun yordamchi xotiraning hammasi emas.

Rekursiya va iteratsiya

Iteratsiya FOR yoki WHILE kabi takrorlash mexanizmi orqali ishni qayta bajaradi. Rekursiya esa yangi funksiya chaqiruvlari orqali takrorlaydi. Ko‘p chiziqli rekursiv algoritmlarni siklga aylantirish mumkin.

SUM(n)ning iterativ ko‘rinishi:

FUNCTION SUM_ITERATIVE(n)
    total = 0

    FOR value = 1 DAN n GACHA
        total = total + value

    RETURN total

Ikkala variant ham O(n) vaqt oladi. Rekursiv variant O(n) call stack xotirasi, iterativ variant esa O(1) yordamchi xotira ishlatadi. Bu oddiy masalada iteratsiya amaliy jihatdan afzal.

Ammo daraxt traversalida iterativ variant stack ehtiyojini yo‘qotmaydi; call stack o‘rniga dasturchi boshqaradigan stack ma’lumotlar tuzilmasi kerak bo‘lishi mumkin:

Rekursiv traversal → holat call stackda saqlanadi
Iterativ traversal → holat explicit stackda saqlanadi

Shuning uchun “iteratsiya har doim O(1) xotira ishlatadi” degan umumlashtirish noto‘g‘ri. Muammoning keyin qayerga qaytishni eslab qolish talabi bo‘lsa, bu holat qayerdadir saqlanishi kerak.

Tanlov “qaysi biri zamonaviyroq?” degan savolga emas, muammo shakli, maksimal chuqurlik, aniqlik va resurs cheklovlariga bog‘liq.

To‘g‘rilik mantig‘i

Rekursiv algoritmning to‘g‘riligini tushuntirish matematik induksiyaga o‘xshaydi, lekin uni sodda savollar bilan ko‘rish mumkin.

SUM(n) uchun:

1. Tayanch holat to‘g‘rimi? SUM(0) = 0 — ha.
2. Kichik holat to‘g‘ri deb faraz qilsak nima bo‘ladi? SUM(n - 1) 1..n-1 yig‘indisini to‘g‘ri qaytarsin.
3. Joriy holat undan to‘g‘ri quriladimi? Unga n qo‘shilsa 1..n yig‘indisi hosil bo‘ladi.
4. Jarayon tayanch holatga yetadimi? Manfiy bo‘lmagan n har safar bittadan kamayadi va 0ga keladi.

Bu fikrlash usuli rekursiv funksiyani “ichki chaqiruvlarning hammasini miyada bir paytda bajarish” zaruratidan qutqaradi. Kichik chaqiruv o‘z shartnomasi bo‘yicha to‘g‘ri javob beradi deb qarab, joriy darajaga e’tibor qaratiladi.

Real qo‘llanishlar

Fayl tizimini ko‘rib chiqish

Papka ichida fayl va subfolderlar, subfolder ichida yana shu turdagi ma’lumot bor. Fayl qidirish, katalog hajmini hisoblash yoki daraxt ko‘rinishini chiqarishda funksiya joriy papkani ko‘radi va har bir subfolder uchun o‘zini chaqiradi. Tayanch holat — ichki papkasi yo‘q katalog yoki oddiy fayl.

Amaliy tizimda symbolic linklar sikl hosil qilishi, ruxsat xatolari yuz berishi yoki papka chuqurligi juda katta bo‘lishi mumkin. Shu sababli real dastur tashrif buyurilgan obyektlarni kuzatishi va xatolarni boshqarishi kerak.

HTML va interfeys daraxtlari

HTML elementlar boshqa elementlarni o‘z ichiga oladi. Sahifani ko‘rsatish, element qidirish yoki stilni avlodlarga tatbiq qilishda daraxt traversal ishlatiladi. Joriy element qayta ishlanadi, keyin child elementlar rekursiv ko‘riladi. Juda chuqur yoki tashqi manbadan kelgan tuzilmalarda iterativ traversal xavfsizroq bo‘lishi mumkin.

Parserlar va ifodalar

(2 + 3) * 4 kabi ifoda kichik ifodalardan tuziladi. Parser qavs ichidagi ifodani yana shu qoidalar bilan tahlil qiladi. Hosil bo‘lgan expression tree’ni hisoblashda operator node’i chap va o‘ng kichik ifoda natijalarini rekursiv oladi.

Qidiruv va o‘yin holatlari

Shaxmat yoki boshqa o‘yinda joriy yurishdan keyin bir nechta yangi holat paydo bo‘ladi. Algoritm ma’lum chuqurlikkacha mumkin bo‘lgan yurishlarni rekursiv tekshirishi mumkin. Holatlar soni juda tez ko‘paygani uchun chuqurlik chegarasi, pruning va natijalarni cachelash zarur bo‘ladi.

Saralash va qidirish

Merge sort, quicksort va binary search muammoni kichik qismlarga ajratish mantig‘ini rekursiv ifodalaydi. Bunda rekursiya ma’lumotlar tuzilmasidan emas, algoritmning bo‘lib yechish tabiatidan kelib chiqadi. Quicksortda noto‘g‘ri pivot tanlovi rekursiya chuqurligini O(n)gacha olib borishi mumkin; shu sababli o‘rtacha va eng yomon holatni alohida baholash muhim.

Afzalliklari

• Rekursiv tuzilmani tabiiy ifodalaydi. Tree, papka va ichma-ich ifodalar kod modeliga bevosita mos tushadi.
• Murakkab boshqaruv holatini call stack saqlaydi. Qayerga qaytish kerakligini qo‘lda boshqarish kamayadi.
• Divide and conquer va backtrackingni tushunarli yozadi. Har daraja faqat joriy kichik muammoga e’tibor beradi.
• To‘g‘rilikni kichik holat orqali asoslash mumkin. Tayanch holat va rekursiv qadam aniq ajraladi.

Bu soddalik bepul emas. Call stack xotirasi, funksiya chaqiruv xarajati va chuqurlik chegarasi rekursiyaning asosiy narxidir.

Cheklovlari

• Har faol chaqiruv uchun stack frame kerak bo‘ladi.
• Chuqurlik katta bo‘lsa stack overflow yuz berishi mumkin.
• Oddiy chiziqli takrorlashda sikldan ko‘ra ko‘proq xotira va chaqiruv xarajati talab qilishi mumkin.
• Noto‘g‘ri tayanch holat yoki kamaymaydigan muammo cheksiz rekursiyaga olib keladi.
• Daraxtsimon rekursiyada bir xil kichik muammolar ko‘p marta hisoblanishi mumkin.
• Rekursiv bajarilish tartibini debuggerda kuzatish boshlovchi uchun qiyinroq bo‘lishi mumkin.
• Ba’zi tillarda ruxsat etilgan recursion depth nisbatan kichik va implementatsiyaga bog‘liq.

Keng tarqalgan xatolar va edge case’lar

Tayanch holatni unutish

Tayanch holatsiz chaqiruvlar davom etadi. Bu matematik ma’nodagi cheksiz jarayon amalda cheksiz ishlamaydi: call stack cheklangan, shuning uchun dastur odatda stack overflow yoki recursion depth xatosi bilan to‘xtaydi.

Tayanch holatga yetib bormaslik

n = 0 sharti borligi musbat, manfiy va noto‘g‘ri kirishlarning barchasi unga yetadi degani emas. Har bir ruxsat etilgan kirish uchun o‘lchov belgilang: masalan, n, qolgan elementlar soni yoki qidiruv oralig‘i. Bu o‘lchov har qadamda qat’iy kamayib, pastki chegaraga yetishi kerak.

Noto‘g‘ri chegara

n = 0 o‘rniga n = 1 tanlash ayrim formulalarda to‘g‘ri, boshqalarida bo‘sh kirishni hisobga olmaydi. Bo‘sh array, bo‘sh string, NULL tree va bitta elementli tuzilmani alohida sinash kerak.

RETURNni unutish

Ichki chaqiruv natija qaytarsa ham, tashqi funksiya uni qaytarmasa yoki ishlatmasa javob yo‘qoladi:

FUNCTION BROKEN(n)
    IF n = 0
        RETURN 0

    SUM(n - 1)        // natija tashqi chaqiruvga uzatilmadi

Rekursiv chaqiruvdan kelgan qiymat joriy natijaga qanday qo‘shilishini aniq yozish kerak.

Lokal va umumiy holatni aralashtirish

Har chaqiruvning lokal o‘zgaruvchisi alohida, ammo umumiy mutable obyekt barcha chaqiruvlar orasida bo‘lishilishi mumkin. Backtrackingda tanlov qo‘shilib, qaytishda olib tashlanmasa, bir tarmoqdagi holat boshqasiga sizib o‘tadi.

tanlovni qo‘sh
rekursiv tekshir
tanlovni olib tashla    // holatni tiklash

Kirishni keraksiz nusxalash

Har chaqiruvda arrayning yangi bo‘lagini nusxalash kodni sodda ko‘rsatishi mumkin, ammo vaqt va xotira xarajatini oshiradi. Ko‘pincha boshlanish va tugash indexlarini uzatish yetarli. Nusxa olinishi yoki view/reference uzatilishi til va kutubxona implementatsiyasiga bog‘liq.

Eksponentsial rekursiyani chiziqli deb o‘ylash

Kodda n kamaygani uchun algoritm avtomatik O(n) bo‘lmaydi. Har chaqiruv ikkita yangi chaqiruv yaratsa, chaqiruvlar soni daraxt bo‘ylab tez ko‘payishi mumkin. Recursion tree chizish va bir xil parametrlar takrorlanishini tekshirish kerak.

Chuqurlikni faqat o‘rtacha holat bilan baholash

Muvozanatlangan tree O(log n) chuqurlikda bo‘lishi mumkin, ammo bir tomonga qiyshaygan tree O(n) chuqurlikka ega. Tashqi foydalanuvchi yaratgan yoki nazorat qilinmaydigan ma’lumot uchun eng yomon holat stack overflowga sabab bo‘lishi mumkin.

Siklli graphda tashriflarni kuzatmaslik

Tree’da har node’ga odatda bitta yo‘l bor. Graphda esa A → B → A kabi sikl bo‘lishi mumkin. Rekursiv DFS visited to‘plamisiz bir node’lar orasida cheksiz aylanadi. Graph traversalida tayanch holatning bir qismi — node avval ko‘rilganini tekshirish.

Natijani haddan tashqari katta hisoblash

Faktorial kabi rekursiv hisob to‘g‘ri tugasa ham, natija ma’lumot turiga sig‘masligi mumkin. Bu recursion xatosi emas, sonli overflow muammosi. Algoritmning kirish chegarasi va ishlatilayotgan son modelini alohida hisobga olish kerak.

Stack overflow nima?

Call stack uchun xotira cheklangan. Har rekursiv chaqiruv yangi freym qo‘shsa, juda katta chuqurlikda joy tugaydi. Bu stack overflow deyiladi.

COUNTDOWN(1 000 000)
    → COUNTDOWN(999 999)
        → COUNTDOWN(999 998)
            → ... juda ko‘p faol freym

Aniq chegarani universal son bilan aytib bo‘lmaydi. U til, runtime, operatsion tizim, freym hajmi va sozlamalarga bog‘liq. Muammoni hal qilish yo‘llari:

• chiziqli rekursiyani siklga aylantirish;
• tree yoki graph uchun explicit stack ishlatish;
• qayta ishlashni bo‘laklash;
• algoritm chuqurligini kamaytirish;
• faqat muhit kafolatlasa tail call optimizationga tayanish.

Stack limitini shunchaki kattalashtirish ba’zan vaqtinchalik yordam beradi, lekin cheklanmagan kirish uchun algoritmik xavfni yo‘qotmaydi.

Qachon rekursiya ishlatish kerak?

Rekursiya quyidagi vaziyatlarda kuchli tanlov:

• ma’lumot tree, graph yoki ichma-ich papkalar kabi rekursiv tuzilishga ega;
• muammo o‘ziga o‘xshash kichik qismlarga tabiiy ajraladi;
• divide and conquer algoritmi ishlatiladi;
• backtrackingda tanlovlar daraxti bo‘ylab yurish kerak;
• maksimal chuqurlik nazorat ostida va call stack uchun xavfsiz;
• rekursiv ifoda iterativ variantdan ancha tushunarli va xatoga kamroq moyil.

Rekursiyani tanlaganda faqat kod uzunligiga qaramang. Tayanch holat, progress o‘lchovi, maksimal chuqurlik va takroriy kichik muammolarni oldindan tekshiring.

Qachon rekursiya ishlatmaslik kerak?

Quyidagi holatlarda iteratsiya yoki explicit ma’lumotlar tuzilmasi yaxshiroq bo‘lishi mumkin:

• oddiy chiziqli takrorlash sikl bilan ravshan ifodalansa;
• kirish juda katta va rekursiya chuqurligi O(n) bo‘lsa;
• runtime recursion depth yoki stack xotirasini qattiq cheklasa;
• funksiya chaqiruvining qo‘shimcha xarajati kritik bo‘lsa;
• tail call optimization mavjudligi kafolatlanmasa;
• tashqi ma’lumot juda chuqur yoki ataylab zararli tuzilma yaratishi mumkin bo‘lsa;
• sodda rekursiya bir xil kichik muammolarni eksponentsial marta hisoblasa va memoization yoki dynamic programming qo‘llanmasa.

Iterativ yechim har doim tushunarliroq degani ham emas. Tree DFSni explicit stack bilan yozish call stack xavfini boshqaradi, ammo kodda stackni qo‘lda yuritish talab qilinadi. To‘g‘ri tanlov o‘qilish qulayligi va resurs xavfsizligi o‘rtasidagi muvozanatdir.

Rekursiv kodni tekshirish ro‘yxati

Rekursiv algoritm yozilgach, quyidagilarni tekshirish foydali:

1. Bo‘sh yoki eng kichik kirish qanday natija qaytaradi?
2. Tayanch holat rekursiv chaqiruvdan oldin tekshiriladimi?
3. Har chaqiruvda qaysi miqdor kamayadi?
4. Barcha ruxsat etilgan kirishlar tayanch holatga yetadimi?
5. Ichki chaqiruv natijasi tashqi natijaga to‘g‘ri qo‘shiladimi?
6. Maksimal chaqiruv chuqurligi qancha?
7. Bir xil parametrli chaqiruvlar takrorlanadimi?
8. Mutable holat qaytishda tiklanadimi?
9. Graph bo‘lsa sikllar qanday aniqlanadi?
10. Iterativ variant xavfsizroq yoki soddaroq emasmi?

Eng muhim xulosa

Rekursiya — muammoni o‘ziga o‘xshash kichikroq muammo orqali yechish usuli. Uning to‘g‘ri ishlashi uchun tayanch holat, unga tomon aniq progress va kichik javobdan joriy javobni to‘g‘ri qurish kerak.

Har rekursiv chaqiruv call stackda alohida freym yaratadi. Chaqiruvlar tayanch holatgacha pastga tushadi, keyin natijalar teskari tartibda yuqoriga qaytadi. Vaqt murakkabligi umumiy chaqiruvlar va har chaqiruvdagi ishga, xotira murakkabligi esa maksimal faol chuqurlik va har freymdagi ma’lumotga bog‘liq.

Rekursiya tree, graph, divide and conquer hamda backtrackingda muammoning tuzilishini juda tabiiy ifodalaydi. Oddiy chiziqli takrorlashda esa sikl ko‘pincha kamroq xotira va kichikroq amaliy xarajat bilan ishlaydi. Rekursiya maqsad emas — muammoning shakliga mos boshqaruv vositasidir.

Rekursiyani tushungach, tree va graph traversal, merge sort, quicksort, dynamic programming hamda backtracking kabi mavzulardagi algoritmlarning ichki mantiqini ko‘rish osonlashadi. Keyingi bosqichda call stack g‘oyasini umumiy stack ma’lumotlar tuzilmasi bilan solishtirish foydali: rekursiyada runtime yashirin boshqargan holatni iterativ algoritmda dasturchi explicit stack orqali o‘zi boshqarishi mumkin.