С# dasturlash tilida rekursiv funksiyalar

uzunlikdagi rekursiya, asosiy ishni tekshirishdan iborat oldin rekursiv qo'ng'iroqni amalga oshirish - ya'ni, qo'ng'iroq o'rniga asosiy qo'ng'iroqning asosiy ish bo'lishini tekshirish va keyin asosiy ishni tekshirish. Qisqa tutashuv, zudlik bilan qaytib keladigan funktsiya chaqiruvining ortiqcha bo'lishiga yo'l qo'ymaslik uchun, ayniqsa samaradorlik sababli amalga oshiriladi. E'tibor bering, asosiy ish allaqachon tekshirilgan (rekursiv bosqichdan oldin), uni alohida tekshirish shart emas, lekin umumiy rekursiya asosiy holatdan boshlanganda, ish uchun o'rash funktsiyasidan foydalanish kerak. o'zi. Masalan, faktorial funktsiyalarda asosiy holat 0 ga teng! = 1, darhol 1ni 1 ga qaytarganda! qisqa tutashuv bo'lib, 0 o'tkazib yuborishi mumkin; bu o'rash funktsiyasi bilan yumshatilishi mumkin.

Qisqa tutashuv, birinchi navbatda, ko'pgina asosiy holatlarga duch kelganda tashvishga soladi, masalan, daraxtdagi Null ko'rsatkichlari, bu funktsiya qo'ng'iroqlari sonida chiziqli bo'lishi mumkin, shuning uchun sezilarli tejash O(n) algoritmlar; Bu chuqurlikdan qidirish uchun quyida keltirilgan. Daraxtdagi qisqa tutashuv, bo'sh tugunni asosiy holat deb hisoblashdan ko'ra, bargni (bolalari bo'lmagan bo'sh tugunni) asosiy holat deb hisoblashga to'g'ri keladi. Agar faktorial hisoblashda faqat bitta asosiy ish bo'lsa, qisqa tutashuv faqat beradi O(1) tejash.

Kontseptual ravishda, qisqa tutashuv bir xil asosiy holat va rekursiv bosqichga ega deb hisoblanishi mumkin, faqat asosiy holatni rekursiyadan oldin tekshiradi yoki boshqa bazaviy holatga ega (standart bazadan bitta qadam olib tashlangan) va ko'proq murakkab rekursiv qadam, ya'ni "check valid then recurse", chunki daraxt tugunlari uchun bo'sh tugunlarni emas, balki bo'sh tugunlarni ko'rib chiqishda. Qisqa tutashuv bazaviy kassani aniq ajratish va standart rekursiyaning rekursiv pog'onasi bilan taqqoslaganda ancha murakkab oqimga ega bo'lgani uchun, u ko'pincha yomon uslub deb hisoblanadi, ayniqsa akademik muhitda.^[11]

Chuqurlikdan birinchi qidirish

Qisqa tutashuvning asosiy misoli keltirilgan birinchi chuqurlikdagi qidiruv Ikkilik daraxtning (DFS); qarang ikkilik daraxtlar standart rekursiv munozarasi uchun bo'lim.

DFS uchun standart rekursiv algoritm:

• 
  asosiy holat: Agar joriy tugun Null bo'lsa, false qiymatini qaytaring
  
• 
  recursive step: aks holda, joriy tugunning qiymatini tekshiring, agar mos bo'lsa, true qiymatini qaytaring, aks holda bolalarga qaytaring
  

Qisqa tutashuvda bu quyidagicha:

• 
  joriy tugunning qiymatini tekshiring, agar to'g'ri kelsa,
  
• 
  aks holda, agar bolalarda, agar Null bo'lmasa, unda takrorlaning.
  

Standart qadamlar nuqtai nazaridan, bu asosiy ishni tekshirishni harakatga keltiradi oldin rekursiv qadam. Shu bilan bir qatorda, ularni navbati bilan asosiy holat va rekursiv qadamning boshqa shakli deb hisoblash mumkin. Shuni esda tutingki, buning uchun daraxtning o'zi bo'sh bo'lganida (ildiz tuguni Null) ishni bajarish uchun o'ram funksiyasi kerak.

