Rekursiv fikrlash: masalani o'zining kichik nusxasi orqali yechish

Qisqacha: Rekursiv fikrlash — masalani "o'zining kichikroq nusxasi + ozgina ish" deb ko'rish. Uchta savolga javob bering: eng kichik holatda javob nima, masala qanday kichrayadi va kichik javoblardan kattasi qanday yig'iladi. Keyin ishonch sakrashi: rekursiv chaqiruv kichik masalani to'g'ri yechadi deb ishoning va ichini kuzatmang. Ichma-ich ma'lumot (menyu turkumlari, papkalar, JSON) uchun bu eng tabiiy yo'l. Lekin JavaScript'da chuqur rekursiya stekni to'ldiradi va tail call optimallashtirish yo'q — chuqurligi noma'lum ma'lumotda rekursiyani o'z stekingiz bilan siklga aylantiring.

Bu darsda

• Masalani rekursiv ta'riflash uchun uch savol retseptidan foydalana olasiz.
• "Ishonch sakrashi" bilan rekursiv funksiyani butun stekni kuzatmasdan yoza olasiz.
• Rekursiya daraxtini chizib, chaqiruvlar soni va chuqurlikni baholay olasiz.
• Rekursiyani massiv-stek bilan siklga aylantira olasiz va qachon bunday qilish kerakligini bilasiz.

Oldin bilishingiz kerak: Rekursiya asoslari, Stack (LIFO), Xotira murakkabligi va amortizatsiya, Kodning murakkabligini hisoblash.

1. Nega bu kerak?

«Bahor» menyusi o'sdi. Endi u oddiy ro'yxat emas — turkumlar ichida turkumlar: "Milliy taomlar" ichida "Sho'rvalar", "Ichimliklar" ichida "Sovuq ichimliklar". Ilovada menyu ichma-ich obyekt bo'lib keladi. Jasur aka so'radi: "Menyuda jami nechta taom bor?"

Sardor ikki qavatli sikl yozdi: turkumlar bo'ylab, keyin har turkumning ichki turkumlari bo'ylab. Ishladi. Bir oydan keyin "Sho'rvalar" ichiga "Go'shtli" va "Sabzavotli" qo'shildi — uchinchi qavat. Hisob noto'g'ri chiqdi. Sardor uchinchi sikl qo'shdi. Keyin to'rtinchisi kerak bo'ldi...

Muammo shundaki, qavatlar soni oldindan noma'lum. Har qavat uchun sikl yozib bo'lmaydi. Lekin har qavatda bir xil ish bajariladi: o'z taomlarini sanash va ichki turkumlarni sanash. Bu — rekursiyaning belgisi.

Rekursiya asoslari darsida funksiya o'zini chaqirishini, to'xtash shartini va stekni ko'rgan edik. U yerda asosiy savol "rekursiya qanday ishlaydi?" edi. Bugungi savol boshqa: rekursiv yechimni qanday o'ylab topish kerak?

2. Rekursiv ta'rif

2.1 O'zi orqali ta'riflash

Ba'zi narsalarni o'zi orqali ta'riflash eng qulay. Sovg'a qutisini tasavvur qiling: ichida yana quti, uning ichida yana quti... Eng ichkarisida — sovg'a. "Qutini ochish" degani: qopqog'ini ko'tar; ichida quti bo'lsa — uni ham och; sovg'a bo'lsa — ol. Ta'rifda "och" so'zi o'zi qatnashdi, lekin aylanib qolmaydi: har safar quti kichikroq, oxiri sovg'a chiqadi.

Menyu turkumi ham shunday ta'riflanadi:

Turkumdagi taomlar soni = uning o'z taomlari soni + har bir ichki turkumdagi taomlar soni.

Ta'rifda "turkumdagi taomlar soni" ikki marta uchradi — chapda va o'ngda. Bu — rekursiv ta'rif (recursive definition). U aylanib qolmaydi, chunki o'ngdagi turkumlar chapdagidan kichikroq (bir qavat ichkarida), va ichki turkumi yo'q turkumda ta'rif o'z-o'zidan to'xtaydi.

2.2 Uch savol retsepti

Har qanday rekursiv yechim uchta savolga javobdan yig'iladi:

