20-dars

Recursion

Recursion — funksiya o'zini o'zi chaqirishi.

Lekin bu ta'rif yetarli emas. Asosiy savol — qachon va nima uchun o'zini chaqiradi, va bu qanday to'xtaydi.

---

Recursion ning ikki sharti

Har qanday to'g'ri yozilgan recursive funksiyada ikki qism bo'lishi shart:

1. Base case — to'xtash sharti (bu bo'lmasa, cheksiz loop)
2. Recursive case — o'zini chaqirish, lekin kichikroq muammo bilan

Agar base case bo'lmasa:

function infinite() {
  return infinite(); // base case yo'q
}

infinite(); // RangeError: Maximum call stack size exceeded

---

Eng oddiy misol — Factorial

Matematik ta'rif:

5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 4 × 3 × 2 × 1 = 24
1! = 1
0! = 1

Recursive ta'rif:

factorial(n) = n × factorial(n - 1)
factorial(0) = 1  ← base case

Kod:

function factorial(n) {
  if (n === 0) return 1;          // base case
  return n * factorial(n - 1);    // recursive case
}

factorial(5); // 120

---

Call Stack da nima bo'ladi — step by step

factorial(5) chaqirilganda Call Stack qanday o'zgarishini ko'ramiz.

Qurilish bosqichi — har bir chaqiruv stack ga qo'shiladi:

factorial(5) chaqirildi → stack ga qo'shildi
  5 === 0? → yo'q → 5 * factorial(4) kerak

factorial(4) chaqirildi → stack ga qo'shildi
  4 === 0? → yo'q → 4 * factorial(3) kerak

factorial(3) chaqirildi → stack ga qo'shildi
  3 === 0? → yo'q → 3 * factorial(2) kerak

factorial(2) chaqirildi → stack ga qo'shildi
  2 === 0? → yo'q → 2 * factorial(1) kerak

factorial(1) chaqirildi → stack ga qo'shildi
  1 === 0? → yo'q → 1 * factorial(0) kerak

factorial(0) chaqirildi → stack ga qo'shildi
  0 === 0? → HA → 1 qaytaradi ← BASE CASE, to'xtadi

Stack eng yuqori nuqtada:

┌─────────────────┐
│  factorial(0)   │  ← 1 qaytaradi
├─────────────────┤
│  factorial(1)   │  ← 1 * ? kutmoqda
├─────────────────┤
│  factorial(2)   │  ← 2 * ? kutmoqda
├─────────────────┤
│  factorial(3)   │  ← 3 * ? kutmoqda
├─────────────────┤
│  factorial(4)   │  ← 4 * ? kutmoqda
├─────────────────┤
│  factorial(5)   │  ← 5 * ? kutmoqda
├─────────────────┤
│     Global      │
└─────────────────┘

Yechilish bosqichi — stack yuqoridan pastga yechiladi:

factorial(0) → 1 qaytardi, stack dan chiqdi
factorial(1) → 1 * 1 = 1 qaytardi, stack dan chiqdi
factorial(2) → 2 * 1 = 2 qaytardi, stack dan chiqdi
factorial(3) → 3 * 2 = 6 qaytardi, stack dan chiqdi
factorial(4) → 4 * 6 = 24 qaytardi, stack dan chiqdi
factorial(5) → 5 * 24 = 120 qaytardi, stack dan chiqdi

Muhim tushuncha: Har bir factorial chaqiruvi o'zining alohida Execution Context iga ega — alohida n qiymati bilan. Ular bir-birining n ini bilmaydi, stack da alohida-alohida turadi.

---

Stack Overflow — qachon bo'ladi

V8 da Call Stack o'lchami cheklangan — taxminan 10,000—15,000 frame (brauzer va versiyaga qarab farq qiladi).

factorial(100000); // RangeError: Maximum call stack size exceeded

Har bir factorial chaqiruvi stack da bitta frame egallaydi. 100,000 frame — stack sig'imidan oshib ketadi.

---

Recursion vs Loop — qaysi birini tanlash

