Chapter 46 — Recursion

Recursion (rekursiya) — function o'zini-o'zi chaqirishi. Bu bobda rekursiyaning ishlash mexanizmini, uni qachon ishlatish kerakligini va uning xavflarini chuqur o'rganamiz.

---

46.1 Recursion nima?

Simple Explanation

Recursion — muammoni, o'sha muammoning kichikroq nusxasi orqali hal qilish, va function ichida o'zining o'zini qayta chaqirish.

Real-Life Analogy

🪆 Recursion — bu matryoshka (rus qo'g'irchog'i): har bir katta qo'g'irchoq ichida — xuddi shu qo'g'irchoqning kichikroq nusxasi bor, toki eng kichik, ichi bo'sh qo'g'irchoqqa (asosiy holat) yetguncha.

Example — Faktorial hisoblash

script.js
JavaScriptNusxalash
01function factorial(n) {
02    if (n <= 1) {
03        return 1; // Base case (asosiy holat)
04    }
05    return n * factorial(n - 1); // Recursive case (rekursiv holat)
06}
07 
08console.log(factorial(5)); // 120 (5 × 4 × 3 × 2 × 1)

How It Works — bosqichma-bosqich

code.text
TEXTNusxalash
01factorial(5)
02= 5 * factorial(4)
03= 5 * (4 * factorial(3))
04= 5 * (4 * (3 * factorial(2)))
05= 5 * (4 * (3 * (2 * factorial(1))))
06= 5 * (4 * (3 * (2 * 1)))
07= 120

46.2 ⚠️ Qiyin mavzu: Base Case (Asosiy holat)ning muhimligi

Simple Explanation

Har bir rekursiv function — majburiy ravishda "to'xtash shartiga" (base case) ega bo'lishi kerak, aks holda u abadiy o'zini chaqiraveradi.

Muammoli misol — Base Case'siz rekursiya

script.js
JavaScriptNusxalash
01function badFactorial(n) {
02    return n * badFactorial(n - 1); // base case YO'Q!
03}
04 
05badFactorial(5); // ❌ "Maximum call stack size exceeded"

Nima uchun bunday bo'ladi? Bu — Chapter 29'da o'rgangan Call Stackning to'lib ketishi (Stack Overflow). Har bir rekursiv chaqiruv — Call Stack'ga yangi "qatlam" qo'shadi (Chapter 29.2). Base case bo'lmagani uchun, function hech qachon returnga yetib bormaydi, va chaqiruvlar cheksiz to'planaveradi, toki brauzer/Node.js xotira chegarasiga yetguncha.

Diagram — Call Stack qanday "to'lib ketadi"

code.text
TEXTNusxalash
01badFactorial(5)
02  badFactorial(4)
03    badFactorial(3)
04      badFactorial(2)
05        badFactorial(1)
06          badFactorial(0)
07            badFactorial(-1)
08              badFactorial(-2)
09                ... (abadiy davom etadi, Stack TO'LIB KETADI)

🔥 Important
Har bir rekursiv function yozishda, birinchi navbatda base caseni aniq belgilash kerak — "qachon rekursiya to'xtashi kerak?" degan savolga javob bermasdan, rekursiv qismni yozmang.

46.3 Recursion vs Loop — qachon qaysi birini ishlatish kerak?

Jadval — Solishtirish

Amaliy misol — Loop bilan yechim

script.js
JavaScriptNusxalash
01function factorialLoop(n) {
02    let result = 1;
03    for (let i = 2; i <= n; i++) {
04        result *= i;
05    }
06    return result;
07}
08 
09console.log(factorialLoop(5)); // 120

Explanation

Oddiy hollarda (masalan, faktorial), loop odatda rekursiyadan tezroq va xotira jihatidan tejamliroq. Lekin ba'zi muammolar (masalan, ichma-ich daraxt tuzilmalarni aylanib chiqish) — rekursiya bilan ancha tabiiy va sodda ifodalanadi.

46.4 ⚠️ Qiyin mavzu: Recursion — Nested (ichma-ich) tuzilmalar bilan

Simple Explanation

Recursion'ning haqiqiy kuchi — chuqurligi oldindan noma'lum bo'lgan ma'lumot tuzilmalari (masalan, ichma-ich object'lar, papka tuzilmalari, DOM daraxti) bilan ishlashda namoyon bo'ladi, bu yerda oddiy loop bilan yechim topish ancha qiyin.

Amaliy misol — Ichma-ich object'ni "tekislash" (flatten)

script.js
JavaScriptNusxalash
01let nestedObject = {
02    name: "Ali",
03    address: {
04        city: "Toshkent",
05        details: {
06            zip: "100000",
07            country: {
08                name: "O'zbekiston"
09            }
10        }
11    }
12};
13 
14function flattenObject(obj, result = {}) {
15    for (let key in obj) {
16        if (typeof obj[key] === "object" && obj[key] !== null) {
17            flattenObject(obj[key], result); // REKURSIV chaqiruv
18        } else {
19            result[key] = obj[key];
20        }
21    }
22    return result;
23}
24 
25console.log(flattenObject(nestedObject));
26// { name: "Ali", city: "Toshkent", zip: "100000", name: "O'zbekiston" }

How It Works

1. flattenObject — har bir key uchun, agar qiymat yana object bo'lsa, o'zini-o'zi shu ichki object bilan qayta chaqiradi.
2. Bu jarayon — object qanchalik chuqur "ichma-ich" bo'lishidan qat'i nazar, avtomatik ravishda eng chuqur qatlamgacha davom etadi.
3. Agar qiymat oddiy (object bo'lmagan) bo'lsa — bu base case, va qiymat to'g'ridan-to'g'ri natijaga qo'shiladi.

💡 Key Idea
Bu misolda, obj[key] object bo'lmasligi — base case vazifasini o'taydi (Chapter 46.2'dagi qoida bilan bir xil tamoyil, faqat bu safar sonlar emas, tuzilma chuqurligi asosida).

Diagram

code.text
TEXTNusxalash
01flattenObject(nestedObject)
02    │
03    ├── name: "Ali" → natijaga qo'shiladi
04    │
05    └── address (object!) → REKURSIYA
06         │
07         ├── city: "Toshkent" → natijaga qo'shiladi
08         │
09         └── details (object!) → REKURSIYA
10              │
11              ├── zip: "100000" → natijaga qo'shiladi
12              │
13              └── country (object!) → REKURSIYA
14                   │
15                   └── name: "O'zbekiston" → natijaga qo'shiladi

🔗 Connection
Bu — Chapter 32'da ko'rgan DOM daraxtini aylanib chiqishning ham asosiy tamoyili: DOM elementlari ham "ichma-ich" tuzilma bo'lgani uchun, ular ustida ishlashda rekursiya juda tabiiy yechim hisoblanadi.

46.5 Recursion bilan Array'larni qayta ishlash

Example — Array yig'indisi (rekursiv)

script.js
JavaScriptNusxalash
01function sumArray(arr) {
02    if (arr.length === 0) {
03        return 0; // Base case
04    }
05    return arr[0] + sumArray(arr.slice(1)); // Recursive case
06}
07 
08console.log(sumArray([1, 2, 3, 4, 5])); // 15

Explanation

Har bir chaqiruvda, array'ning birinchi elementi ajratib olinadi va qolgan qismi (slice(1) — Chapter 7) bilan rekursiv chaqiriladi, toki array bo'sh (length === 0) bo'lguncha.

⚠️ Common Mistake
Katta array'lar uchun bu usul (har safar slice() bilan yangi array yaratish) — samarasiz bo'lishi mumkin, chunki har bir chaqiruv yangi array nusxasini yaratadi. Katta ma'lumotlar uchun, odatda oddiy loop yoki reduce() (Chapter 14) afzalroq.

📝 Practice Exercises

🟢 Exercise 1 — Easy

Task:
countdown(n) nomli rekursiv function yozing — u ndan 1gacha sonlarni konsolga chiqarsin, keyin "Tayyor!" deb yozsin. Base case'ni to'g'ri belgilang.
Required Concepts:

• Base case, recursive case
  Hint:
  if (n === 0) { console.log("Tayyor!"); return; }

🟡 Exercise 2 — Medium

Task:
sumArray(arr) functionini Chapter 46.5'dagi kabi emas, balki index parametri bilan (har safar yangi array yaratmasdan) qayta yozing.
Required Concepts:

• Recursion + index parameter (samaraliroq usul)
  Hint:
  function sumArray(arr, index = 0) { if (index === arr.length) return 0; return arr[index] + sumArray(arr, index + 1); }

🔴 Exercise 3 — Hard

Task:
Ichma-ich array'ni (Chapter 7.6'dagi kabi, lekin bu safar chuqurligi noma'lum) to'liq "tekislaydigan" (flatten) rekursiv function yozing, flat(Infinity)dan foydalanmasdan:

script.js
JavaScriptNusxalash
01let nested = [1, [2, [3, [4, [5]]]]];
02// Natija: [1, 2, 3, 4, 5]

Required Concepts:

• Recursion + Array.isArray()
  Hint:
  Har bir element uchun, agar u array bo'lsa, rekursiv flatten() chaqiring va natijani concat qiling.

🔮 Predict the Output

script.js
JavaScriptNusxalash
01function mystery(n) {
02    if (n <= 0) {
03        return 0;
04    }
05    return n + mystery(n - 1);
06}
07 
08console.log(mystery(4));

🧠 Think first! Javobni ko'rishdan oldin kamida 30 soniya o'ylang.

<details> <summary>Answer</summary> 10

Why?

code.text
TEXTNusxalash
01mystery(4) = 4 + mystery(3)
02           = 4 + (3 + mystery(2))
03           = 4 + (3 + (2 + mystery(1)))
04           = 4 + (3 + (2 + (1 + mystery(0))))
05           = 4 + (3 + (2 + (1 + 0)))
06           = 10

Bu function — 1dan ngacha bo'lgan sonlarning yig'indisini rekursiv tarzda hisoblaydi.

</details>

🐛 Debugging Challenge

Quyidagi kodda muammo bor:

script.js
JavaScriptNusxalash
01function sumUpTo(n) {
02    return n + sumUpTo(n - 1);
03}
04 
05console.log(sumUpTo(5));

Your Task:

• Kod ishga tushganda nima bo'lishini bashorat qiling.
• Nima uchun xatolik yuz berishini tushuntiring.
• Kodni tuzating.

<details> <summary>Solution</summary> Muammo: Bu functionda base case umuman yo'q. n har safar kamayib boradi (5, 4, 3, 2, 1, 0, -1, -2, ...), lekin hech qachon to'xtamaydi, natijada "Maximum call stack size exceeded" xatoligiga olib keladi.

Yechim:

script.js
JavaScriptNusxalash
01function sumUpTo(n) {
02    if (n <= 0) {
03        return 0; // BASE CASE
04    }
05    return n + sumUpTo(n - 1);
06}
07 
08console.log(sumUpTo(5)); // 15

</details>

📌 Chapter Summary

• Recursion — function o'zini-o'zi chaqirishi, muammoni kichikroq nusxalari orqali hal qilish.
• Har bir rekursiv function — majburiy base case (to'xtash sharti)ga ega bo'lishi kerak.
• Base case'siz rekursiya — Call Stack to'lib ketishiga (Stack Overflow) olib keladi.
• Recursion — ichma-ich (nested) tuzilmalar (object, DOM, papka) bilan ishlashda ayniqsa tabiiy va foydali.
• Oddiy, tekis takrorlash uchun — loop odatda tezroq va xotira jihatidan tejamliroq.

🎯 Key Takeaways

• Har doim avval base case'ni aniqlang, keyin rekursiv qismni yozing.
• Recursion — Chapter 29'dagi Call Stack mexanizmiga to'g'ridan-to'g'ri bog'liq: har chaqiruv — yangi "qatlam".
• Ichma-ich tuzilmalar (object, array, DOM) uchun recursion — ko'pincha loop'dan tabiiyroq yechim.
• Katta ma'lumotlar uchun, recursion'ning xotira va tezlik narxini hisobga oling.
• "Bo'l va hukmronlik qil" (divide and conquer) tamoyiliga asoslangan algoritmlar — deyarli har doim recursion orqali yoziladi.

⚡ Quick Cheat Sheet

script.js
JavaScriptNusxalash
01function recursiveFunc(n) {
02    if (/* base case shart */) {
03        return /* asosiy natija */;
04    }
05    return /* n bilan bog'liq amal */ + recursiveFunc(/* kichikroq qiymat */);
06}
07 
08// Nested tuzilma uchun
09function traverse(obj) {
10    for (let key in obj) {
11        if (typeof obj[key] === "object") {
12            traverse(obj[key]); // rekursiya
13        } else {
14            // ishlov berish
15        }
16    }
17}

---