1. Eng kichik holat (base case) — qaysi kirishda javob rekursiyasiz, darhol ma'lum? Menyuda: ichki turkumi yo'q turkum — javob o'z taomlari soni.
2. Kichikroq nusxa — masalani qanday qilib xuddi shunday, lekin kichikroq masala(lar)ga keltiramiz? Menyuda: har ichki turkum — kichikroq menyu.
3. Yig'ish — kichik javoblardan kattasini qanday hosil qilamiz? Menyuda: o'z taomlari + ichki javoblar yig'indisi.

Retseptni oddiy misolda sinaymiz — sonning raqamlari yig'indisi (4096 → 4 + 0 + 9 + 6 = 19):

1. Eng kichik holat: bitta raqamli son (n < 10) — javob sonning o'zi.
2. Kichikroq nusxa: oxirgi raqamsiz son — Math.floor(n / 10) (4096 → 409).
3. Yig'ish: oxirgi raqam (n % 10) + kichik sonning raqamlari yig'indisi.

function sumDigits(n) {
  if (n < 10) return n; // bitta raqam — javob o'zi
  return (n % 10) + sumDigits(Math.floor(n / 10));
}
console.log(sumDigits(4096)); // 19

Kod uch javobni deyarli so'zma-so'z takrorlaydi. Rekursiv kod yozishning siri shu: avval uch savolga so'z bilan javob bering, keyin ularni kodga ko'chiring.

2.3 Ishonch sakrashi

sumDigits(4096) ni yozayotganda sumDigits(409) qanday ishlashini o'ylash shart emas. Faqat bitta narsaga ishonasiz: "sumDigits 409 uchun to'g'ri javob — 13 — qaytaradi". Shunda 4096 uchun javob: 6 + 13 = 19.

Bu ishonch sakrashi (leap of faith): rekursiv chaqiruvni allaqachon yozilgan va ishlaydigan funksiya deb qabul qilish.

«Bahor»dan o'xshatish. Jasur aka oshxonadagi taomlar sonini bilmoqchi. U har bo'lim boshlig'idan so'raydi: "Sizning bo'limingizda nechta taom bor?" Boshliqlar o'z yordamchilaridan so'raydi, ular — o'zlarinikidan. Jasur aka javoblarni qo'shadi, xolos. U boshliq qanday sanaganini tekshirmaydi — ishonadi. Rekursiv funksiya ham xuddi Jasur aka kabi ishlaydi. Boshlovchilar ko'pincha butun stekni boshda kuzatishga urinadi: "4096 409 ni chaqiradi, u 40 ni, u 4 ni, keyin qaytadi..." Bu kichik misolda ishlaydi, lekin daraxt shaklidagi rekursiyada bosh aylanib qoladi.

Nega ishonish mumkin? Domino toshlarini tasavvur qiling. Ikki narsa rost bo'lsa, hamma tosh yiqiladi: birinchi tosh yiqiladi va har yiqilgan tosh keyingisini yiqitadi. Rekursiyada ham shunday. Eng kichik holat to'g'ri — bu birinchi tosh. Har qadam kichik to'g'ri javobdan katta to'g'ri javob yasaydi — bu "keyingisini yiqitish". Demak, hamma o'lchamda javob to'g'ri. Matematikada bu fikrlash induksiya deyiladi.

Siz faqat ikki narsani tekshirasiz: eng kichik holat to'g'rimi va har chaqiruv haqiqatan kichrayadimi. Qolganini ishonch sakrashi hal qiladi.

Tekshirib ko'ring: power(x, n) — x ning n-darajasi. Eng kichik holat: n = 0, javob 1. Kichikroq nusxa: power(x, n - 1). Yig'ish qanday?

2.4 Retseptni o'zingiz qo'llang