Agar a mukammal ikkilik daraxt balandlik h, 2 bor^h+1−1 tugun va 2^h+1 Bolalardagi bo'sh ko'rsatkichlar (har ikkitasi uchun 2 dan^h , shuning uchun qisqa tutashuv eng yomon holatda funktsiya chaqiruvlari sonini yarmiga qisqartiradi.

C-da standart rekursiv algoritm quyidagicha amalga oshirilishi mumkin:

bool daraxt_kontaktlari(tuzilmaviy tugun *tree_node, int men) { agar (tree_node == NULL) qaytish yolg'on; // asosiy ish boshqa agar (tree_node->ma'lumotlar == men) qaytish to'g'ri; boshqa qaytish daraxt_kontaktlari(tree_node->chap, men) || daraxt_kontaktlari(tree_node->to'g'ri, men);}

Qisqa tutashgan algoritm quyidagicha amalga oshirilishi mumkin:

// Bo'sh daraxtga ishlov beradigan o'rash funktsiyasibool daraxt_kontaktlari(tuzilmaviy tugun *tree_node, int men) { agar (tree_node == NULL) qaytish yolg'on; // bo'sh daraxt boshqa qaytish daraxt_kontaktlari_do(tree_node, men); // yordamchi funktsiyani chaqirish}// tree_node-ni qabul qiladi! = NULLbool daraxt_kontaktlari_do(tuzilmaviy tugun *tree_node, int men) { agar (tree_node->ma'lumotlar == men) qaytish to'g'ri; // topildi boshqa // recurse qaytish (tree_node->chap && daraxt_kontaktlari_do(tree_node->chap, men)) || (tree_node->to'g'ri && daraxt_kontaktlari_do(tree_node->to'g'ri, men));}

