Recursion — o'z-o'zini chaqirish

~20 daq · JavaScript · Funksiyalar chuqurroq

Muammodan boshlaylik

Papka ichida papkalar bor, ular ichida yana papkalar. Necha qavat chuqur ekanini bilmaysiz. Barcha fayllarni topish kerak.

Sikl bilan yozish qiyin — necha marta ichiga kirish kerakligini bilmaymiz. Recursion bu muammoni tabiiy hal qiladi.

Recursion nima?

Recursion — funksiyaning o'z-o'zini chaqirishi. Muammo kichik qismlarga bo'linadi — har bir qism xuddi shu funksiya bilan hal qilinadi.

Har bir rekursiv funksiyada ikkita narsa bo'lishi shart:

1. Base case — to'xtash sharti. Bo'lmasa — cheksiz chaqiruv.
2. Recursive case — o'zini kichikroq muammo bilan chaqirish.

function sanash(n) {
  if (n <= 0) return; // ← base case: to'xtash
  console.log(n);
  sanash(n - 1);      // ← recursive case: kichikroq muammo
}

sanash(3);
// 3
// 2
// 1

Hayotiy o'xshatma

Oynalar zali — ikki tomonda katta oynalar. Oynaga qaraganda — o'zingizni ko'rasiz, lekin orqangizda yana o'zingiz, undan keyin yana... Bu cheksiz davom etadi. Recursion ham shunday — funksiya o'zini ko'radi, lekin har safar kichikroq.

Farqi — rekursiv funksiyada to'xtash sharti bor. Oynalar zali esa cheksiz — "stack overflow".

Klassik misol — faktorial

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

Rekursiv ta'rif: n! = n × (n-1)!

function faktorial(n) {
  if (n <= 1) return 1;        // ← base case
  return n * faktorial(n - 1); // ← recursive case
}

faktorial(5);
// 5 * faktorial(4)
// 5 * 4 * faktorial(3)
// 5 * 4 * 3 * faktorial(2)
// 5 * 4 * 3 * 2 * faktorial(1)
// 5 * 4 * 3 * 2 * 1 = 120

Nima uchun shunday?

Nima uchun base case shart?

Base case bo'lmasa — funksiya cheksiz o'zini chaqiradi. Call stack to'lib ketadi:

function cheksiz(n) {
  return cheksiz(n - 1); // ← base case yo'q!
}
cheksiz(5); // ❌ RangeError: Maximum call stack size exceeded

Call stack — funksiya chaqiruvlari saqlanadigan joy. Har chaqiruv joy oladi. Cheksiz chaqiruv — joy tugaydi.

Recursion vs Sikl — qachon qaysi?

Sikl — oddiy takrorlash uchun tezroq va xotira tejamkor. Recursion — daraxt tuzilishi (papkalar, DOM, JSON) bilan ishlashda tabiiyroq.

// Faktorial — siklda ham oson
function faktorial(n) {
  let natija = 1;
  for (let i = 2; i <= n; i++) natija *= i;
  return natija;
}
// Bu holda sikl yaxshiroq — oddiyroq, tezroq

Daraxt tuzilishi — recursion kuchi

Ichma-ich ob'ektni tekislash (flatten):

const daraxt = {
  qiymat: 1,
  bolalar: [
    { qiymat: 2, bolalar: [] },
    {
      qiymat: 3,
      bolalar: [
        { qiymat: 4, bolalar: [] },
        { qiymat: 5, bolalar: [] },
      ]
    }
  ]
};

function qiymatlarni_ol(tugun) {
  const natija = [tugun.qiymat]; // ← joriy tugun qiymati

  for (const bola of tugun.bolalar) {
    natija.push(...qiymatlarni_ol(bola)); // ← har bola uchun rekursiya
  }

  return natija;
}

qiymatlarni_ol(daraxt); // [1, 2, 3, 4, 5]

Sikllar bilan bu kodni yozish ancha murakkab bo'lardi.

Fibonacci

0, 1, 1, 2, 3, 5, 8, 13, 21... — har son oldingi ikkitasining yig'indisi.

function fibonacci(n) {
  if (n <= 1) return n;                          // ← base case
  return fibonacci(n - 1) + fibonacci(n - 2);   // ← recursive case
}

fibonacci(6); // 8

Lekin bu juda sekin — bir xil qiymatlar qayta-qayta hisoblanadi. fibonacci(30) — millionlab chaqiruv.

Yechim — memoization:

function fibonacci(n, kesh = {}) {
  if (n <= 1) return n;
  if (kesh[n]) return kesh[n];          // ← keshdan qaytaradi

  kesh[n] = fibonacci(n - 1, kesh) + fibonacci(n - 2, kesh); // ← keshga saqlaydi
  return kesh[n];
}

fibonacci(50); // tez ishlaydi

Tez-tez uchraydigan xatolar

Base case yo'q yoki noto'g'ri:

function sanash(n) {
  console.log(n);
  sanash(n - 1); // ❌ base case yo'q — cheksiz
}

function sanash(n) {
  if (n === 0) return; // ✅ lekin n manfiy bo'lsa?
  console.log(n);
  sanash(n - 1);
}

function sanash(n) {
  if (n <= 0) return; // ✅ manfiy sonlar uchun ham xavfsiz
  console.log(n);
  sanash(n - 1);
}

Katta n bilan stack overflow:

faktorial(100000); // ❌ RangeError — call stack to'lib ketadi

Juda katta n uchun — sikl yoki tail recursion (JavaScript da to'liq qo'llab-quvvatlanmaydi).

Fibonacci ni memoizationsiz ishlatish:

fibonacci(40); // ❌ juda sekin — milliardlab chaqiruv
fibonacci(40, {}); // ✅ memoization bilan tez

Xulosa

Recursion — funksiyaning o'z-o'zini chaqirishi. Har bir rekursiv funksiyada base case (to'xtash) va recursive case (kichikroq muammo) bo'lishi shart.

Recursion — daraxt tuzilishi, ichma-ich ma'lumotlar uchun tabiiy. Oddiy takrorlash uchun sikl yaxshiroq.

Fibonacci kabi takrorlanadigan hisoblashlarda — memoization ishlatiladi.

Keyingi dars

16-dars: IIFE — Immediately Invoked Function Expression