Java tilidagi rekursiya bo'yicha bu chuqur o'quv qo'llanma Rekursiya nima ekanligini misollar, turlar va tegishli tushunchalar bilan tushuntiradi. Shuningdek, u Rekursiya va Iteratsiyani o'z ichiga oladi:
Java tilidagi oldingi darsliklarimizdan biz takroriy yondashuvni ko'rdik, bunda biz tsiklni e'lon qilamiz va keyin ma'lumotlar strukturasi bo'ylab iterativ usulda bitta elementni olib o'tamiz. vaqt.
Shartli oqimni ham ko'rdik, bunda yana bitta tsikl o'zgaruvchisini saqlab qolamiz va tsikl o'zgaruvchisi shartga javob berguncha kod qismini takrorlaymiz. Funksional chaqiruvlar haqida gap ketganda, biz funktsiya chaqiruvlari uchun ham iterativ yondashuvni o'rganib chiqdik.
Ushbu qo'llanmada biz dasturlashga boshqa yondashuvni, ya'ni Rekursiv yondashuvni muhokama qilamiz.
Java-da rekursiya nima?
Rekursiya - bu funksiya yoki usulning o'zini qayta-qayta chaqirishi jarayoni. To'g'ridan-to'g'ri yoki bilvosita qayta-qayta chaqiriladigan bu funksiya "rekursiv funktsiya" deb ataladi.
Rekursiyani tushunish uchun turli misollarni ko'ramiz. Endi rekursiya sintaksisini ko'rib chiqamiz.
Rekursiya sintaksisi
Rekursiyani amalga oshiradigan har qanday usul ikkita asosiy qismdan iborat:
- O'zini rekursiv deb atash mumkin bo'lgan usul qo'ng'irog'i
- Rekursiyani to'xtatadigan old shart.
E'tibor bering, har qanday rekursiv usul uchun old shart zarur, agar biz buni qilmasak sindirishrekursiya, keyin u cheksiz ishlashda davom etadi va stekning to'lib ketishiga olib keladi.
Rekursiyaning umumiy sintaksisi quyidagicha:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } E'tibor bering, oldingi shart ham deyiladi. asosiy holat. Biz keyingi bo'limda asosiy shart haqida ko'proq gaplashamiz.
Java-da rekursiyani tushunish
Ushbu bo'limda biz rekursiya jarayonini tushunishga harakat qilamiz va uning qanday sodir bo'lishini ko'ramiz. Biz bazaviy holat, stekning to‘lib ketishi haqida bilib olamiz va rekursiya va boshqa shu kabi tafsilotlar yordamida muayyan muammoni qanday yechish mumkinligini ko‘rib chiqamiz.
Rekursiyaning asosiy sharti
Rekursiv dasturni yozishda biz buni qilishimiz kerak. avval asosiy ish uchun yechimni taqdim eting. Keyin kattaroq masalani kichikroq masalalar bilan ifodalaymiz.
Misol sifatida sonning faktorialini hisoblashning klassik masalasini olishimiz mumkin. n soni berilgan bo‘lsa, n ning n bilan belgilangan faktorialini topishimiz kerak!
Endi rekursiya yordamida n faktorialni (n!) hisoblash dasturini amalga oshiramiz.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }Chiqish
Ushbu dasturda (n=1) shart asosiy shart ekanligini va bu shartga erishilganda funktsiya 1 ni qaytarishini ko'rishimiz mumkin. Funksiyaning boshqa qismi rekursiv chaqiruvdir. Ammo har safar rekursiv usul chaqirilganda, n 1 ga kamayadi.
Shunday qilib, n ning qiymati oxir-oqibat 1 ga yoki 1 dan kichik bo'ladi degan xulosaga kelishimiz mumkin.nuqta, usul 1-qiymatni qaytaradi. Ushbu asosiy shartga erishiladi va funktsiya to'xtaydi. E'tibor bering, n ning qiymati asosiy shartni qondirar ekan, har qanday bo'lishi mumkin.
Rekursiyadan foydalanib muammoni yechish
Rekursiyadan foydalanishning asosiy g'oyasi kattaroq muammoni quyidagi shartlar bilan ifodalashdir. kichikroq muammolar. Bundan tashqari, biz rekursiyadan chiqishimiz uchun bir yoki bir nechta asosiy shartlarni qo'shishimiz kerak.
Bu yuqoridagi faktorial misolda allaqachon ko'rsatilgan. Bu dasturda biz n faktorialni (n!) kichikroq qiymatlar bilan ifodaladik va asosiy shartga (n =1) ega bo'ldik, shunda n 1 ga yetganda rekursiv usuldan chiqishimiz mumkin.
Rekursiyadagi stekning to'lib ketishi xatosi
Biz bilamizki, har qanday usul yoki funksiya chaqirilganda, funktsiya holati stekda saqlanadi va funksiya qaytib kelganda olinadi. Stek rekursiv usul uchun ham ishlatiladi.
Ammo rekursiya holatida, agar biz asosiy shartni aniqlamasak yoki asosiy shartga qandaydir tarzda erishilmasa yoki bajarilmasa, muammo yuzaga kelishi mumkin. Agar bu holat yuzaga kelsa, stek to'lib ketishi mumkin.
Keling, faktoriy belgilanishning quyidagi misolini ko'rib chiqamiz.
Bu erda biz noto'g'ri asosiy shartni berdik, n==100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }Demak, n > 100, usul 1 ni qaytaradi, lekin rekursiya to'xtamaydi. n qiymati u erda bo'lgani kabi cheksiz ravishda kamayishda davom etadito'xtatish uchun boshqa shart emas. Bu stek oshib ketguncha davom etadi.
Boshqa holat n qiymati 100. Bu holda, shuningdek, usul hech qachon asosiy shartni bajarmaydi va stekning to'lib ketishiga olib keladi.
Java-dagi rekursiya misollari
Ushbu bo'limda biz quyidagi misollarni ishlatib amalga oshiramiz. rekursiya.
#1) Rekursiyadan foydalangan holda Fibonachchi seriyasi
Fibonachchi qatori berilgan,
1,1,2,3,5,8,13,21, 34,55,...
Yuqoridagi ketma-ketlik joriy element oldingi ikki elementning yig'indisi ekanligini ko'rsatadi. Shuningdek, Fibonachchi qatoridagi birinchi element 1 ga teng.
Demak, umuman olganda, agar n joriy son bo'lsa, u (n-1) va (n-2) yig'indisi bilan beriladi. Joriy element oldingi elementlar bilan ifodalanganligi uchun biz bu masalani rekursiya yordamida ifodalashimiz mumkin.
Fibonachchi qatorini amalga oshirish dasturi quyida keltirilgan:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n = 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i = number; i++) { System.out.print(fibonacci(i) + " "); } } } Chiqish
#2) Rekursiya yordamida son palindrom ekanligini tekshiring
Palindrom bu biz teng bo'lgan ketma-ketlikdir. uni chapdan o'ngga yoki o'ngdan chapga o'qing.
121 raqami berilgan bo'lsa, biz uni chapdan o'ngga va o'ngdan chapga o'qiganimizda teng ekanligini ko'ramiz. Demak, 121 raqami palindromdir.
Boshqa raqamni olaylik, 1242. Uni chapdan o'ngga o'qiganimizda 1242, o'ngdan chapga o'qiganimizda esa 2421 bo'ladi. Demak, bu palindrom emas.
Bizpalindrom dasturini raqamlarning raqamlarini teskari aylantirish orqali amalga oshiring va berilgan sonni uning teskari ko'rinishiga rekursiv taqqoslang.
Quyidagi dastur palindromni tekshirish dasturini amalga oshiradi.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num 10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } } }Chiqish
#3) Teskari satr rekursiyasi Java
“Salom” qatori berilgan boʻlsa, biz uni teskari aylantirishimiz kerak, shunda natija qatori “olleH”.
Bu rekursiya yordamida amalga oshiriladi. Satrdagi oxirgi belgidan boshlab, satrdagi barcha belgilar tugaguncha har bir belgini rekursiv chop qilamiz.
Quyidagi dastur berilgan satrni teskari aylantirish uchun rekursiyadan foydalanadi.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() = 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("The given string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } Chiqish
#4) Ikkilik qidiruv Java rekursiyasi
Ikkilik qidiruv algoritmi qidiruv uchun mashhur algoritmdir. Ushbu algoritmda n ta elementdan iborat tartiblangan massiv berilgan holda, biz ushbu massivdan berilgan kalit elementni qidiramiz. Boshida massivning oʻrta elementini topib, massivni ikkiga boʻlamiz.
Keyin oʻrtadagi kalitga qarab biz qidiruvimizni massivning birinchi yoki ikkinchi yarmida cheklaymiz. Shu tarzda asosiy elementlarning joylashuvi topilmaguncha xuddi shu jarayon takrorlanadi.
Biz bu algoritmni bu yerda rekursiya yordamida amalga oshiramiz.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } Chiqish
#5) Rekursiya yordamida massivning minimal qiymatini toping
Rekursiyadan foydalanib, massivdagi minimal qiymatni ham topishimiz mumkin.
TheMassivdagi minimal qiymatni topish uchun Java dasturi quyida keltirilgan.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Given Array : " + Arrays.toString(numArray)); int n = numArray.length; System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); } }Chiqish
Bularning ba'zilari. rekursiyaga misollar. Ushbu misollardan tashqari, dasturiy ta'minotdagi boshqa ko'plab muammolarni rekursiv texnikalar yordamida amalga oshirish mumkin.
Rekursiya turlari
Rekursiya ikki xil bo'ladi. rekursiv usul.
Ular:
#1) Quyruq rekursiyasi
Rekursiv usulga chaqiruv oxirgi bayonot bo'lganda. rekursiv usul ichida bajariladi, u “Tail Recursion” deb ataladi.
Quyruq rekursiyasida rekursiv chaqiruv operatori odatda usulning qaytish bayonoti bilan birga bajariladi.
Quyruq rekursiyasi uchun umumiy sintaksis quyida keltirilgan:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Bosh rekursiyasi
Bosh rekursiya - bu quyruq rekursiyasi bo'lmagan har qanday rekursiv yondashuv. Demak, hatto umumiy rekursiya ham oldingi rekursiyadir.
Bosh rekursiyaning sintaksisi quyidagicha:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Rekursiya va Java-dagi iteratsiya
| Rekursiya | Iteratsiya |
|---|---|
| Rekursiya - bu asosiy shart bajarilmaguncha usul o'zini qayta-qayta chaqiradigan jarayon. | Iteratsiya - bu kod qismi chekli marta yoki shart bajarilgunga qadar qayta-qayta bajariladigan jarayon. |
| Funksiyalar uchun ilovami. | Qoʻllaniladi for loops. |
| For uchun yaxshi ishlaydikichikroq kod o'lchami. | Kattaroq kod hajmi uchun yaxshi ishlaydi. |
| Har bir rekursiv qo'ng'iroq stekga yuborilganda ko'proq xotiradan foydalanadi | Nisobdan kamroq xotira ishlatiladi. |
| Nosozliklarni tuzatish va texnik xizmat ko‘rsatish qiyin | Nosozliklarni tuzatish va saqlash osonroq |
| Agar baza o‘rnatilgan bo‘lsa, stekning to‘lib ketishiga olib keladi. shart belgilanmagan yoki erishilmagan. | Cheksiz bajarilishi mumkin, lekin oxir-oqibat har qanday xotira xatosi bilan ishlashni to'xtatadi |
| Vaqt murakkabligi juda yuqori. | Vaqt murakkabligi nisbatan pastroq tomonda. |
Tez-tez so'raladigan savollar
Savol №1) Java'da Rekursiya qanday ishlaydi?
Javob: Rekursiyada rekursiv funktsiya asosiy shart bajarilmaguncha o'zini qayta-qayta chaqiradi. Chaqirilayotgan funksiya uchun xotira chaqiruvchi funksiya uchun xotiraning yuqori qismidagi stekga suriladi. Har bir funktsiya chaqiruvi uchun mahalliy o'zgaruvchilarning alohida nusxasi tuziladi.
2-savol) Rekursiya nima uchun ishlatiladi?
Javob: Rekursiya kichikroq masalalarga bo'linishi mumkin bo'lgan masalalarni hal qilish uchun ishlatiladi va butun muammo kichikroq masala shaklida ifodalanishi mumkin.
Rekursiya juda katta bo'lgan masalalar uchun ham qo'llaniladi. iterativ yondashuv yordamida hal qilinadigan murakkab. Vaqtning murakkabligi muammo bo'lmagan muammolardan tashqari, rekursiyadan foydalaning.
3-savol) Qanday foyda bor?Rekursiya?
Javob:
Rekursiyaning afzalliklari quyidagilardan iborat:
- Rekursiya ortiqcha qo'ng'iroqlarni kamaytiradi. funktsiyaning.
- Rekursiya iterativ yondashuv bilan solishtirganda muammolarni oson yechish imkonini beradi.
Savol №4) Qaysi biri yaxshiroq – Rekursiya yoki Iteratsiya?
Javob: Rekursiya asosiy funktsiyaga erishilgunga qadar takroriy qo'ng'iroqlarni amalga oshiradi. Shunday qilib, har bir funktsiya chaqiruvi uchun xotira stekga surilganligi sababli xotira yuki bo'ladi.
Iteratsiya esa, ko'p xotira yukiga ega emas. Rekursiyaning bajarilishi iterativ yondashuvga qaraganda sekinroq. Rekursiya kod hajmini kamaytiradi, iterativ yondashuv esa kodni katta qiladi.
Savol №5) Rekursiyaning iteratsiyaga nisbatan qanday afzalliklari bor?
Javob:
- Rekursiya kodni aniqroq va qisqaroq qiladi.
- Rekursiya Xanoy minorasi, daraxt kabi muammolar uchun iterativ yondashuvdan yaxshiroqdir. o'tish va h.k.
- Har bir funktsiya chaqiruvida xotira stekga surilganligi sababli, Rekursiya ko'proq xotiradan foydalanadi.
- Rekursiya ishlashi iterativ yondashuvga qaraganda sekinroq.
Xulosa
Rekursiya dasturlash tilidan qat'i nazar, dasturiy ta'minotda juda muhim tushunchadir. Rekursiya asosan Xanoy minoralari, daraxtlarni kesib o'tish, bog'langan ro'yxatlar va boshqalar kabi ma'lumotlar tuzilmasi muammolarini hal qilishda qo'llaniladi. Ko'proq xotira talab qilsa-da,rekursiya kodni sodda va tushunarli qiladi.
Biz ushbu qoʻllanmada Rekursiya haqida hamma narsani oʻrganib chiqdik. Kontseptsiyani yaxshiroq tushunish uchun biz ko'plab dasturlash misollarini ham amalga oshirdik.