WisarWisar
Dasturlash kitobi/3-QISM — Algoritmlar12 daqiqa

3.11-bob: Rekursiya va backtracking

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 11-mavzu

1. Kirish va motivatsiya

Hozirgacha rekursiyani bir necha marta ishlatdik: merge/quick sort 3.9-bob, tree traversal 3.6-bob, DFS 3.7-bob, rekursiv binary search 3.10-bob. Endi uni chuqur o'rganamiz. Rekursiya — funksiyaning o'zini chaqirishi — boshida sehrli ko'rinadi, lekin ko'p muammoni tabiiy va elegant yechadi.

Asosiy g'oya: katta muammoni o'ziga o'xshash kichikroq muammoga bo'lish (0.6: decomposition), eng kichik holatgacha (base case). Backtracking — rekursiyaning kuchli kengaytmasi: barcha variantlarni sinab ko'rish (sina ishlamasa orqaga qaytib boshqasini sina) — labirint, sudoku, kombinatsiyalar.

O'xshatish (rekursiya): ikki oyna bir-biriga qaragan — cheksiz aks etish (har biri ichida kichikroq). Yoki rus matryoshka qo'g'irchog'i: har biri ichida kichikroq, eng kichigigacha (base case). Rekursiya — masalani o'zining kichikroq nusxasiga bo'lish.

O'xshatish (backtracking): labirintda yo'l qidirish. Bir yo'lni sina; tupik bo'lsa — orqaga qaytib (backtrack), boshqa yo'lni sina. Barcha imkoniyatlarni tizimli sinash.

Nega muhim?

  • Daraxt/graf (3.6, 3.7), divide-and-conquer 3.9-bob, DP 3.12-bob — rekursiyaga tayanadi.
  • Backtracking — kombinatorik masalalar (permutatsiya, kombinatsiya, sudoku, N-queens).
  • Elegant, ixcham kod; ba'zi masalalar rekursiyasiz juda murakkab.
  • Intervyu klassikasi.

2. Nazariya — chuqur tushuntirish

2.1. Rekursiya nima va ikki qismi

Rekursiya — funksiyaning o'zini chaqirishi. Har rekursiv funksiyada ikki qism bo'lishi SHART:

  1. Base case (asos holat) — rekursiya to'xtaydigan shart (eng kichik holat). Busiz — cheksiz rekursiya stack overflow (0.1, 2.4).
  2. Recursive case (rekursiv holat) — funksiya o'zini kichikroq kirish bilan chaqiradi (base case sari).
js
function faktorial(n) {
  if (n <= 1) return 1;          // BASE CASE — to'xtaydi
  return n * faktorial(n - 1);   // RECURSIVE CASE — kichikroq (n-1)
}
// faktorial(4) = 4 * 3 * 2 * 1 = 24

Base case'siz rekursiya = cheksiz = Maximum call stack size exceeded (0.1, 2.4). Har rekursiyada "bu qachon TO'XTAYDI?" deb so'rang 0.6-bob.

2.2. Rekursiya qanday ishlaydi — call stack (2.4)

Har rekursiv chaqiruv call stackga 2.4-bob qo'shiladi; base case'ga yetganda — teskari yechiladi:

text
  faktorial(4)
     4 * faktorial(3)        stack: [fakt(4)]
       3 * faktorial(2)      stack: [fakt(4), fakt(3)]
         2 * faktorial(1)    stack: [fakt(4), fakt(3), fakt(2)]
           1  (BASE)         stack: [..., fakt(1)]
         2 * 1 = 2           (yechiladi, stackdan chiqadi)
       3 * 2 = 6
     4 * 6 = 24

Stack chuqurligi = rekursiya darajasi. Juda chuqur (masalan faktorial(100000)) stack overflow (2.4, 0.1).

Chaqiruvlar daraxti (recursion tree). Faktorialdek bitta chaqiruvli (linear) rekursiyada call stack tik chiziq — har daraja bittadan. Ammo bir chaqiruv ikki+ chaqiruv tug'sa (fibonacci), chaqiruvlar daraxtga yoyiladi. fib(5) ni chizamiz:

text
                fib(5)
            ┌─────┴─────┐
         fib(4)        fib(3)
        ┌──┴──┐       ┌──┴──┐
     fib(3)  fib(2) fib(2) fib(1)
     ┌─┴─┐    ...    ...
  fib(2) fib(1)

Daraxt = nega sekin. fib(3) bu yerda ikki marta, fib(2) uch marta hisoblanadi — daraxt pastga tarvaqaylab, bir xil tugun qayta-qayta takrorlanadi. Shu sababli naive fibonacci O(2ⁿ) 2.4-bob. Aynan shu takroriy tugunlarni bir marta hisoblab saqlash — memoizatsiya (3.12 DP) — daraxtni qirqib, eksponensialni chiziqliga aylantiradi. (Backtracking ham shunday daraxt: har shox — bitta variant; pruning — foydasiz shoxni daraxtdan kesish, 2.7.)

2.3. Rekursiya vs iteratsiya (tsikl)

Har rekursiv yechimni tsikl bilan ham yozish mumkin (va aksincha):

js
// Rekursiv
function yigindiRec(n) { return n <= 0 ? 0 : n + yigindiRec(n - 1); }
// Iterativ (tsikl — 2.2)
function yigindiIter(n) { let s = 0; for (let i = 1; i <= n; i++) s += i; return s; }
Rekursiya Iteratsiya
O'qishlilik tabiiy (daraxt, bo'lish) tabiiy (chiziqli)
Xotira O(chuqurlik) — stack O(1) odatda
Stack overflow xavf bor yo'q

Qachon rekursiya: daraxtsimon/bo'linadigan masala (tree — 3.6, divide-and-conquer — 3.9), backtracking. Qachon iteratsiya: oddiy chiziqli takror (yig'indi, qidiruv). JS'da chuqur rekursiya xavfli (stack).

2.4. Klassik rekursiya misollari

js
// Fibonacci (sodda — lekin sekin, 3.12 da yaxshilanadi)
function fib(n) {
  if (n <= 1) return n;                  // base case (fib(0)=0, fib(1)=1)
  return fib(n - 1) + fib(n - 2);        // ikki rekursiv chaqiruv
}
//  O(2ⁿ) — eksponensial! (bir xil qiymat qayta-qayta hisoblanadi — 3.12)

// Massiv yig'indisi (rekursiv)
function yigindi(arr, i = 0) {
  if (i >= arr.length) return 0;         // base case
  return arr[i] + yigindi(arr, i + 1);
}

// Matnni ag'darish (rekursiv)
function agdar(s) {
  if (s.length <= 1) return s;           // base case
  return agdar(s.slice(1)) + s[0];       // qolganini ag'darib, birinchini oxiriga
}

