С# dasturlash tilida rekursiv funksiyalar

funktsiya Ханой:
kiritish: tamsayı n, shu kabi n >= 1
1. agar n 1 ga teng keyin qaytib keling 1
2. qaytish [2 * [qo'ng'iroq qiling hanoy (n-1)] + 1]
oxiri xanoy

Barcha rekursiv funktsiyalar aniq echimga ega bo'lmasada, Xanoy minorasi ketma-ketligini aniq formulaga keltirish mumkin.^[9]

Xanoy minoralari uchun aniq formula:

h1 = 1 = 2^1 - 1 soat2 = 3 = 2^2 - 1 soat3 = 7 = 2^3 - 1 soat4 = 15 = 2^4 - 1 soat5 = 31 = 2^5 - 1 soat6 = 63 = 2^6 - 1 soat7 = 127 = 2^7 - 1 Umuman olganda: hn = 2^n - 1, barchasi uchun n> = 1

Ikkilik qidiruv

The ikkilik qidirish algoritm - bu izlash usuli tartiblangan qator har bir rekursiv o'tish bilan massivni ikkiga kesib bitta element uchun. Bu hiyla-nayrang - qatorning markaziga yaqin o'rta nuqtani tanlash, shu vaqtdagi ma'lumotlarni qidirilayotgan ma'lumotlar bilan taqqoslash va keyin uchta mumkin bo'lgan shartlardan biriga javob berishdir: ma'lumotlar o'rta nuqtada topilgan, o'rta nuqtadagi ma'lumotlar kattaroq qidirilayotgan ma'lumotlardan yoki o'rta nuqtadagi ma'lumotlar qidirilayotgan ma'lumotlardan kamroq.

Ushbu algoritmda rekursiya qo'llaniladi, chunki har bir o'tish paytida eskisini yarmiga qisqartirish orqali yangi massiv yaratiladi. Ikkilik qidirish protsedurasi keyinchalik rekursiv deb nomlanadi, bu safar yangi (va kichikroq) massivda. Odatda massivning kattaligi boshlanish va tugatish indekslarini boshqarish orqali o'rnatiladi. Algoritm o'sishning logaritmik tartibini namoyish etadi, chunki u mohiyatan har bir o'tish paytida muammoli maydonni ikkiga ajratadi.

Ikkilik qidirishni C-da amalga oshirishning misoli:

Ma'lumotlarning rekursiv tuzilmalari (tarkibiy rekursiya)

Asosiy maqola: Rekursiv ma'lumotlar turi

Kompyuter fanida rekursiyaning muhim qo'llanilishi bu kabi dinamik ma'lumotlar tuzilmalarini aniqlashda ro'yxatlar va daraxtlar. Rekursiv ma'lumotlar tuzilmalari ish vaqti talablariga javoban nazariy jihatdan cheksiz hajmgacha dinamik ravishda o'sishi mumkin; aksincha, statik massivning kattaligi kompilyatsiya vaqtida o'rnatilishi kerak.

"Rekursiv algoritmlar, ayniqsa, asosiy muammo yoki ishlov beriladigan ma'lumotlar rekursiv so'zlar bilan aniqlanganda juda mos keladi."^[10]

Ushbu bo'limdagi misollar "strukturaviy rekursiya" deb nomlanadigan narsani tasvirlaydi. Ushbu atama rekursiv protseduralarning rekursiv aniqlangan ma'lumotlarga ta'sir qilishini anglatadi.

Dasturchi shablonni ma'lumotlar ta'rifidan olgan ekan, funktsiyalar tarkibiy rekursiyani qo'llaydi. Ya'ni, funktsiya tanasidagi rekursiyalar ma'lum bir birikma qiymatining darhol qismini iste'mol qiladi.^[6]

Bog'langan ro'yxatlar

Asosiy maqola: Bog'langan ro'yxat

Quyida bog'langan ro'yxat tugunlari tuzilishining C ta'rifi keltirilgan. Ayniqsa, tugunning o'zi qanday aniqlanganiga e'tibor bering. Ning "keyingi" elementi struct tuguni boshqasiga ko'rsatgich struct tuguni, ro'yxat turini samarali yaratish.