Kassadagi bugungi tushumlar massivda: [35, 28, 30] (ming so'm). Ularning yig'indisini rekursiya bilan topamiz. Uch savolga avval o'zingiz javob berib ko'ring, keyin tekshiring:

1. Eng kichik holat: bo'sh massiv — yig'indi .
2. Kichikroq nusxa: birinchi elementsiz massiv — nums.slice(1).
3. Yig'ish: birinchi element + kichik massivning yig'indisi.

function sumList(nums) {
  if (nums.length === 0) return 0; // bo'sh — yig'indi 0
  return nums[0] + sumList(nums.slice(1));
}
console.log(sumList([35, 28, 30])); // 93
console.log(sumList([])); // 0

Ishonch sakrashi bilan o'qing: sumList([28, 30]) 58 qaytaradi deb hisoblaymiz — unda javob 35 + 58 = 93. Ichkariga kirib, 30 qanday qo'shilganini kuzatish shart emas.

Bo'sh massivni eng kichik holat qilib oldik, bitta elementlisini emas. Nega? Bo'sh massiv ham to'g'ri kirish: bitta elementli holatdan boshlasak, sumList([]) cheksiz chaqiruvga tushardi. Eng kichik holat — eng kichik mumkin bo'lgan kirish bo'lsin.

Maslahat: Bu misol retseptni o'rganish uchun. Amalda yig'indini reduce yoki oddiy sikl bilan hisoblang: slice har chaqiruvda yangi massiv yasaydi va rekursiya stek joyini oladi.

2.5 Yana ikki misol

Daraja va ichma-ich ro'yxatni yassilash. Ikkinchisida buyurtmalar guruhlarga, guruhlar esa yana guruhlarga bo'lingan:

function power(x, n) {
  if (n === 0) return 1; // har qanday son⁰ = 1
  return x * power(x, n - 1); // xⁿ = x · xⁿ⁻¹
}

function flatten(items) {
  const result = [];
  for (const item of items) {
    if (Array.isArray(item)) {
      // ichki ro'yxat — uni ham o'zi yassilasin
      result.push(...flatten(item));
    } else {
      result.push(item);
    }
  }
  return result;
}

console.log(power(2, 10)); // 1024
console.log(flatten([101, [102, [103, 104]], [], 105]));

Konsolda:

1024
[ 101, 102, 103, 104, 105 ]

flatten uchun uch javob: eng kichik holat — massiv bo'lmagan element (o'zini qo'shamiz); kichikroq nusxa — ichki massiv; yig'ish — ichki natijani o'z natijamizga qo'shish. Bo'sh massiv [] alohida holat talab qilmadi: sikl aylanmaydi va bo'sh natija qaytadi. JavaScript'da buning tayyor varianti bor — items.flat(Infinity) (flat va flatMap). Ichini bilish uchun o'zimiz yozdik.

3. Menyu turkumlarini sanash

Endi Sardorning masalasi. Uch javobni kodga ko'chiramiz. Qadamlarda daraxt va stekni kuzating — har tugun yonidagi = son — o'sha turkum qaytargan javob:

Ikki narsaga e'tibor bering. Birinchisi — kod qavatlar sonini bilmaydi. Menyuga o'ninchi qavat qo'shilsa ham, countDishes o'zgarmaydi. Ikkinchisi — "Milliy" o'z hisobini qilayotganda "Sho'rvalar" ichida nima bo'lishi bilan qiziqmadi: faqat javobni oldi. Bu ishonch sakrashining amaldagi ko'rinishi.

4. Rekursiya daraxti

4.1 Daraxtni chizish

Har rekursiv chaqiruv — bitta tugun, u chaqirgan chaqiruvlar — bolalari. Bu rekursiya daraxti (recursion tree). Vizualda u menyuning o'z shaklini takrorladi: har turkum bir marta chaqirildi.

Har doim ham shunday emas. Kodning murakkabligini hisoblash darsidagi fib(5) daraxtini eslang: u yerda ma'lumot bitta son edi, lekin daraxt 15 tugunli bo'ldi va fib(2) uch marta qaytadan hisoblandi. Rekursiya daraxti — ma'lumotning emas, chaqiruvlarning shakli.

4.2 Daraxtdan murakkablik

Daraxtdan ikki narsani o'qiymiz:

• Vaqt = tugunlar soni × har tugundagi ish. countDishes da har turkum bir marta, har birida o'z taomlarini sanash va bolalarini aylanish — jami O(n), bu yerda n — turkumlar soni.
• Xotira = daraxt balandligi (eng uzun shox). Stek bir vaqtda faqat ildizdan joriy tugungacha bo'lgan chaqiruvlarni ushlaydi (Xotira murakkabligi). Vizualda stekda eng ko'pi bilan 3 ta count turdi — daraxt balandligi.

4.3 O'lchov

Rekursiv countDishes ni o'lchadik. Menyu sun'iy yasaldi: n ta turkum, har birida 3 tagacha ichki turkum (balandligi log₃ n atrofida). Usul — benchmarking darsidagidek: har n alohida jarayonda, isitish, 7 o'lchov medianasi:

n ikki baravar — vaqt ham taxminan ikki baravar (shovqin bilan ×1,7 – ×2,6): ikkala usul ham O(n). Tezlikda sezilarli farq yo'q. Ikkinchi ustundagi "stek bilan sikl" — keyingi bo'limda.

5. Rekursiyani siklga aylantirish

5.1 Nega kerak?

Tezlik bir xil bo'lsa, nega aylantirish kerak? Javob — chuqurlik. Menyu kalta, lekin real ma'lumot ba'zan juda chuqur: izohlarga javoblar zanjiri, ichma-ich papkalar, foydalanuvchi yuborgan JSON. Stek esa kichik — Xotira murakkabligi darsida sumTo 9 765 chuqurlikda yiqilgan edi.

Bu usulni Stack (LIFO) darsida sumWithStack bilan ko'rgan edik. Bu yerda uni har qanday rekursiyaga qo'llash mumkin bo'lgan retseptga aylantiramiz.

Rekursiya stekni yashirincha ishlatadi: "hali tugamagan ishlar"ni dvigatel o'zi eslab qoladi. Biz bu eslab qolishni o'zimiz qilsak — massivni stek sifatida ishlatsak — chaqiruvlar steki kerak bo'lmaydi. Massiv uyumda (heap) yashaydi va millionlab elementni ko'taradi.

5.2 Retsept

1. Stekka boshlang'ich ishni soling (ildiz turkum).
2. Stek bo'sh bo'lmaguncha: bitta ishni oling (pop), uni bajaring.
3. Rekursiv chaqiruv o'rniga — kichik ishlarni stekka soling (push).

const cat = (name, dishes, children = []) =>
  ({ name, dishes, children });

function countDishes(category) {
  let total = category.dishes.length;
  for (const child of category.children) {
    total += countDishes(child);
  }
  return total;
}

function countDishesIter(root) {
  let total = 0;
  const stack = [root]; // hali sanalmagan turkumlar
  while (stack.length > 0) {
    const category = stack.pop();
    total += category.dishes.length;
    for (const child of category.children) stack.push(child);
  }
  return total;
}

// 100 000 qavatli "zanjir": har turkum ichida bitta turkum
const root = cat("0", ["osh"]);
let current = root;
for (let i = 1; i < 100000; i++) {
  const next = cat(String(i), ["osh"]);
  current.children.push(next);
  current = next;
}

console.log(countDishesIter(root));
try {
  countDishes(root);
} catch (error) {
  console.log(`${error.name}: ${error.message}`);
}

Konsolda:

100000
RangeError: Maximum call stack size exceeded

Bir xil ma'lumot: sikl 100 000 qavatni sanadi, rekursiya esa stekni to'ldirib yiqildi. RangeError — "diapazon xatosi: chaqiruvlar stekining eng katta o'lchamidan oshib ketildi".

5.3 Tartib farqi

Siklli versiyada turkumlar boshqa tartibda ko'riladi. pop oxirgi qo'shilganini oladi — demak, ichki turkumlar teskari tartibda (avval "Ichimliklar", keyin "Milliy"). Sanash uchun tartib muhim emas, yig'indi bir xil. Agar tartib muhim bo'lsa (masalan, menyuni ekranga chiqarish), bolalarni teskari tartibda soling: stack.push(...category.children.toReversed()). Daraxtlarni turli tartibda aylanishni Daraxt bo'ylab yurish darsida batafsil ko'ramiz.

5.4 Qachon qaysi biri?

Oxirgi qatorga izoh: sanashda har turkum o'z hissasini darhol qo'shdi. Lekin "daraxt balandligi" kabi masalada ota o'z javobini faqat bolalari javob bergandan keyin biladi. Siklda buni qilish uchun stekka "qayerda to'xtaganimiz"ni ham yozish kerak — kod uzayadi. Rekursiya buni bepul beradi.

6. JavaScript'da tail call yo'q

6.1 Tail call nima?

Agar rekursiv chaqiruv funksiyaning eng oxirgi amali bo'lsa (natijasi to'g'ridan-to'g'ri qaytarilsa), u tail call ("dumdagi chaqiruv") deyiladi. Bunday chaqiruvdan keyin joriy funksiyada ish qolmaydi. Demak, dvigatel joriy chaqiruvning stek joyini yangisiga qayta ishlatishi mumkin — rekursiya sikl kabi O(1) xotira oladi. Bu tail call optimallashtirish (TCO) deb ataladi.

sumTo ni shunday qayta yozish mumkin: yig'indini argumentda olib yuramiz.

function sumTo(n, total = 0) {
  if (n === 0) return total;
  return sumTo(n - 1, total + n); // oxirgi amal — chaqiruv
}

console.log(sumTo(1000));
console.log(sumTo(100000));

Konsolda:

500500
RangeError: Maximum call stack size exceeded

6.2 Standartda bor, amalda yo'q

ES2015 standarti strict rejimda tail call'larni optimallashtirishni talab qiladi ("proper tail calls"). Lekin bugun buni faqat Safari'ning dvigateli (JavaScriptCore) bajaradi. V8 (Chrome, Node) uni 2016-yilda bayroq ortida sinab ko'rdi, lekin hech qachon yoqmadi va keyinroq butunlay olib tashladi. Sabablardan biri: optimallashtirilgan chaqiruvlar stek izidan (stack trace) yo'qoladi va xatolarni topish qiyinlashadi. Firefox ham qo'llamaydi.

Amaliy xulosa: JavaScript'da "dumga o'tkazsam, chuqurlik muammosi yo'qoladi" deb ishonmang. Node 24 da tail call ko'rinishidagi sumTo ham oddiy sumTo kabi yiqildi. Chuqurlik muammosini faqat sikl yoki o'z stekingiz hal qiladi. Boshqa tillarda (Scheme, Haskell, Scala'da @tailrec) bu hiyla ishlaydi — shuning uchun internetda ko'p uchraydi.

