Asosiy rekursiya

Umumiy ma'lumot

Rekursiya — bu funksiyaning bir xil masalaning kichikroq versiyasini yechish uchun o'zini qayta-qayta chaqirishi, masala to'g'ridan-to'g'ri javob berish uchun yetarlicha kichik bo'lguncha davom etadi. Har bir rekursiv funksiyaga ikkita qism kerak:

• Bazaviy holat (base case) — eng sodda kirish, bu yerda siz to'xtaysiz va o'zingizni yana chaqirmasdan javob qaytarasiz.
• Rekursiv holat (recursive case) — bu yerda siz funksiyani kichikroq kirish bilan chaqirasiz va uning natijasi ustiga quraiz.

Bazaviy holatni o'tkazib yuborsangiz, funksiya o'zini abadiy chaqiradi va bu qulashga olib keladi. Shuning uchun har doim bazaviy holatni birinchi yozing.

1-misol: teskari sanoq (countdown)

function countdown(n) {
  if (n <= 0) {        // base case: stop here
    console.log("Done!");
    return;
  }
  console.log(n);
  countdown(n - 1);    // recursive case: smaller problem
}
 
countdown(3); // 3, 2, 1, Done!

Har bir chaqiruv bitta sonni qayta ishlaydi, so'ng qolganini (n - 1) boshqa chaqiruvga uzatadi. Bazaviy holat (n <= 0) uning oxir-oqibat to'xtashini kafolatlaydi.

2-misol: massiv yig'indisi

Ro'yxatni yig'ish uchun birinchi elementni oling va uni qolganlarining yig'indisiga qo'shing. Bazaviy holat — bo'sh ro'yxat, uning yig'indisi 0.

function sumArray(list) {
  if (list.length === 0) return 0;      // base case
  const [first, ...rest] = list;        // first item + everything else
  return first + sumArray(rest);        // recursive case
}
 
sumArray([2, 4, 6]); // 12

Uni yuqoridan pastga o'qing: sumArray([2,4,6]) bu 2 + sumArray([4,6]), bu esa 2 + (4 + sumArray([6])), va hokazo, bo'sh ro'yxat 0 qaytarguncha.

3-misol: faktorial

n faktoriali (n! deb yoziladi) n dan 1 gacha bo'lgan barcha butun sonlarni ko'paytiradi. 0! 1 ga teng deb belgilangan — bu bazaviy holat.

function factorial(n) {
  if (n <= 1) return 1;         // base case
  return n * factorial(n - 1);  // recursive case
}
 
factorial(4); // 24  (4 * 3 * 2 * 1)

Stek haqida qisqacha

Har bir tugallanmagan chaqiruv call stack (chaqiruvlar steki)da kutadi — bu to'xtatilgan funksiya chaqiruvlarining uyumi bo'lib, ularning har biri o'zi qayerda bo'lganini eslab qoladi. Bazaviy holat qaytganda, chaqiruvlar birma-bir tugaydi va uyum yechiladi. Agar rekursiya juda chuqurlashsa (aytaylik, o'n minglab chaqiruvlar), stek to'lib qoladi va siz "stack overflow" xatosini olasiz. Bu kabi kichik kirishlar uchun bundan tashvishlanmasa ham bo'ladi.

Har qanday rekursiv narsani sikl (loop) bilan ham yozish mumkin; rekursiya shunchaki o'zining kichikroq nusxalariga bo'linadigan masalalar uchun ko'pincha tabiiyroq o'qiladi (masalan, daraxtlar).

Suhbat maslahatlari

• Har doim bazaviy holatni birinchi ayting — aynan u rekursiyani to'xtatadi va cheksiz siklning oldini oladi.
• Kichik misolni ovoz chiqarib tahlil qiling (masalan, factorial(3)), chaqiruvlar qanday uyumga to'planishi va keyin yechilishini ko'rsatish uchun.
• Chuqur rekursiya call stackni to'ldirib yuborishi mumkinligini va chuqurlik tashvishga solganda sikl alternativa ekanligini eslatib o'ting.