Recursion — funksiya muammoning kichikroq nusxasini yechish uchun o‘zini bevosita yoki boshqa funksiyalar orqali qayta chaqiradigan usuldir. Har chaqiriq alohida parametr va lokal holatga ega bo‘ladi. Jarayon base case’ga yetganda qaytish boshlanadi; base case yo‘q yoki unga yaqinlashmasa cheksiz recursion va stack overflow yuz beradi.
Tuzilishi
Rekursiv yechim ikki qismga ega: oddiy holatni to‘g‘ridan yechuvchi base case va kirishni kichraytiruvchi recursive step. Faktorial misolida n=0 natija 1, boshqa holatda n * factorial(n-1). To‘g‘rilik inductionga o‘xshash fikr bilan isbotlanadi: kichik masala to‘g‘ri deb olinib, joriy qadam undan to‘g‘ri natija yaratadi.
Har qadam progress metricni kamaytirishi yoki yakuniy holatga yaqinlashtirishi kerak. Grafda cycle bo‘lsa faqat chuqurlik kamaymasligi mumkin; visited set ayni tugunni qayta kirishdan saqlaydi.
Qo‘llanish
Tree traversal tabiiy rekursiv: tugun qayta ishlanib, har child uchun ayni funksiya chaqiriladi. Divide-and-conquer quicksort va merge sort muammoni qismlarga bo‘ladi. Parser ichma-ich grammatik tuzilmani recursion bilan ifodalaydi. Backtracking variantni tanlab, muvaffaqiyatsiz bo‘lsa oldingi holatga qaytadi.
Rekursiv kod qisqa bo‘lsa ham vaqt murakkabligi yashirin bo‘lishi mumkin. Naive Fibonacci bir xil kichik masalani ko‘p takrorlab eksponensial ishlaydi. Memoization natijani cache qilib dinamik dasturlashga aylantiradi. Cache kaliti barcha relevant holatni qamrashi kerak.
Stack va tail recursion
Har chaqiriq call stackda frame egallaydi. Chuqurlik input hajmiga chiziqli bo‘lsa katta ma’lumot stack limitidan oshadi. Iterative algoritm va explicit stack heapda boshqariladigan hajm beradi. DFS uchun recursive va iterative variant bir xil asimptotik xotira ishlatishi mumkin, lekin explicit tuzilma limit va xatoni nazorat qiladi.
Tail recursionda recursive call funksiyaning oxirgi amali bo‘ladi. Tail-call optimization mavjud bo‘lsa compiler joriy frameni qayta ishlatadi. Barcha til yoki debug rejimi buni kafolatlamaydi; stack xavfsizligi uchun hujjatlashtirilgan kafolatga tayaniladi.
Xatolar va himoya
Foydalanuvchi bergan JSON, XML yoki arxiv ichma-ichligi juda katta bo‘lsa parser stackini tugatib DoS yaratishi mumkin. Parser maksimal depth qo‘yadi va limit xatosini boshqariladigan tarzda qaytaradi. Directory symlink cycle yoki object graph cycle visited identity orqali aniqlanadi.
Mutual recursionda A Bni, B yana Ani chaqiradi; base case zanjir bo‘ylab tahlil qilinadi. Debugger stack trace qaytarilmagan chaqiriqlarni ko‘rsatadi, ammo minglab frame logni haddan oshirmasligi uchun qisqartiriladi. Test minimal, limitga yaqin va limitdan oshgan inputni qamrab oladi.
Memoization chegaralari
Memoization recursive subproblemni tezlashtiradi, ammo cache kaliti katta yoki cheksiz bo‘lsa xotira tugashi mumkin. Requestga xos hisob uchun cache lifetime ham request bilan tugaydi; global cache tenant ma’lumotini aralashtirmaydi. Recursive dynamic programmingda top-down usul faqat kerakli holatni hisoblaydi, bottom-up esa stackdan foydalanmay, tartibni ochiq boshqaradi. Qaysi biri samarali ekanini reachable state soni belgilaydi. Parallel recursion tasklarni har tugunda yaratib yuborsa scheduling xarajati ishni bosib ketadi. Cutoffdan kichik subproblem ketma-ket bajariladi. Shared memo table uchun sinxronizatsiya yoki immutable natija protokoli kerak.
Rekursiv yechimni baholashda faqat vaqt murakkabligi emas, maksimal chaqiruv chuqurligi ham hisoblanadi. Kirish kattalashganda chuqurlik chiziqli oshsa, iterativ shakl yoki aniq stek tuzilmasi xavfsizroq bo‘lishi mumkin.
Bog‘liq tushunchalar
Base case, Call stack, Tail recursion, Memoization, Backtracking, Stack overflow