2.5. Rekursiya turlari

  • Linear — bitta rekursiv chaqiruv (faktorial, yig'indi).
  • Binary/multiple — ikki+ chaqiruv (fibonacci, tree traversal — 3.6).
  • Tail recursion — rekursiv chaqiruv oxirgi amal (ba'zi tillar optimallashtiradi; JS odatda yo'q).

2.6. Backtracking — barcha variantlarni sinash

Backtracking — rekursiya bilan barcha imkoniyatlarni tizimli sinash: variantni tanla davom et (rekursiya) ishlamasa bekor qil (backtrack) keyingisini sina:

text
  Naqsh:
  for har bir variant:
    tanla (qo'sh)
    agar to'liq yechim  saqla
    aks holda  rekursiv davom et
    bekor qil (olib tashla — backtrack)
js
// Massivning barcha permutatsiyalari (tartiblanishlari)
function permutatsiyalar(arr) {
  const natija = [];
  function backtrack(joriy, qolgan) {
    if (qolgan.length === 0) { natija.push([...joriy]); return; }  // to'liq (base)
    for (let i = 0; i < qolgan.length; i++) {
      joriy.push(qolgan[i]);                          // TANLA
      backtrack(joriy, [...qolgan.slice(0, i), ...qolgan.slice(i + 1)]);  // DAVOM
      joriy.pop();                                    // BEKOR QIL (backtrack)
    }
  }
  backtrack([], arr);
  return natija;
}
permutatsiyalar([1, 2, 3]);   // [[1,2,3],[1,3,2],[2,1,3],...] — 6 ta (3!)

2.7. Backtracking klassik masalalari

  • Permutatsiyalar / kombinatsiyalar — barcha tartiblanishlar/tanlovlar.
  • Subsets (qism to'plamlar) — barcha kichik to'plamlar.
  • N-Queens — N ta vazirni shaxmatda urilmaydigan joylash.
  • Sudoku — har katakka raqam sinash.
  • Labirint/yo'l — barcha yo'llarni sinash.
  • Pruning (kesish) — ishlamaydigan shoxni erta tashlash (optimizatsiya).

2.8. Murakkablik

  • Rekursiya: vaqt — chaqiruvlar soni; xotira — O(chuqurlik) (stack).
  • Backtracking: ko'pincha eksponensial (O(2ⁿ), O(n!)) — barcha variant. Lekin pruning bilan amalda tezroq.

Backtracking — to'liq qidiruv (brute force) ning aqlli shakli. Kichik n uchun maqbul; katta n uchun DP 3.12-bob yoki boshqa usul kerak.

3. Sintaksis — tez ma'lumotnoma

text
REKURSIYA:    base case (to'xtash) + recursive case (kichikroq)
               base case'siz  stack overflow (2.4, 0.1)
CALL STACK:   har chaqiruv stackka; chuqurlik = daraja
BACKTRACKING: tanla  rekursiv davom  bekor qil (pop)
              for variant: choose  recurse  unchoose
QACHON:       rekursiya — daraxt/bo'linadigan; iteratsiya — chiziqli

4. Batafsil kod namunalari

Misol 1 — Base/recursive case (2.1)

js
// Sonni ikkilik (binary) ko'rinishga (rekursiv — 0.1)
function binary(n) {
  if (n === 0) return "0";                // base case
  if (n === 1) return "1";                // base case
  return binary(Math.floor(n / 2)) + (n % 2);   // recursive (0.1: 2 ga bo'lish)
}
binary(13);   // "1101"

// Daraxt balandligi (3.6 takror — rekursiya tabiiy)
function balandlik(node) {
  if (!node) return 0;                     // base case
  return 1 + Math.max(balandlik(node.left), balandlik(node.right));
}

Misol 2 — Power set / subsets (backtracking — 2.6)

js
// Barcha kichik to'plamlar (subsets)
function subsets(arr) {
  const natija = [];
  function backtrack(start, joriy) {
    natija.push([...joriy]);              // har holat — to'plam (2.8)
    for (let i = start; i < arr.length; i++) {
      joriy.push(arr[i]);                 // TANLA
      backtrack(i + 1, joriy);            // DAVOM (keyingilardan)
      joriy.pop();                        // BEKOR QIL
    }
  }
  backtrack(0, []);
  return natija;
}
subsets([1, 2, 3]);   // [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] — 2³=8 ta

Misol 3 — Kombinatsiyalar (n dan k ta tanlash — 2.6)

js
// n elementdan k ta tanlashning barcha usullari
function kombinatsiyalar(arr, k) {
  const natija = [];
  function backtrack(start, joriy) {
    if (joriy.length === k) { natija.push([...joriy]); return; }  // to'liq (base)
    for (let i = start; i < arr.length; i++) {
      joriy.push(arr[i]);                 // TANLA
      backtrack(i + 1, joriy);            // DAVOM
      joriy.pop();                        // BEKOR QIL
    }
  }
  backtrack(0, []);
  return natija;
}
kombinatsiyalar([1, 2, 3, 4], 2);   // [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Misol 4 — N-Queens (klassik backtracking + pruning — 2.7)

js
// N×N shaxmatda N vazirni urilmaydigan joylash (necha usul)
function nQueens(n) {
  let son = 0;
  const ustun = new Set(), diag1 = new Set(), diag2 = new Set();   // urilish (3.5)
  function qoy(qator) {
    if (qator === n) { son++; return; }   // hamma vazir qo'yildi (base)
    for (let ust = 0; ust < n; ust++) {
      // PRUNING: bu ustun/diagonal band bo'lsa — o'tkaz (2.7)
      if (ustun.has(ust) || diag1.has(qator - ust) || diag2.has(qator + ust)) continue;
      ustun.add(ust); diag1.add(qator - ust); diag2.add(qator + ust);   // TANLA
      qoy(qator + 1);                                                    // DAVOM
      ustun.delete(ust); diag1.delete(qator - ust); diag2.delete(qator + ust); // BEKOR
    }
  }
  qoy(0);
  return son;
}
nQueens(8);   // 92 (8×8 shaxmatda 8 vazir joylashining usullari)

5. To'g'ri va noto'g'ri holatlar

1) Base case'siz rekursiya

js
//  to'xtash sharti yo'q  stack overflow (2.1, 0.1)
function bad(n) { return n + bad(n - 1); }

//  base case
function good(n) { if (n <= 0) return 0; return n + good(n - 1); }

2) Backtracking'da "bekor qilish"ni unutish

js
//  pop yo'q  joriy holat keyingi shoxga "oqib ketadi" (2.6)
joriy.push(x); backtrack(...);   // pop yo'q!

//  tanla  davom  BEKOR QIL
joriy.push(x); backtrack(...); joriy.pop();

3) Natijani nusxalamasdan saqlash

js
//  natija.push(joriy) — havola; keyin joriy o'zgaradi  hammasi buziladi (2.8)
natija.push(joriy);

//  nusxa (2.8: spread)
natija.push([...joriy]);

4) Chuqur rekursiya (iteratsiya o'rniga)

text
 faktorial(1000000) — stack overflow (2.3)
 oddiy chiziqli takror uchun tsikl (2.3)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Maximum call stack size exceeded

Sababi: base case yo'q yoki noto'g'ri, yoki juda chuqur rekursiya (2.1, 2.3, 0.1). Yechimi: base case'ni tekshiring; chuqur bo'lsa iterativ (tsikl/o'z stack — 3.4).