Ning ishlatilishiga e'tibor bering qisqa tutashuvni baholash Boolean && (AND) operatorlari, shuning uchun rekursiv chaqiruv faqat tugun to'g'ri bo'lsa (Null bo'lmagan) amalga oshiriladi. AND-dagi birinchi atama tugunga ishora qilsa, ikkinchi atama bool, shuning uchun umumiy ifoda mantiqiy qiymatga baholanadi. Bu rekursiv qisqa tutashuvda keng tarqalgan ibora. Bu mantiqiy || ning qisqa tutashuvli baholashiga qo'shimcha (OR) operatori, faqat chap bolasi ishlamay qolsa, o'ng bolani tekshirish uchun. Aslida, butun oqim oqimi Ushbu funktsiyalarni qaytarish bayonotida bitta mantiqiy ifoda bilan almashtirish mumkin, ammo samaradorlik uchun hech qanday foyda keltirmaydi.

Gibrid algoritm

Rekursiv algoritmlar ko'pincha kichik ma'lumotlar uchun samarasiz bo'ladi, chunki bu takrorlanadigan funktsiya chaqiruvlari va qaytishlariga bog'liq. Shu sababli, rekursiv algoritmlarni samarali tatbiq etish ko'pincha rekursiv algoritmdan boshlanadi, ammo kirish kichik bo'lganda boshqa algoritmga o'tadi. Muhim misol birlashtirish, bu ko'pincha rekursiv bo'lmagan holatga o'tish orqali amalga oshiriladi qo'shish tartibi da bo'lgani kabi ma'lumotlar etarlicha kichik bo'lganda plitka bilan birlashtirilgan tartib. Gibrid rekursiv algoritmlarni, ko'pincha bo'lgani kabi, yanada takomillashtirish mumkin Timsort, gibrid birlashma saralash / qo'shish tartibidan olingan.

Takrorlash va takrorlanish

Rekursiya va takrorlash teng darajada ifodali: rekursiyani aniq bilan takrorlash bilan almashtirish mumkin chaqiruv to'plami, takrorlanish bilan almashtirilishi mumkin quyruq rekursiyasi. Qaysi yondashuv afzalligi ko'rib chiqilayotgan muammo va ishlatilgan tilga bog'liq. Yilda majburiy dasturlash, takrorlash, ayniqsa oddiy rekursiya uchun afzalroqdir, chunki bu funktsiya chaqiruvlari va qo'ng'iroqlar stekini boshqarishning ortiqcha yukidan qochadi, lekin rekursiya odatda ko'p rekursiya uchun ishlatiladi. Aksincha, ichida funktsional tillar quyruq rekursiyasini optimallashtirish bilan ortiqcha xarajatlarga olib keladigan rekursiya afzaldir. Takrorlash yordamida algoritmni amalga oshirish osonlikcha erishilmasligi mumkin.

X ni hisoblash uchun andozalarni solishtiring_n x bilan belgilanadi_n = f (n, x_n-1) x dan_tayanch:

funktsiya rekursiv (n), agar n == asos qaytish xtayanch aks holda f (n, rekursiv (n-1)) qaytaring

funktsiya yineleyici (n) x = xtayanch uchun i = asos + 1 dan n x = f (i, x) ga x qaytariladi

Imperativ til uchun qo'shimcha xarajatlar funktsiyani, funktsional til uchun qo'shimcha xarajatlar x akkumulyator o'zgaruvchisini belgilaydi.

Masalan, a faktorial funktsiyasini takroriy ravishda amalga oshirish mumkin C argumentlarni berish va qiymatlarni rekursiya bilan qaytarish o'rniga, loop indeksining o'zgaruvchisi va akkumulyator o'zgaruvchisiga tayinlash orqali:

imzosiz int faktorial(imzosiz int n) { imzosiz int mahsulot = 1; // bo'sh mahsulot 1 ga teng esa (n) { mahsulot *= n; --n; } qaytish mahsulot;}

Ta'sirchan kuch

Ko'pchilik dasturlash tillari bugungi kunda qo'llanilayotgan rekursiv funktsiyalar va protseduralarni to'g'ridan-to'g'ri aniqlashtirishga imkon beradi. Bunday funktsiya chaqirilganda dasturning ish vaqti muhiti har xilligini kuzatib boradi misollar funktsiyasi (ko'pincha a yordamida chaqiruv to'plami, ammo boshqa usullardan foydalanish mumkin). Rekursiv qo'ng'iroqlarni bilan almashtirish orqali har qanday rekursiv funktsiyani takrorlanadigan funktsiyaga aylantirish mumkin takroriy boshqaruv konstruktsiyalari va qo'ng'iroqlar to'plamini a bilan simulyatsiya qilish stack aniq boshqariladi dastur bo'yicha.^[12][13]

Aksincha, kompyuter tomonidan baholanishi mumkin bo'lgan barcha takrorlanadigan funktsiyalar va protseduralar (qarang Turing to'liqligi) rekursiv funktsiyalar bilan ifodalanishi mumkin; kabi takroriy boshqaruv konstruktsiyalari esa ko'chadan va ko'chadan uchun muntazam ravishda rekursiv shaklda qayta yoziladi funktsional tillar.^[14][15] Biroq, amalda ushbu qayta yozish bog'liqdir quyruq qo'ng'irog'ini yo'q qilish, bu barcha tillarning xususiyati emas. C, Javava Python barcha funktsiya chaqiruvlari, shu jumladan, asosiy oqim tillari quyruq qo'ng'iroqlari, loop konstruktsiyalaridan foydalanishda yuzaga kelmaydigan stack ajratilishiga olib kelishi mumkin; ushbu tillarda rekursiv shaklda qayta ishlangan takrorlanadigan dastur bo'lishi mumkin qo'ng'iroqlar to'plamini to'ldirish, garchi quyruq qo'ng'irog'ini yo'q qilish tilning spetsifikatsiyasi bilan qoplanmagan xususiyat bo'lishi mumkin va bir xil tilning turli xil ilovalari quyruq qo'ng'irog'ini yo'q qilish qobiliyatlari bilan farq qilishi mumkin.

Ishlash muammolari

Tillarda (masalan C va Java) davriy ko'chadan konstruktsiyalarni ma'qullaydigan, odatda stackni boshqarish uchun zarur bo'lgan ortiqcha xarajatlar va funktsiya chaqiruvlarining nisbatan sustligi tufayli rekursiv dasturlar bilan bog'liq vaqt va makon uchun katta xarajatlar mavjud; yilda funktsional tillar, funktsiya chaqiruvi (xususan, a quyruq chaqiruvi) odatda juda tezkor operatsiya bo'lib, farq odatda unchalik sezilmaydi.

Aniq misol sifatida yuqoridagi "faktorial" misolning rekursiv va takroriy bajarilishi o'rtasidagi ishlashning farqi juda bog'liq kompilyator ishlatilgan. Loop konstruktsiyalari afzal ko'rilgan tillarda takroriy versiya bir nechta bo'lishi mumkin kattalik buyruqlari rekursivga qaraganda tezroq. Funktsional tillarda, ikkita dasturning umumiy vaqt farqi ahamiyatsiz bo'lishi mumkin; aslida kichik sonlarni emas, balki kattaroq sonlarni ko'paytirish xarajatlari (bu erda berilgan iterativ versiya amalga oshiriladi) takrorlanishni tanlash bilan tejashga imkon beradigan vaqtni engib chiqishi mumkin.

Bo'sh joy

Ba'zi dasturlash tillarida .ning maksimal hajmi chaqiruv to'plami mavjud maydondan ancha kam uyum, va rekursiv algoritmlar takrorlanuvchi algoritmlarga qaraganda ko'proq bo'sh joy talab qiladi. Binobarin, ushbu tillar ba'zan oldini olish uchun rekursiya chuqurligiga cheklov qo'yadi stack overflows; Python ana shunday tillardan biri.^[16] Ning maxsus ishi bo'yicha quyidagi ogohlantirishga e'tibor bering quyruq rekursiyasi.

Zaiflik

Rekursiv algoritmlar stek to'lib toshishi mumkinligi sababli, ular zaif bo'lishi mumkin patologik yoki zararli kiritish.^[17] Ba'zi zararli dasturlar, ayniqsa, dasturning qo'ng'iroqlar to'plamini maqsad qilib oladi va stackning o'ziga xos rekursiv xususiyatidan foydalanadi.^[18] Zararli dastur mavjud bo'lmaganda ham, cheksiz rekursiyadan kelib chiqadigan stek to'kilishi dastur uchun o'lik bo'lishi mumkin va istisno bilan ishlash mantiq mos keladigan narsalarga to'sqinlik qilmasligi mumkin jarayon bo'lishdan bekor qilingan.^[19]

Rekursiv muammolarni ko'paytiring

Ko'payib ketadigan rekursiv muammolar o'z-o'zidan rekursivdir, chunki ular oldingi holatga qarab kuzatilishi kerak. Bir misol daraxtlarni kesib o'tish kabi birinchi chuqurlikdagi qidiruv; ikkala rekursiv va takroriy usullardan foydalanilsa ham,^[20] ular birma-bir rekursiv va shu bilan tabiiy ravishda takrorlanadigan usul bo'lgan ro'yxatdagi o'tish va chiziqli qidirish bilan farq qiladi. Boshqa misollarga quyidagilar kiradi algoritmlarni ajratib oling kabi Quicksortva kabi funktsiyalar Ackermann funktsiyasi. Ushbu algoritmlarning barchasi aniq yordamida aniqlik bilan amalga oshirilishi mumkin suyakka, ammo dasturchining stekni boshqarish bilan bog'liq sa'y-harakatlari va natijada olingan dasturning murakkabligi, shubhasiz, takroriy echimning afzalliklaridan ustundir.

Rekursiyani qayta ishlash

Rekursiv algoritmlarni rekursiv bo'lmagan analoglar bilan almashtirish mumkin.^[21] Rekursiv algoritmlarni almashtirish usullaridan biri ularni ishlatib simulyatsiya qilishdir uyma xotira o'rniga xotira to'plami.^[22] Shu bilan bir qatorda, almashtirish uchun algoritmni butunlay rekursiv bo'lmagan usullarga asoslangan holda ishlab chiqish qiyin bo'ladi.^[23] Masalan, uchun rekursiv algoritmlar mos keladigan joker belgilar, kabi Boy Salz' wildmat algoritm,^[24] bir vaqtlar odatiy bo'lgan. Xuddi shu maqsad uchun rekursiv bo'lmagan algoritmlar, masalan Kraussga mos keladigan joker belgilar algoritmi, rekursiyaning kamchiliklarini oldini olish uchun ishlab chiqilgan^[25] va yig'ish kabi texnikalar asosida faqat bosqichma-bosqich takomillashdi testlar va profil yaratish ishlash.^[26]

Quyruq-rekursiv funktsiyalar

Quyruq-rekursiv funktsiyalar - bu barcha rekursiv chaqiriqlar bo'lgan funktsiyalar quyruq qo'ng'iroqlari va shuning uchun kechiktirilgan operatsiyalarni tuzmang. Masalan, gcd funktsiyasi (quyida yana ko'rsatilgan) quyruq-rekursivdir. Aksincha, faktorial funktsiya (quyida) emas quyruq-rekursiv; chunki uning rekursiv chaqiruvi quyruq holatida emas, u so'nggi rekursiv chaqiruv tugagandan so'ng bajarilishi kerak bo'lgan kechiktirilgan ko'paytirish operatsiyalarini tuzadi. Bilan kompilyator yoki tarjimon quyruq-rekursiv qo'ng'iroqlar kabi munosabatda sakrash funktsiya chaqiruvlaridan ko'ra, gcd kabi quyruq-rekursiv funktsiya doimiy bo'shliqdan foydalanib ishlaydi. Shunday qilib, dastur asosan iterativ bo'lib, "for" va "while" ko'chadan kabi imperativ tilni boshqarish tuzilmalaridan foydalanishga tengdir.

