Reja: Rekursiv funksiya haqida maʼlumot

Mavzu: Rekursiv funksiya.
Reja:
1. Rekursiv funksiya haqida maʼlumot.
2. Javada rekursiv funksiya.
3. Javada rekursiv funksiyaga misollar.

1. Rekursiv funksiya haqida ma'lumot.

Funksiya o'ziga o'zi to'g'ridan-to'g'ri yoki qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb ataladi.
Hikoyadagi misolga qaytadigan bo'lsak, Abdullajon u yerda summa() nomli funksiya natijasini hisoblash uchun unga bir necha marta qayta murojaat qilishiga to'g'ri keldi. Aynan shu narsa rekursiyaning mohiyatini tashkil qiladi. Lekin, shunchaki ta'rif yordamida to'g'ri va xatosiz ishlovchi rekursiv funksiya tuzish qiyin, buning uchun rekursiv funksiyaning asosiy shartlarini yaxshi bilish kerak.
Rekursiyani to'g'ri tashkil qilish shartlari:
Har qanday to'g'ri tuzilgan rekursiya asosini ikkita shart tashkil qiladi.
Rekursiya asos sharti
Funksiyaning o'ziga o'zgartirilgan argument bilan murojaat qilish.
Rekursiv funksiya qaysidir vaqtga kelib o'ziga murojaat qilishni to'xtatishi kerak bo'ladi. Aynan shu narsani rekursiya asos sharti ta'minlab beradi. Hikoyamizdagi misolga qaytadigan bo'lsak, Abdullajon summa() funksiyasiga bir necha marta murojaat qildi va oxirida funksiyaga keluvchi massivda faqat bitta element qolganda to'xtadi. Bu masala uchun arrayda yagona element qolishi asos shart bo'lib xizmat qiladi va shu yerga yetganda dastur to'xtashi kerakligini bilib oladi. Rekursiv funksiya tuzishda asos shartni to'g'ri qo'yish juda ham muhim hisoblanadi. Hali bunga yana to'xtalamiz.
Keyingi shartda o'zgartirilgan argument deganda, odatda masala boshidagi argumentdan kichikroq argument tushiniladi (ba'zi hollarda kattaroq bo'lishi mumkin). Misolimizda, Abdullajon har safar summa() funksiyasiga murojaat qilganda undagi massiv hajmini bittaga kamaytirib bordi. Bu narsa ham juda muhim, chunki bir xil argument bilan qayta-qayta murojaat qilinganda yoki argument notog'ri o'zgartirilganda funksiya o'zini cheksiz marta chaqirishiga to'g'ri kelib qoladi. Bu haqida ham batafsil yana gaplashamiz.
Nima uchun rekursiya kerak:
Aslini olganda, har qanday rekursiv ishlangan masalani iterativ usulda ishlash mumkin va buning aksi ham to'g'ri.Buning ustiga rekursiv yechim har doim xotiradan qo'shimcha joy talab qiladi.
Shunday ekan, nima uchun unda rekursiya kerak? Albatta, buning yetarlicha sabablari bor:
Rekursiya deyarli hamma joyda ishlatiladi. Ya'ni, lo'nda qilib aytganda undan qochib qutilishning iloji yo'q. Harakat qilib ko'rish esa qimmatga tushishi aniq )
Ba'zi holatlarda rekursiv yechim ancha soddaroq. Ayniqsa, ba'zi masalalarning iterativ yechimi juda ham uzun bo'lib ketishi mumkin. Rekursiya esa kodni bir necha barobar qisqartirib berishi mumkin.
Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib bo'lmaydi. Tree, Graph, Heap, QuickSort, MergeSort, … Bu ro'yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo'lgan Tree va Graphlarda rekursiya har qadamda uchraydi. Dasturchilikni esa ularsiz tasavvur qilib bo'lmaydi, bu esa o'z o'rnida rekursiya qanchalik muhimligini belgilab beradi.
Rekursiya funksional dasturlashning asosiy elementlaridan hisoblanadi. Hali funksional dasturlash haqida eshitmagan bo'lsangiz u haqida ma'lumot axtarib o'qib ko'rishni maslahat beraman. Bir so'z bilan aytganda, hozirda dasturlash sohasi jadallik bilan funksional dasturlash paradigmasi tomon ketmoqda (Go va Scala yorqin namunalar).
Yana bir qiziq ma'lumot, shunday dasturlash tillari borki ularda umuman takrorlanish operatorlari yo'q va bu borada butunlay rekursiyaga tayanadi. Haskell va Erlang shular jumlasidan.