// Loop bilan:
function factorialLoop(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

// Recursion bilan:
function factorialRecursive(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

Loop — bitta Execution Context, i o'zgarib boradi. Stack da faqat bitta frame. Recursion — har chaqiruvda yangi Execution Context. n ta frame stack da to'planadi.

Shuning uchun katta n uchun loop tezroq va xavfsizroq.

---

Recursion qachon loopdan yaxshiroq

Recursion ma'nosi bor — muammo o'z-o'ziga o'xshash kichik qismlarga bo'linsa. Buni "self-similar structure" deyiladi.

Eng yaxshi misol — daraxt (tree) strukturasi:

const fileSystem = {
  name: 'root',
  children: [
    {
      name: 'src',
      children: [
        { name: 'index.js', children: [] },
        { name: 'app.js',   children: [] }
      ]
    },
    {
      name: 'public',
      children: [
        { name: 'index.html', children: [] }
      ]
    }
  ]
};

Bu strukturani loop bilan bosib chiqish — juda murakkab (qancha chuqurlik borligini bilmaysiz). Recursion bilan — oddiy:

function printTree(node, depth = 0) {
  const indent = '  '.repeat(depth);
  console.log(`${indent}${node.name}`);

  for (const child of node.children) {
    printTree(child, depth + 1); // kichikroq muammo — bitta child
  }
}

printTree(fileSystem);
// root
//   src
//     index.js
//     app.js
//   public
//     index.html

Loop bilan yozsangiz — stack ni qo'lda boshqarishingiz kerak bo'ladi. Recursion bu ishni avtomatik qiladi — Call Stack aynan shu uchun.

---

Amaliy misollar

1. Sonlar yig'indisi

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

sum(5); // 5 + 4 + 3 + 2 + 1 + 0 = 15

2. Massiv elementlarini tekshirish

function includes(arr, target, index = 0) {
  if (index === arr.length) return false;  // base case — oxiriga yetdi
  if (arr[index] === target) return true;  // base case — topdi
  return includes(arr, target, index + 1); // recursive case
}

includes([1, 2, 3, 4, 5], 3); // true
includes([1, 2, 3, 4, 5], 9); // false

3. Chuqur (nested) obyektdan qiymat topish

const data = {
  a: {
    b: {
      c: {
        value: 42
      }
    }
  }
};

function deepGet(obj, keys) {
  if (keys.length === 0) return obj;              // base case
  const [first, ...rest] = keys;
  if (obj[first] === undefined) return undefined;
  return deepGet(obj[first], rest);                // recursive case
}

deepGet(data, ['a', 'b', 'c', 'value']); // 42

Loop bilan bu — keys ning qancha chuqur ekanini bilmasdan yozish qiyin. Recursion bilan — har qadamda bitta kalit, qolganini o'ziga topshiradi.

---

Tail Call — stack ni tejash

Tail Call — recursive chaqiruv funksiyaning oxirgi ishi bo'lsa:

// Oddiy recursion — tail call EMAS:
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1); // ← factorial qaytgandan keyin ko'paytirish bor
}                               //   demak bu "oxirgi ish" emas

// Tail Call Optimization (TCO) uchun — accumulator bilan:
function factorial(n, acc = 1) {
  if (n === 0) return acc;            // base case
  return factorial(n - 1, n * acc);   // ← bu OXIRGI ish, keyin hech narsa yo'q
}

Farq nima?

Oddiy recursion da — factorial(4) ning javobi kelmaguncha, factorial(5) ning frame i stack da kutib turishi kerak (chunki 5 * ? hisoblash uchun javob kerak).

Tail Call da — factorial(5, 1) factorial(4, 5) ni chaqirgach, o'z frame ini tashlab ketishi mumkin — chunki qaytib kelganda qiladigan ishi yo'q, natija to'g'ridan-to'g'ri yuqoriga uzatiladi.

Oddiy:   factorial(5) → factorial(4) → factorial(3) → ... (hammasi kutmoqda)
TCO:     factorial(5,1) → factorial(4,5) → factorial(3,20) → ... (oldingi frame o'chadi)

V8 da TCO haqiqati: V8 TCO ni to'liq implement qilmagan — faqat strict mode da, cheklangan hollarda ishlaydi. Shuning uchun amalda katta sonlar bilan hali ham Stack Overflow bo'lishi mumkin. Lekin konseptual jihatdan bilish muhim — boshqa tillar (Haskell, Erlang, Elixir) TCO ni to'liq qo'llab-quvvatlaydi.