Xato 2 — Backtracking noto'g'ri natija (holatlar aralashgan)

Sababi: "bekor qilish" (pop/delete) yo'q yoki nusxa olinmagan (2.6, 2-3 holat). Yechimi: har tanlovdan keyin bekor qiling; natijani [...joriy] bilan saqlang.

Xato 3 — Sekin (eksponensial)

Sababi: naive rekursiya bir xil qiymatni qayta hisoblaydi (fibonacci O(2ⁿ) — 2.4). Yechimi: memoizatsiya 3.12-bob yoki DP.

Xato 4 — Rekursiv funksiya undefined qaytaradi

Sababi: rekursiv chaqiruvda return unutilgan (2.3-funksiya). Yechimi: return funksiya(...).

Xato 5 — Backtracking juda sekin (katta n)

Sababi: pruning yo'q — barcha variant 2.8-bob. Yechimi: ishlamaydigan shoxni erta kesing (N-Queens — Misol 4); yoki DP 3.12-bob.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

  • Tree/Graph (3.6, 3.7): traversal, DFS — rekursiya.
  • Saralash 3.9-bob: merge/quick — divide-and-conquer (rekursiya).
  • Qidiruv 3.10-bob: rekursiv binary search.
  • DP 3.12-bob: rekursiya + memoizatsiya.
  • Call stack (2.4, 0.1): rekursiya mexanizmi; stack overflow.
  • Closure 2.4-bob: backtracking ichki funksiya tashqi natijaga.
  • Real: fayl tizimi yurish 0.2-bob, JSON parse 2.8-bob, DOM traversal 2.16-bob.

8. Eng yaxshi amaliyotlar (best practices)

  • Har rekursiyada base case — birinchi yozing; "qachon to'xtaydi?" (2.1, 0.6).
  • Daraxt/bo'linadigan rekursiya; chiziqli iteratsiya 2.3-bob.
  • Chuqur rekursiyadan ehtiyot (JS stack) — iterativ yoki tail 2.3-bob.
  • Backtracking naqshi: tanla davom bekor qil 2.6-bob.
  • Natijani nusxalang ([...joriy]) — havola tuzog'i (3-holat).
  • Pruning bilan backtracking'ni tezlashtiring (2.7, Misol 4).
  • Takror hisob memoizatsiya 3.12-bob — eksponensialdan saqlaydi.
  • Kichik misolda call stack'ni qo'lda chizing — tushunish/debug 2.2-bob.