tuzilmaviy tugun{ int ma'lumotlar; // ba'zi bir butun ma'lumotlar tuzilmaviy tugun *Keyingisi; // boshqa tuzilish tuguniga ko'rsatgich};

Chunki struct tuguni ma'lumotlar tuzilishi rekursiv tarzda aniqlanadi, unda ishlaydigan protseduralar tabiiy ravishda rekursiv protseduralar sifatida amalga oshirilishi mumkin. The list_print Quyida belgilangan protsedura ro'yxat bo'sh bo'lgunga qadar ro'yxatda yuradi (ya'ni ro'yxat ko'rsatgichi NULL qiymatiga ega). Har bir tugun uchun u ma'lumotlar elementini (tamsayı) bosib chiqaradi. C dasturida ro'yxat o'zgarmas bo'lib qoladi list_print protsedura.

bekor list_print(tuzilmaviy tugun *ro'yxat){ agar (ro'yxat != NULL) // asosiy ish { printf ("% d", ro'yxat->ma'lumotlar); // bo'sh joy bilan birga butun sonli ma'lumotlarni chop eting list_print (ro'yxat->Keyingisi); // keyingi tugundagi rekursiv qo'ng'iroq }}

Ikkilik daraxtlar

Asosiy maqola: Ikkilik daraxt