Tekshirib ko'ring: Quyidagi qatorlardan qaysi biri tail call? (a) return n + sumTo(n - 1); (b) return sumTo(n - 1, total + n); (c) return 1 + count(child);

7. Chegaraviy holatlar

• Bo'sh turkum. dishes: [], children: [] — javob 0. Alohida if kerak emas: uzunlik 0, sikl aylanmaydi.
• Maydon yo'q. Serverdan children siz turkum kelsa — category.children undefined, for...of esa TypeError: category.children is not iterable beradi. Himoya: category.children ?? [].
• Manfiy yoki kasr son. power(2, -1) — n hech qachon 0 ga yetmaydi (−1, −2, …) va stek to'ladi. Eng kichik holat har qanday kirishda yetib boriladimi — tekshiring yoki kirishni cheklang.
• Sikl ma'lumotda. Agar turkum xato bilan o'zini (yoki ota turkumini) ichiga olsa, rekursiya cheksiz aylanadi. Ko'rilgan turkumlarni Set da saqlash — himoya (Graflarda BFS va DFS darsida batafsil).
• Juda chuqur ma'lumot. O'n minglab qavat — rekursiya o'rniga stek bilan sikl.

8. Ko'p uchraydigan xatolar

8.1 Natijani ishlatmaslik