9. Amaliy loyiha: "Rekursiya va Backtracking Masalalari"

Rekursiya va backtracking'ni amalda mustahkamlash.

Maqsad

Base/recursive case, call stack tushunchasini va backtracking naqshini (tanla-davom-bekor) o'zlashtirish.

Talablar (requirements)

Rekursiya:

  1. faktorial, yigindi, agdar (matn) — base case bilan (2.1, 2.4).
  2. power(base, exp) — rekursiv daraja (tez daraja: exp/2 bilan — bonus).
  3. Daraxt/fayl tizimi yurish (3.2 loyihasini rekursiv) — papka ichi rekursiv.
  4. Har biri uchun call stack chuqurligini muhokama qiling 2.2-bob.

Backtracking: 5. Subsets (barcha kichik to'plamlar — Misol 2). 6. Permutatsiyalar (barcha tartiblanishlar — Misol/2.6). 7. Kombinatsiyalar (n dan k — Misol 3). 8. Qavslar generatsiyasi: n juft to'g'ri qavs (((())), (()())...) — pruning bilan. 9. (Bonus) N-Queens yoki sodda labirint yo'li (Misol 4). 10. Har backtracking'da "tanla-davom-bekor" naqshini aniq ko'rsating; natijani nusxalang (3-holat).

Maslahatlar (hint)

  • Base case birinchi 2.1-bob; "qachon to'xtaydi?".
  • Backtracking: push (tanla) recurse pop (bekor) 2.6-bob.
  • Natija: natija.push([...joriy]) (nusxa — 3-holat).
  • Qavslar: ochiq < n bo'lsa "(" qo'sh; yopiq < ochiq bo'lsa ")" qo'sh (pruning).
  • Eksponensiallikni his qiling (subsets 2ⁿ, permutatsiya n!).
  • Stack overflow'dan ehtiyot (chuqur rekursiya).

"Tayyor" mezonlari (acceptance criteria)

  • Rekursiv funksiyalar base case bilan to'g'ri ishlaydi.
  • Subsets 2ⁿ, permutatsiya n!, kombinatsiya to'g'ri sonni beradi.
  • Qavslar generatsiyasi faqat to'g'ri qavslarni beradi.
  • Har backtracking "tanla-davom-bekor" naqshida.
  • Natija nusxalangan (havola tuzog'i yo'q).
  • (Bonus) N-Queens/labirint ishlaydi.
  • Stack overflow yo'q; base case'lar to'g'ri.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda rekursiya va backtrackingni o'rgandik:

  • Rekursiya — funksiyaning o'zini chaqirishi; base case (to'xtash) + recursive case (kichikroq). Base case'siz stack overflow (2.4, 0.1).
  • Call stack orqali ishlaydi; chuqurlik = daraja. Rekursiya vs iteratsiya — daraxt/bo'linadigan vs chiziqli.
  • Backtracking — barcha variantni tizimli sinash: tanla davom bekor qil; permutatsiya, kombinatsiya, subsets, N-Queens.
  • Pruning — ishlamaydigan shoxni erta kesish (tezlik).
  • Tuzoqlar: base case'siz, bekor qilmaslik, nusxalamaslik, chuqur rekursiya.

Keyingi bob — 3.12-bob: Dinamik dasturlash (DP) asoslari. Rekursiyada (fibonacci) bir xil qiymat qayta-qayta hisoblanib, O(2ⁿ) sekinlik ko'rdik. DP aynan shuni hal qiladi: hisoblangan natijalarni saqlab (memoizatsiya/tabulyatsiya), qayta hisoblamaslik. Bu — rekursiya + Hash Table 3.5-bob ning kuchli birikmasi.

Foydalanilgan rasmiy/ishonchli manbalar

  • Universal CS — recursion, call stack, backtracking, pruning
  • bigocheatsheet.com — rekursiv algoritmlar murakkabligi
  • MDN Web Docs — funksiya, call stack 2.4-bob, RangeError (stack overflow)

Izohlar (0)

Izoh yozish uchun kiring.

  • Hozircha izoh yo'q. Birinchi bo'ling!
3.11-bob: Rekursiya va backtracking — Wisar