Albatta, bularning barchasi rekursiyani takrorlash operatorlaridan butunlay ustunligini anglatmaydi. Aslida, ko'p hollarda dasturchilar rekursiya ishlatishdan qochishadi. Buning asosiy sabablari esa:

Rekursiya har doim xotiradan qo'shimcha joy talab qiladi. Bu haqida Call stack mavzumizda gaplashamiz. Rekursiv yechimda xato qilib ehtimoli yuqori. Avval ham aytganimizdek, rekursiya juda ham chalg'ituvchi. Shu sababli, uni ishlatishda osongina xato qilib qo'yish mumkin.
Rekursiv yechimni xatosini topish qiyin. Bunday masalalarda xato qilib qo'yish ehtimoli yuqori bo'lishi bilan birga uni topib to'g'irlash ham qiyin bo'lishi mumkin. Buning asosiy sababi, bunday yechimlarni tasavvur qilib olish (hayolan debug qilish) juda qiyin.
Rekursiv algoritmning murakkabligini hisoblash ko'pincha juda murakkab. Hattoki, ba'zan to'g'ri yechimni yozishning o'zi ham kam bo'lib qolishi mumkin. Chunki, uni iterativ yechim bilan solishtirishda uning murakkabligini hisoblash kerak bo'ladi. Rekursiv algoritmlarda bu ko'pincha juda murakkab va yaxshigina matematika talab qiladi.
2. Javada rekursiv funksiya.
Rekursiya - bu funktsiya chaqiruvining o'zini bajarish texnikasi. Ushbu usul murakkab muammolarni hal qilish osonroq bo'lgan oddiy muammolarga ajratish yo'lini beradi.
Rekursiyani tushunish biroz qiyin bo'lishi mumkin. Uning qanday ishlashini aniqlashning eng yaxshi yo'li u bilan tajriba o'tkazishdir.
Rekursiyaga misol
Ikki raqamni bir-biriga qo'shish oson, lekin bir qator raqamlarni qo'shish ancha murakkab. Quyidagi misolda, rekursiya bir qator raqamlarni ikkita raqamni qo'shish kabi oddiy vazifaga bo'lish orqali qo'shish uchun ishlatiladi:

3. Javada rekursiv funksiyaga misollar.

Misol
10 gacha bo'lgan barcha raqamlarni qo'shish uchun rekursiyadan foydalaning.
public class Main {
public static void main(String[] args) {
int result = sum(10);
System.out.println(result);
}
public static int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
}
Misol tushuntirildi
Sum() funksiyasi chaqirilganda, u k parametrini k dan kichik barcha raqamlar yig‘indisiga qo‘shadi va natijani qaytaradi. K=0 ga aylanganda, funksiya shunchaki 0 ​​ni qaytaradi. Ishlayotganda dastur quyidagi amallarni bajaradi:

10 + summa(9)

10 + ( 9 + yig'indisi(8) )
10 + ( 9 + ( 8 + yig'indisi(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + yig‘indisi(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
K 0 boʻlganda funksiya oʻzini chaqirmagani uchun dastur shu yerda toʻxtab, natijani qaytaradi.
To'xtash holati
Looplar cheksiz aylanish muammosiga duch kelganidek, rekursiv funksiyalar ham cheksiz rekursiya muammosiga duch kelishi mumkin. Cheksiz rekursiya - bu funksiya hech qachon o'zini chaqirishni to'xtatmaydi. Har bir rekursiv funktsiya to'xtash shartiga ega bo'lishi kerak, ya'ni funksiya o'zini chaqirishni to'xtatadigan shart. Oldingi misolda toʻxtash sharti k parametri 0 ga aylanganda hisoblanadi.
Kontseptsiyani yaxshiroq tushunish uchun turli xil misollarni ko'rish foydali bo'ladi. Ushbu misolda, funktsiya boshlanish va oxiri o'rtasida raqamlar oralig'ini qo'shadi. Bu rekursiv funksiyaning toʻxtash sharti end boshlash dan katta boʻlmaganda:
Misol
5 dan 10 gacha bo'lgan barcha raqamlarni qo'shish uchun rekursiyadan foydalaning.
public class Main {
public static void main(String[] args) {
int result = sum(5, 10);
System.out.println(result);
}
public static int sum(int start, int end) {
if (end > start) {
return end + sum(start, end - 1);
} else {
return end;
}
}
}
Ishlab chiquvchi rekursiya bilan juda ehtiyot bo'lishi kerak, chunki hech qachon tugamaydigan yoki ortiqcha xotira yoki protsessor quvvatini ishlatadigan funktsiyani yozish juda oson bo'lishi mumkin. Biroq, to'g'ri yozilsa, rekursiya dasturlashda juda samarali va matematik jihatdan oqlangan yondashuv bo'lishi mumkin.