function countDishes(category) {
  let total = category.dishes.length;
  for (const child of category.children) {
    countDishes(child); // natija tashlab yuborildi!
  }
  return total;
}

const menu = {
  dishes: [],
  children: [{ dishes: ["osh", "manti"], children: [] }],
};
console.log(countDishes(menu)); // 0

Xato xabari yo'q, lekin javob noto'g'ri: ichki turkumdagi ikki taom sanalmadi. Rekursiv chaqiruv bajarildi, lekin uning natijasi hech qayerga qo'shilmadi. Bu jim xato — eng xavflisi. Tuzatish: chaqiruv natijasi yig'ishda ishlatilsin: total += countDishes(child).

8.2 To'g'ri kichraymaydigan chaqiruv

sumDigits ichida Math.floor ni unutib, sumDigits(n / 10) yozilsa nima bo'ladi? Son kichrayadi (4096 → 409,6 → 40,96 → 4,096) va 10 dan kichik bo'lganda to'xtaydi. Lekin kasr qismlar ham qo'shiladi: natija 19 emas, 20.656000000000024. Har chaqiruvda kirish nafaqat kichrayishi, balki to'g'ri kichik masalaga aylanishi kerak — bu yerda "oxirgi raqamsiz son". Ikkinchi savolga javobni kodda aynan tekshiring.