Quyruq rekursiyasi:	Rekursiyani oshirish:
// INPUT: x, y tamsayılar, shunday qilib x> = y va y> = 0 bo'ladiint gcd(int x, int y){ agar (y == 0) qaytish x; boshqa qaytish gcd(y, x % y);}	// INPUT: n n> = 0 ga teng bo'lgan butun sonint haqiqat(int n){ agar (n == 0) qaytish 1; boshqa qaytish n * haqiqat(n - 1);}

Quyruq rekursiyasining ahamiyati shundaki, quyruq-rekursiv qo'ng'iroqni amalga oshirishda (yoki har qanday quyruq chaqirig'ida) qo'ng'iroq qiluvchining qaytish holati saqlanib qolmasligi kerak chaqiruv to'plami; rekursiv qo'ng'iroq qaytganda, u to'g'ridan-to'g'ri oldindan saqlangan qaytish pozitsiyasida tarmoqlanadi. Shuning uchun quyruq chaqiruvlarining ushbu xususiyatini tan oladigan tillarda quyruq rekursiyasi ham bo'shliqni, ham vaqtni tejaydi.

Ijro tartibi

O'zini faqat bir marta chaqiradigan funktsiyani oddiy holatida, rekursiv chaqiriq oldidan qo'yilgan ko'rsatmalar rekursiv chaqiruvdan keyin qo'yilgan ko'rsatmalardan oldin har bir rekursiya uchun bir marta bajariladi. Ikkinchisi maksimal rekursiyaga erishilgandan so'ng qayta-qayta bajariladi. Ushbu misolni ko'rib chiqing:

Funktsiya 1

bekor recursiveFunction(int num) { printf("% d n", num); agar (num < 4) recursiveFunction(num + 1);}

O'zgartirilgan chiziqlar bilan 2-funktsiya

bekor recursiveFunction(int num) { agar (num < 4) recursiveFunction(num + 1); printf("% d n", num);}

Rekursiv algoritmlarning vaqt samaradorligi

The vaqt samaradorligi rekursiv algoritmlarni a bilan ifodalash mumkin takrorlanish munosabati ning Big O notation. Ular (odatda) keyin bitta Big-O terminida soddalashtirilishi mumkin.

Qisqa klavish (master teorema)

Asosiy maqola: Magistr teoremasi (algoritmlarni tahlil qilish)

Agar funktsiyaning vaqt murakkabligi shaklda bo'lsa

Shunday qilib, vaqt murakkabligining Big O:

• 
  Agar   ba'zi bir doimiy uchun  , keyin 
  
• 
  Agar  , keyin 
  
• 
  Agar   ba'zi bir doimiy uchun  va agar bo'lsa   ba'zi bir doimiy uchun v <1 va barchasi etarlicha katta n, keyin 
  

qayerda a har bir rekursiya darajasidagi rekursiv qo'ng'iroqlar sonini, b rekursiyaning keyingi darajasi uchun qaysi omil kichikroq bo'lganligini anglatadi (ya'ni muammoni ajratadigan qismlar soni) va f (n) funktsiya rekursiyaning har bir darajasida (masalan, qismlarga ajratish, birlashtirish) mustaqil ravishda bajaradigan ishni ifodalaydi.