Funksiyalar bilan chuqur ishlash

Rekursiya va stek

Rekursiya — bu masalani o'ziga o'xshash, ammo soddaroq qism-masalalarga bo'lib yechish uslubi. Bunda funksiya o'zini o'zi chaqiradi. Bu dasturlashning eng go'zal va kuchli g'oyalaridan biri.

Rekursiya g'oyasi

Funksiya boshqa funksiyani chaqirishi mumkin. Agar funksiya o'zini o'zi chaqirsa — bu rekursiya deb ataladi.

Rekursiyaning asosiy g'oyasi shunda: katta masalani biroz kichraytiramiz va o'sha kichik masalani o'sha funksiyaning o'zi orqali yechamiz. Bu jarayon masala shu qadar kichrayguncha davom etadiki, oxir-oqibat javob to'g'ridan-to'g'ri ma'lum bo'lib qoladi.

Demak, har qanday rekursiv funksiyada ikkita holat bo'ladi:

Asos (baza) holati — masala shu qadar sodda bo'ladiki, javobni darhol qaytaramiz. Bu rekursiyani to'xtatadigan holat;
Rekursiv holat — masalani kichraytirib, funksiyaning o'zini yana chaqiramiz.

Agar asos holatini unutib qo'ysangiz yoki masala hech qachon kichraymasa, funksiya o'zini cheksiz chaqiraveradi va dastur xatolik bilan to'xtaydi (RangeError: Maximum call stack size exceeded).

Birinchi misol: daraja (pow)

x sonini n-darajaga ko'taruvchi funksiya yozamiz, ya'ni xni o'zini n marta ko'paytiramiz. Buni ikki xil ko'rish mumkin.

Iterativ (takroriy) yo'l — oddiy for sikli bilan:

pow-iter.js

// natija shu yerda chiqadi

Rekursiv yo'l — masalani soddalashtiramiz. E'tibor bering: pow(x, n) ni x * pow(x, n-1) shaklida yozish mumkin:

pow-rec.js

// natija shu yerda chiqadi

pow(2, 3) chaqirilganda ijro quyidagicha "pastga tushadi" va so'ng "yuqoriga qaytadi":

pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2 (asos holati, rekursiya to'xtaydi)
Endi orqaga qaytamiz: 2 * 2 = 4, so'ng 2 * 4 = 8.

Rekursiv yechim ko'pincha qisqaroq va tushunarliroq bo'ladi. Iterativ yechim esa odatda tezroq va kamroq xotira sarflaydi. Har ikkisini bilish foydali.

Ijro steki (execution stack)

Har bir funksiya chaqirilganda, uning ichki ma'lumotlari — o'zgaruvchilari, argumentlari va hozir ijro qilinayotgan qatorning o'rni — maxsus ichki tuzilmada saqlanadi. Bu tuzilma ijro steki (execution context stack) deb ataladi.

Har bir chaqiruv uchun alohida ijro konteksti (execution context) yaratiladi va u stekning ustiga qo'yiladi. Funksiya boshqa funksiyani chaqirsa:

Joriy funksiyaning ijrosi pauza qilinadi;
Uning konteksti stekda saqlanib turadi;
Yangi chaqiruv uchun yangi kontekst stek ustiga qo'yiladi;
Yangi chaqiruv tugagach, uning konteksti stekdan olib tashlanadi va pauza qilingan kontekst davom etadi.

pow(2, 3) uchun stek eng chuqur nuqtada uchta kontekstni saqlaydi: pow(2,3), pow(2,2) va pow(2,1). Asos holatiga yetgach, ular birma-bir stekdan tozalanib boradi.

Rekursiyaning chuqurligi (bir vaqtning o'zida stekdagi kontekstlar soni) cheklangan. JavaScript dvigatellari odatda o'n minglab chuqurlikni ko'taradi, undan ortiq bo'lsa xatolik chiqadi. Juda chuqur rekursiya kerak bo'lsa, uni sikl (iteratsiya)ga aylantirish afzal.

Ikkinchi misol: faktorial

Faktorial n! — 1 dan n gacha bo'lgan sonlarning ko'paytmasi: n! = 1 * 2 * 3 * ... * n. Uni rekursiv shaklda juda chiroyli yozish mumkin, chunki n! = n * (n-1)!:

factorial.js

// natija shu yerda chiqadi

Bu yerda asos holati n == 0 bo'lib, 1 qaytaradi (matematikada 0! = 1). Qolgan barcha holatlar rekursiv ravishda soddalashadi.

Rekursiv funksiyani yozayotganda avval o'zingizdan so'rang: "Qachon to'xtayman?" (asos holati) va "Masalani qanday kichraytiraman?" (rekursiv holat). Shu ikki savolga javob topsangiz, funksiya deyarli tayyor.

Uchinchi misol: Fibonachchi sonlari

Fibonachchi ketma-ketligi 0 va 1 dan boshlanadi, keyingi har bir son avvalgi ikkitasining yig'indisiga teng: 0, 1, 1, 2, 3, 5, 8, 13, .... Ta'rifning o'zi rekursiv: F(n) = F(n-1) + F(n-2).

fib.js

// natija shu yerda chiqadi

Bu "sof" rekursiv Fibonachchi juda sekin: fib(n) bir xil qiymatlarni ko'p marta qayta hisoblaydi. Masalan fib(35) allaqachon sezilarli sekinlashadi. Amalda buni sikl yoki eslab qolish (memoization) bilan tezlashtiradilar. Ammo o'rganish uchun bu misol rekursiyaning tabiatini juda yaxshi ko'rsatadi.

Tezroq, iterativ variant esa oddiy siklda ishlaydi:

fib-iter.js

// natija shu yerda chiqadi

Rekursiv ma'lumot tuzilmalari

Rekursiya faqat funksiyalarga xos emas. Ba'zi ma'lumot tuzilmalari ham rekursiv tabiatga ega — ular o'z ichida o'ziga o'xshash qismlarni saqlaydi.

Bo'linmaydigan (nested) obyektlar — masalan kompaniya bo'limlari, ularning ichida yana ichki bo'limlar bor;
Daraxt (tree) — HTML hujjatning DOM tuzilmasi, fayl tizimidagi papkalar;
Bog'langan ro'yxat (linked list) — har bir element keyingi elementga ishora qiladi.

Bunday tuzilmalarni rekursiv funksiya bilan qayta ishlash juda tabiiy. Misol uchun, ichma-ich joylashgan bo'limlardagi umumiy maoshni sanaymiz:

company.js

// natija shu yerda chiqadi

E'tibor bering: funksiya massivga duch kelsa (asos holati) — to'g'ridan-to'g'ri yig'indini qaytaradi. Obyektga duch kelsa (rekursiv holat) — har bir ichki qismi uchun o'zini qayta chaqiradi. Tuzilma qanchalik chuqur bo'lsa ham, kod o'zgarmaydi.

Xulosa

Rekursiya — funksiyaning o'zini o'zi chaqirishi orqali masalani soddaroq qism-masalalarga bo'lib yechish;
Har bir rekursiv funksiyada asos holati (to'xtash) va rekursiv holat (kichraytirish) bo'lishi shart;
Har bir chaqiruv ijro steki da yangi kontekst yaratadi; chuqurlik cheklangan;
Rekursiv yechim ko'pincha qisqa va tushunarli, iterativ yechim esa odatda tezroq;
Daraxt, ichma-ich obyektlar kabi rekursiv tuzilmalar rekursiya bilan tabiiy qayta ishlanadi.