8.3 Umumiy massivni buzish

Rekursiv funksiyaga bitta massivni berib, ichida uni o'zgartirsangiz (path.push va pop siz qaytish), turli shoxlar bir-birining ma'lumotini buzadi. Har shox o'z nusxasini olsin yoki o'zgartirishni qaytarib qo'ysin — bu g'oya keyingi darsda backtracking'ning yuragi bo'ladi.

8.4 Bir ishni ko'p marta qilish

fib kabi ikki shoxli rekursiyada bir xil kichik masala qayta-qayta yechiladi — vaqt eksponensial. Daraxtda takroriy tugunlarni ko'rsangiz — natijalarni eslab qoling (Memoization).

9. Mashqlar

1-mashq (oson): Raqamlar yig'indisi

Yuqoridagi sumDigits bilan sumDigits(90071) necha bo'ladi?

2-mashq (o'rta): Teskari satr

reverse(text) ni rekursiv yozing: reverse("osh") → "hso". Avval uch savolga so'z bilan javob bering, keyin kodga o'ting. Ishora: slice satrning bo'lagini qaytaradi.

function reverse(text) {
  if (text.length <= 1) return text;
  return reverse(text.slice(1)) + text[0];
}
console.log(reverse("osh")); // hso
console.log(reverse("").length); // 0

3-mashq (qiyin): Menyu daraxti bilan ishlash

kurs/mashqlar/14/23-rekursiya/menu.test.mjs faylida uchta funksiya yozing:

• maxDepth(category) — menyuning qavatlari soni (faqat ildiz — 1);
• findPath(category, dish) — taom joylashgan turkumlar nomlari ro'yxati (ildizdan boshlab) yoki null;
• maxDepthIter(category) — maxDepth ning stek bilan siklli varianti (stekka [turkum, chuqurlik] juftini soling).

Testlar: darsdagi menyuda chuqurlik 3; "mastava" yo'li ["Menyu", "Milliy", "Sho'rvalar"]; yo'q taom — null; 100 000 qavatli zanjirda maxDepthIter 100 000 qaytaradi (node:test).

// kurs/mashqlar/14/23-rekursiya/menu.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const cat = (name, dishes, children = []) =>
  ({ name, dishes, children });

const menu = cat("Menyu", [], [
  cat("Milliy", ["osh", "manti", "lag'mon"], [
    cat("Sho'rvalar", ["sho'rva", "mastava"]),
  ]),
  cat("Ichimliklar", ["ko'k choy"], [
    cat("Sovuq", ["kompot", "ayron"]),
  ]),
]);

function maxDepth(category) {
  let deepest = 0;
  for (const child of category.children) {
    deepest = Math.max(deepest, maxDepth(child));
  }
  return deepest + 1; // o'zi ham bir qavat
}

function findPath(category, dish) {
  if (category.dishes.includes(dish)) return [category.name];
  for (const child of category.children) {
    const path = findPath(child, dish);
    if (path !== null) return [category.name, ...path];
  }
  return null;
}

function maxDepthIter(root) {
  let deepest = 0;
  const stack = [[root, 1]];
  while (stack.length > 0) {
    const [category, depth] = stack.pop();
    deepest = Math.max(deepest, depth);
    for (const child of category.children) {
      stack.push([child, depth + 1]);
    }
  }
  return deepest;
}

test("menyu chuqurligi — 3", () => {
  assert.equal(maxDepth(menu), 3);
  assert.equal(maxDepthIter(menu), 3);
  assert.equal(maxDepth(cat("Bo'sh", [])), 1);
});

test("mastava yo'li", () => {
  assert.deepEqual(findPath(menu, "mastava"),
    ["Menyu", "Milliy", "Sho'rvalar"]);
});

test("yo'q taom — null", () => {
  assert.equal(findPath(menu, "pitsa"), null);
});

test("100 000 qavat — sikl yiqilmaydi", () => {
  const root = cat("0", []);
  let current = root;
  for (let i = 1; i < 100000; i++) {
    const next = cat(String(i), []);
    current.children.push(next);
    current = next;
  }
  assert.equal(maxDepthIter(root), 100000);
  assert.throws(() => maxDepth(root), RangeError);
});

✔ menyu chuqurligi — 3 (0.765ms)
✔ mastava yo'li (0.6879ms)
✔ yo'q taom — null (0.1097ms)
✔ 100 000 qavat — sikl yiqilmaydi (52.0975ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 144.6849

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga to'rt qator qo'shing: sumDigits, power (sodda), countDishes (rekursiv) va countDishesIter. Xotira ustunida stek yoki massivni aniq ayting.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Raqamlar yig'indisi | rekursiya | O(d), d — raqamlar | O(d) stek |
| Daraja xⁿ | sodda rekursiya | O(n) | O(n) stek |
| Menyu taomlari | rekursiya | O(n) | O(h) stek, h — balandlik |
| Menyu taomlari | stek bilan sikl | O(n) | O(n) massiv eng yomon |

git add 14/MURAKKABLIK.md 14/23-rekursiya
git commit -m "14/23: menyu daraxti — rekursiya va stek bilan sikl"

10. Real ishda

• Ichma-ich ma'lumot hamma joyda. DOM daraxti, papkalar, JSON, izohlarga javoblar, menyu va kategoriyalar, tashkilot tuzilmasi. Ularni aylanishning eng tabiiy yo'li — rekursiya. structuredClone, JSON.stringify kabi o'rnatilgan funksiyalar ham ichma-ich obyektni rekursiv aylanadi.
• Kutubxonalar chuqurlikdan qo'rqadi. Foydalanuvchi yuborgan ma'lumotni aylanadigan kutubxonalar (JSON parserlar, chuqur nusxa olish, solishtirish) ko'pincha o'z stekidan foydalanadi yoki chuqurlikka chegara qo'yadi — juda chuqur JSON bilan serverni yiqitish ham hujum usuli.
• Algoritmlar asosi. Keyingi darslarning ko'pi rekursiv fikrlashga tayanadi: backtracking, bo'lib-yech, merge sort, daraxtlar, graflarda DFS, dinamik dasturlash.
• Intervyu. "Buni rekursiv yozing", keyin "endi rekursiyasiz" — tez-tez so'raladigan juftlik. Uch savol retsepti va stekka aylantirish retsepti ikkalasiga javob beradi.

Xulosa

• Rekursiv ta'rif — masala o'zining kichikroq nusxasi orqali; har safar kichrayadi va eng kichik holatda to'xtaydi.
• Uch savol: eng kichik holat, kichikroq nusxa, yig'ish. Avval so'z bilan, keyin kod.
• Ishonch sakrashi: rekursiv chaqiruv kichik masalani to'g'ri yechadi deb qabul qiling — faqat eng kichik holat va kichrayishni tekshiring.
• Rekursiya daraxti: vaqt — tugunlar soni × har tugundagi ish, xotira — daraxt balandligi.
• Rekursiyani massiv-stek bilan siklga aylantirish mumkin: tezlik bir xil (800 000 turkum ≈ 9–10 ms), lekin 100 000 qavat faqat siklda ishladi.
• JavaScript'da (V8) tail call optimallashtirilmaydi — dumga o'tkazilgan rekursiya ham RangeError beradi.

Keyingi dars: Backtracking asoslari — tanla, chuqurga tush, tanlovni bekor qil: qism-to'plamlar, permutatsiyalar va kombinatsiyalar holat daraxti bilan.

Manbalar

• Harold Abelson, Gerald Jay Sussman, "Structure and Interpretation of Computer Programs", 2-nashr, MIT Press, 1996 — "Procedures and the Processes They Generate" bo'limi (rekursiv va iterativ jarayonlar).
• ECMAScript 2015, 14.6 "Tail Position Calls" — tc39.es/ecma262
• V8 jamoasi, "ES2015, ES2016, and beyond" (2016) — proper tail calls holati — v8.dev/blog/modern-javascript
• MDN: "Too much recursion" / RangeError — developer.mozilla.org