Quyida ikkilik daraxt tuguni uchun oddiy ta'rif berilgan. Bog'langan ro'yxatlar uchun tugun singari, u o'z-o'zidan, rekursiv ravishda aniqlanadi. O'z-o'ziga yo'naltirilgan ikkita ko'rsatgich mavjud: chap (chap pastki daraxtga ishora) va o'ng (o'ng pastki daraxtga ishora).

tuzilmaviy tugun{ int ma'lumotlar; // ba'zi bir butun ma'lumotlar tuzilmaviy tugun *chap; // chap pastki daraxtga ko'rsatgich tuzilmaviy tugun *to'g'ri; // o'ng pastki daraxtga ishora qiling};

Daraxtdagi operatsiyalar rekursiya yordamida amalga oshirilishi mumkin. Shuni esda tutingki, ikkita o'z-o'ziga yo'naltirilgan ko'rsatgich (chap va o'ng) mavjud bo'lganligi sababli, daraxt operatsiyalari ikkita rekursiv qo'ng'iroqni talab qilishi mumkin:

// tree_node tarkibida i mavjudligini tekshiring; agar shunday bo'lsa, 1 ni qaytaring, agar bo'lmasa, 0 ni qaytaring.int daraxt_kontaktlari(tuzilmaviy tugun *tree_node, int men) { agar (tree_node == NULL) qaytish 0; // asosiy ish boshqa agar (tree_node->ma'lumotlar == men) qaytish 1; boshqa qaytish daraxt_kontaktlari(tree_node->chap, men) || daraxt_kontaktlari(tree_node->to'g'ri, men);}

Har qanday qo'ng'iroq uchun eng ko'p ikkita rekursiv qo'ng'iroq amalga oshiriladi daraxt_kontaktlari yuqorida ta'riflanganidek.

// Inorder traval:bekor daraxt_print(tuzilmaviy tugun *tree_node) { agar (tree_node != NULL) { // asosiy ish daraxt_print(tree_node->chap); // chapga o'ting printf("% d", tree_node->ma'lumotlar); // butun sonni, so'ngra bo'sh joyni chop eting daraxt_print(tree_node->to'g'ri); // o'ngga o'ting }}

Yuqoridagi misol an tartibda o'tish ikkilik daraxt. A Ikkilik qidiruv daraxti har bir tugunning ma'lumotlar elementlari tartibda joylashgan ikkilik daraxtning alohida holati.

Fayl tizimining o'tishi

A-dagi fayllar soni fayl tizimi farq qilishi mumkin, rekursiya uning mazmunini bosib o'tish va shu bilan sanab o'tishning yagona amaliy usuli. Fayl tizimidan o'tish bu bilan juda o'xshash daraxtlarni kesib o'tish, shuning uchun daraxtlar bo'ylab harakatlanish tushunchalari fayl tizimidan o'tishda qo'llaniladi. Aniqrog'i, quyidagi kod a ga misol bo'ladi oldindan buyurtma fayl tizimining.

Import java.io. *;jamoat sinf FileSystem { jamoat statik bekor asosiy (Ip [] kamon) { shpal (); } /*** Fayl tizimining ildizlarini oladi* Rekursiv fayl tizimining harakatlanishi bilan daromad */ xususiy statik bekor shpal () { Fayl [] fs = Fayl.listRoots (); uchun (int men = 0; men < fs.uzunlik; men++) { agar (fs[men].isDirectory () && fs[men].canRead ()) { rtraverse (fs[men]); } } } /*** Berilgan katalogni rekursiv ravishda kesib o'ting ** @param fd o'tishning boshlang'ich nuqtasini bildiradi */ xususiy statik bekor rtraverse (Fayl fd) { Fayl [] fss = fd.listFiles (); uchun (int men = 0; men < fss.uzunlik; men++) { Tizim.chiqib.println (fss[men]); agar (fss[men].isDirectory () && fss[men].canRead ()) { rtraverse (fss[men]); } } }}

Ushbu kod hech bo'lmaganda rekursiya va orasidagi chiziqlarni birlashtiradi takrorlash. Bu, asosan, a-ni bosib o'tishning eng yaxshi usuli bo'lgan rekursiv dasturdir fayl tizimi. Bu to'g'ridan-to'g'ri va bilvosita rekursiyaning namunasidir. "Rtraverse" usuli to'g'ridan-to'g'ri to'g'ridan-to'g'ri misoldir; "shpal" usuli bilvosita, "rtraverse" deb nomlanadi. Ushbu misolda "asosiy ish" stsenariysi kerak emas, chunki ma'lum bir fayl tizimida har doim aniq bir qator fayllar yoki kataloglar bo'ladi.

Amalga oshirish masalalari

Haqiqiy amalga oshirishda, aniq rekursiv funktsiyadan ko'ra (asosiy ishni bitta tekshirish, aks holda rekursiv qadam), aniqlik yoki samaradorlik uchun bir qator o'zgartirishlar kiritilishi mumkin. Bunga quyidagilar kiradi:

• 
  Sargich funktsiyasi (tepada)
  
• 
  Asosiy korpusni qisqa tutashuv, aka "qo'l uzunligidagi rekursiya" (pastki qismida)
  
• 
  Gibrid algoritm (pastki qismida) - ma'lumotlar etarlicha kichik bo'lgandan keyin boshqa algoritmga o'tish
  

Xushbichimlik asosida, o'rash funktsiyalari odatda ma'qullanadi, qisqa tutashgan holda esa, asosan, akademik muhitda tayanch kassasi yomon ko'riladi. Gibrid algoritmlar tez-tez samaradorlik uchun, kichik holatlarda rekursiya ustama xarajatlarini kamaytirish uchun ishlatiladi va qo'lning uzunligi bo'yicha rekursiya bu alohida holat.

Sargich funktsiyasi

A o'rash funktsiyasi to'g'ridan-to'g'ri chaqirilgan, lekin o'zini o'zi takrorlamaydigan, aksincha rekursiyani bajaradigan alohida yordamchi funktsiyani chaqiradigan funktsiya.

Wrapper funktsiyalari parametrlarni tasdiqlash uchun ishlatilishi mumkin (shuning uchun rekursiv funktsiya ularni o'tkazib yuborishi mumkin), ishga tushirishni amalga oshiradi (xotirani ajratadi, o'zgaruvchilarni ishga tushiradi), ayniqsa "rekursiya darajasi" kabi yordamchi o'zgaruvchilar uchun yoki qisman hisoblash uchun yod olishva istisno va xatolarni ko'rib chiqing. Qo'llab-quvvatlaydigan tillarda ichki funktsiyalar, yordamchi funktsiya o'rash funktsiyasi ichiga joylashtirilishi va umumiy doiradan foydalanishi mumkin. O'rnatilgan funktsiyalar bo'lmasa, yordamchi funktsiyalar o'rniga alohida funktsiya, agar iloji bo'lsa, xususiy (agar ular to'g'ridan-to'g'ri chaqirilmasa), va ma'lumot yordamida o'rash funktsiyasi bilan bo'lishiladi havola.

Asosiy ishni qisqa tutashuv

Qisqa tutashgan taglik qutisi, shuningdek ma'lum