Recursion əsasları
Recursion — funksiyanın məsələni daha kiçik eyni tipli məsələyə ayıraraq özünü çağırmasıdır. Hər düzgün rekursiv funksiyada iki hissə olmalıdır:
- Base case — rekursiyanın dayandığı ən sadə hal (
n == 0,node == null, boş siyahı). Base case yoxdursa və ya heç vaxt çatılmırsa, nəticə stack overflow-dur. - Recursive case — məsələni kiçildib özünü çağırmaq. Hər çağırışda giriş mütləq base case-ə yaxınlaşmalıdır.
Rekursiyanı düşünərkən faydalı zehni model — "inam sıçrayışı": fərz et ki, funksiya n-1 üçün onsuz da düzgün işləyir; sənin işin yalnız o nəticədən n üçün cavabı qurmaqdır. Bütün çağırış ağacını başında canlandırmağa çalışmaq ən çox rast gəlinən çaşqınlıq mənbəyidir.
Rekursiya təbii uyğun gəldiyi yerlər: ağac və qraf gəzintiləri, iç-içə strukturlar (JSON, fayl sistemi, DOM), "böl və hökm sür" alqoritmləri (merge sort, quick sort, binary search), backtracking (permutasiyalar, sudoku, N-Queens).
Call stack necə böyüyür. Hər rekursiv çağırış stack-də yeni frame yaradır və o frame funksiya qayıdana qədər yaşayır. factorial(5) çağırışında beş frame eyni anda stack-də durur; ən dərin çağırış qayıtdıqca frame-lər bir-bir açılır və nəticələr yuxarı ötürülür.
Bundan iki nəticə çıxır:
- Rekursiyanın space complexity-si dərinliyə bərabərdir:
O(d).factorial(n)üçünO(n), balanslı ağacda DFS üçünO(log n), əyilmiş ağacdaO(n). - Stack məhduddur (adətən bir neçə MB, JS-də təxminən 10 000 çağırış dərinliyi). Dərinlik istifadəçi girişindən asılıdırsa, rekursiyaya arxalanmaq risklidir.
Tail recursion — rekursiv çağırışın funksiyadakı son əməliyyat olması (return helper(n - 1, acc * n), return n * helper(n - 1) deyil). Bəzi dillər bunu dövrə çevirib stack-i sabit saxlayır: Kotlin-də tailrec açar sözü ilə. JS mühitlərinin əksəriyyətində və Dart-da isə tail-call optimizasiyası yoxdur — buna arxalanmaq olmaz.
| Meyar | Recursion | Iteration |
|---|---|---|
| Oxunaqlılıq (ağac, iç-içə data) | Çox yüksək — struktur məsələnin formasını təkrarlayır | Aşağı — əl ilə stack saxlamaq lazımdır |
| Oxunaqlılıq (sadə dövr) | Süni görünür | Təbii |
| Yaddaş | O(dərinlik) — call stack | Adətən O(1) |
| Stack overflow riski | Var — dərinlik böyük olanda | Yoxdur |
| Sürət | Bir qədər yavaş — çağırış overhead-i | Bir qədər sürətli |
| Debug etmək | Çətin — dərin stack trace | Asan |
| Nə vaxt seç | Ağac/qraf, backtracking, böl və hökm sür | Xətti gəzinti, dərinlik məlum deyil və ya böyükdür |
Rekursiyanı iterasiyaya çevirmək — iki tipik ssenari var.
- Xətti (tail-şəkilli) rekursiya: siyahını gəzmək, cəm hesablamaq, faktorial. Bunları birbaşa
while/fordövrünə çevirmək olur; toplanan nəticəni akkumulyator dəyişəndə saxlayırsan. YaddaşO(n)-dənO(1)-ə düşür. - Şaxələnən rekursiya: ağac gəzintisi, DFS. Burada call stack-in yerinə açıq stack (massiv və ya
ArrayDeque) qoyulur: node-u stack-ə at, çıxart, emal et, uşaqlarını at. Məntiq eyni qalır, amma yaddaş heap-də olduğu üçün dərinlik limiti praktiki olaraq aradan qalxır.
Memoization ayrı bir təkmilləşdirmədir: eyni alt məsələ təkrar-təkrar hesablanırsa, nəticələri map-də saxla. Klassik nümunə fibonacci-dir: sadə rekursiv variant O(2ⁿ)-dir, çünki fib(30) çağırışında fib(10) minlərlə dəfə hesablanır. Memoization ilə hər n bir dəfə hesablanır — O(n) time, O(n) space. Bu, dinamik proqramlaşdırmanın giriş qapısıdır.
İnterview məsləhəti. Rekursiv həlli izah edərkən üç şeyi ardıcıl de: (1) base case nədir, (2) məsələni necə kiçildirəm, (3) time və space complexity — space-də call stack-i mütləq say. Bu üçlüyü demək müsahibə "bu adam rekursiyanı anlayır" siqnalı verir.
Ən çox verilən sual: "Sadə rekursiv fibonacci-nin mürəkkəbliyi nədir və necə yaxşılaşdırarsan?" Gözlənilən cavab: O(2ⁿ) time / O(n) space (stack dərinliyi), memoization ilə O(n)/O(n), aşağıdan-yuxarı iterativ variantla isə O(n) time / O(1) space. Bu üç pilləni ardıcıl göstərmək çox güclü cavabdır.
Ən çox rast gəlinən səhvlər: base case-i unutmaq və ya səhv qoymaq (n == 1 yazıb n == 0 girişini nəzərə almamaq); space complexity-də call stack-i saymamaq; hər məsələni rekursiya ilə həll etməyə çalışmaq — sadə dövr daha oxunaqlı olanda rekursiya seçmək mənfi siqnaldır.