Java-da Rekursiya üzrə Bu Dərin Dərslik Nümunələr, Növlər və Əlaqədar Konseptlər ilə Rekursiyanın nə olduğunu izah edir. O, həmçinin Rekursiya Vs İterasiyanı əhatə edir:
Əvvəlki Java dərsliklərimizdən biz döngə elan etdiyimiz və sonra bir elementi götürərək iterativ şəkildə verilənlər strukturundan keçdiyimiz iterativ yanaşmanı gördük. vaxt.
Biz həmçinin şərti axını gördük, burada yenə bir dövrə dəyişənini saxlayırıq və döngə dəyişəni şərtə cavab verənə qədər kod parçasını təkrar edirik. Funksiya çağırışlarına gəldikdə, biz funksiya çağırışları üçün də iterativ yanaşmanı araşdırdıq.
Bu dərslikdə biz proqramlaşdırmaya fərqli yanaşmanı, yəni Rekursiv yanaşmanı müzakirə edəcəyik.
Java-da Rekursiya Nədir?
Rekursiya funksiya və ya metodun özünü təkrar-təkrar çağırması prosesidir. Təkrar və ya birbaşa və ya dolayı yolla çağırılan bu funksiya “rekursiv funksiya” adlanır.
Rekursiyanı başa düşmək üçün müxtəlif nümunələrə baxacağıq. İndi rekursiyanın sintaksisinə baxaq.
Rekursiya sintaksisi
Rekursiyanı həyata keçirən istənilən metod iki əsas hissədən ibarətdir:
- Özünü rekursiv adlandıra bilən metod çağırışı
- Rekursiyanı dayandıracaq ilkin şərt.
Qeyd edək ki, hər hansı rekursiv metod üçün ilkin şərt zəruridir, əgər biz bunu etməsək qırmaqrekursiya, o zaman sonsuz işləməyə davam edəcək və yığının daşması ilə nəticələnəcək.
Rekursiyanın ümumi sintaksisi aşağıdakı kimidir:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Qeyd edək ki, ilkin şərt də adlanır. baza vəziyyəti. Biz növbəti bölmədə əsas şərt haqqında daha çox danışacağıq.
Java-da rekursiyanı başa düşmək
Bu bölmədə biz rekursiya prosesini anlamağa və onun necə baş verdiyini görməyə çalışacağıq. Biz baza vəziyyəti, stek daşması haqqında öyrənəcəyik və konkret problemin rekursiya və digər bu kimi təfərrüatlarla necə həll oluna biləcəyini görəcəyik.
Rekursiya Baza Şərti
Rekursiv proqramı yazarkən biz bunu etməliyik. əvvəlcə əsas işin həllini təmin edin. Sonra daha böyük problemi daha kiçik məsələlərlə ifadə edirik.
Misal olaraq, ədədin faktorialının hesablanmasına dair klassik məsələni götürə bilərik. Verilmiş n ədədi, n ilə işarələnən n faktorialını tapmalıyıq!
İndi rekursiyadan istifadə edərək n faktorialının (n!) hesablanması proqramını həyata keçirək.
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); } }Çıxış
Bu proqramda (n=1) şərtin əsas şərt olduğunu və bu şərtə çatdıqda funksiyanın 1-i qaytardığını görə bilərik. Funksiyanın digər hissəsi rekursiv çağırışdır. Lakin hər dəfə rekursiv metod çağırılanda n 1 azalır.
Beləliklə, belə nəticəyə gələ bilərik ki, nəticədə n-in dəyəri 1 və ya 1-dən kiçik olacaq və bu zamannöqtə, metod 1 dəyərini qaytaracaq. Bu əsas şərtə çatılacaq və funksiya dayanacaq. Nəzərə alın ki, n dəyəri əsas şərti ödədiyi müddətcə istənilən ola bilər.
Rekursiyadan istifadə edərək problemin həlli
Rekursiyadan istifadənin əsas ideyası daha böyük problemi aşağıdakı ifadələrlə ifadə etməkdir. daha kiçik problemlər. Həmçinin, bir və ya bir neçə əsas şərti əlavə etməliyik ki, rekursiyadan çıxa bilək.
Bu, yuxarıdakı faktorial nümunədə artıq nümayiş etdirilib. Bu proqramda biz n faktorialını (n!) kiçik qiymətlərlə ifadə etdik və əsas şərtə (n =1) malik olduq ki, n 1-ə çatdıqda rekursiv metoddan çıxa bilək.
Rekursiyada yığının daşması xətası
Biz bilirik ki, hər hansı metod və ya funksiya çağırıldıqda, funksiyanın vəziyyəti stekdə saxlanılır və funksiya geri qayıtdıqda geri alınır. Stek rekursiv metod üçün də istifadə olunur.
Lakin rekursiya vəziyyətində, əgər biz əsas şərti təyin etməsək və ya əsas şərtə hansısa şəkildə çatılmadıqda və ya yerinə yetirilmədikdə problem yarana bilər. Bu vəziyyət baş verərsə, yığının daşması baş verə bilər.
Aşağıdakı faktorial qeyd nümunəsini nəzərdən keçirək.
Burada səhv əsas şərt vermişik, 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); } }Beləliklə, n > 100 metodu 1 qaytaracaq, lakin rekursiya dayanmayacaq. n-nin dəyəri burada olduğu kimi qeyri-müəyyən müddətə azalmağa davam edəcəkdirdayandırmaq üçün başqa şərt yoxdur. Bu, yığın daşana qədər davam edəcək.
Digər hal n dəyərinin 100. Bu halda, metod heç vaxt əsas şərti yerinə yetirməyəcək və stek daşması ilə nəticələnməyəcək.
Java-da Rekursiya Nümunələri
Bu bölmədə biz aşağıdakı nümunələri istifadə edərək həyata keçirəcəyik. rekursiya.
#1) Rekursiyadan istifadə edən Fibonaççi seriyası
Fibonaççi seriyası,
1,1,2,3,5,8,13,21, 34,55,...
Yuxarıdakı ardıcıllıq cari elementin əvvəlki iki elementin cəmi olduğunu göstərir. Həmçinin, Fibonaççi seriyasının birinci elementi 1-dir.
Beləliklə, əgər n cari ədəddirsə, o zaman (n-1) və (n-2) cəmi ilə verilir. Cari element əvvəlki elementlərlə ifadə edildiyi üçün biz bu problemi rekursiyadan istifadə etməklə ifadə edə bilərik.
Fibonaççi seriyasını həyata keçirmək üçün proqram aşağıda verilmişdir:
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) + " "); } } } Çıxış
#2) Rekursiyadan istifadə edərək ədədin palindrom olub-olmadığını yoxlayın
Palindrom, biz olduqda bərabər olan ardıcıllıqdır. onu soldan sağa və ya sağdan sola oxuyun.
121 rəqəmi verildikdə onu soldan sağa və sağdan sola oxuduqda bərabər olduğunu görürük. Deməli, 121 rəqəmi palindromdur.
Başqa rəqəm götürək, 1242. Onu soldan sağa oxuduqda 1242, sağdan sola oxuduqda isə 2421 kimi oxunur. Beləliklə, bu palindrom deyil.
Bizədədlərin rəqəmlərini tərsinə çevirməklə palindrom proqramını həyata keçirin və verilmiş ədədi onun əks təsviri ilə rekursiv müqayisə edin.
Aşağıdakı proqram palindromu yoxlamaq proqramını həyata keçirir.
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."); } } }Çıxış
#3) Ters sətir rekursiyası Java
“Salam” sətri verildikdə biz onu tərsinə çevirməliyik ki, nəticə sətri “olleH”dir.
Bu, rekursiyadan istifadə etməklə həyata keçirilir. Sətirdəki son simvoldan başlayaraq sətirdəki bütün simvollar tükənənə qədər hər simvolu rekursiv çap edirik.
Aşağıdakı proqram verilmiş sətri tərsinə çevirmək üçün rekursiyadan istifadə edir.
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); } } Çıxış
#4) Binar Axtarış Java Rekursiyası
İkili axtarış alqoritmi məşhur axtarış alqoritmidir. Bu alqoritmdə n elementdən ibarət çeşidlənmiş massiv verildikdə, biz bu massivdə verilmiş əsas elementi axtarırıq. Başlanğıcda, massivin orta elementini tapmaqla massivi iki yarıya bölürük.
Sonra açarın orta olub-olmamasından asılı olaraq, axtarışımızı massivin birinci və ya ikinci yarısında məhdudlaşdırırıq. Bu yolla eyni proses əsas elementlərin yeri tapılana qədər təkrarlanır.
Bu alqoritmi burada rekursiyadan istifadə edərək həyata keçirəcəyik.
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); } } Çıxış
#5) Rekursiyadan istifadə edərək Massivdə Minimum Dəyəri Tapın
Rekursiyadan istifadə edərək massivdə minimum dəyəri də tapa bilərik.
TheMassivdə minimum dəyəri tapmaq üçün Java proqramı aşağıda verilmişdir.
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"); } }Çıxış
Bunlardan bəziləri rekursiya nümunələri. Bu nümunələrdən başqa, proqram təminatındakı bir çox başqa problemlər rekursiv üsullardan istifadə etməklə həyata keçirilə bilər.
Rekursiya növləri
Rekursiya zəng edildiyi zamandan asılı olaraq iki növdür. rekursiv metod.
Onlar:
#1) Quyruq Rekursiya
Rekursiv metoda çağırış sonuncu ifadə olduqda rekursiv metod daxilində icra edilir, o, “Tail Recursion” adlanır.
Quyruq rekursiyasında rekursiv çağırış ifadəsi adətən metodun qaytarma ifadəsi ilə birlikdə yerinə yetirilir.
quyruq rekursiyası üçün ümumi sintaksis aşağıda verilmişdir:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Baş rekursiyası
Baş rekursiyası quyruq rekursiyası olmayan hər hansı rekursiv yanaşmadır. Beləliklə, hətta ümumi rekursiya qabaqda olan rekursiyadır.
Baş rekursiyasının sintaksisi aşağıdakı kimidir:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Java-da Rekursiya və İterasiya
| Rekursiya | İterasiya |
|---|---|
| Rekursiya əsas şərt yerinə yetirilənə qədər metodun təkrar özünü çağırdığı prosesdir. | İterasiya kod parçasının sonlu sayda dəfə və ya şərt yerinə yetirilənə qədər təkrar icra olunduğu proses. |
| Funksiyalar üçün tətbiqdir. | Tətbiq olunur for loops. |
| Üçün yaxşı işləyirdaha kiçik kod ölçüsü. | Daha böyük kod ölçüsü üçün yaxşı işləyir. |
| Hər rekursiv çağırış yığına köçürüldükdə daha çox yaddaş istifadə edir | Nisbətən daha az yaddaş istifadə olunur. |
| Debug və saxlanması çətindir | Debug və saxlanması daha asan |
| Bazada stek daşması ilə nəticələnir. şərt göstərilməyib və ya əldə olunmayıb. | Sonsuz icra edə bilər, lakin nəticədə hər hansı yaddaş xətası ilə icranı dayandıracaq |
| Vaxt mürəkkəbliyi çox yüksəkdir. | Zamanın mürəkkəbliyi nisbətən aşağı tərəfdədir. |
Tez-tez verilən suallar
S #1) Java-da Rekursiya necə işləyir?
Cavab: Rekursiyada rekursiv funksiya əsas şərt ödənilənə qədər özünü təkrar-təkrar çağırır. Çağırılan funksiya üçün yaddaş zəng funksiyası üçün yaddaşın yuxarı hissəsindəki yığına itələnir. Hər bir funksiya çağırışı üçün lokal dəyişənlərin ayrıca nüsxəsi hazırlanır.
Q #2) Rekursiya nə üçün istifadə olunur?
Cavab: Rekursiya kiçik olanlara bölünə bilən və bütün problem daha kiçik problemlə ifadə oluna bilən problemləri həll etmək üçün istifadə olunur.
Rekursiya çox böyük olan problemlər üçün də istifadə olunur. iterativ yanaşmadan istifadə etməklə həll ediləcək kompleks. Zamanın mürəkkəbliyi problemi olmayan problemlərlə yanaşı, rekursiyadan istifadə edin.
Q #3) Nə faydaları varRekursiya?
Cavab:
Rekursiyanın üstünlüklərinə aşağıdakılar daxildir:
- Rekursiya lazımsız çağırışları azaldır funksiyasının.
- Rekursiya iterativ yanaşma ilə müqayisədə problemləri asanlıqla həll etməyə imkan verir.
S №4) Hansı daha yaxşıdır – Rekursiya yoxsa İterasiya?
Cavab: Rekursiya əsas funksiyaya çatana qədər təkrar zənglər edir. Beləliklə, hər bir funksiya çağırışı üçün yaddaş stek üzərinə itələndiyi üçün yaddaş yükü yaranır.
İterasiya isə çox yaddaş yükünə malik deyil. Rekursiyanın icrası iterativ yanaşmadan daha yavaşdır. Rekursiya kodun ölçüsünü azaldır, iterativ yanaşma isə kodu böyük edir.
Q #5) Rekursiyanın İterasiyaya nisbətən üstünlükləri nələrdir?
Cavab:
- Rekursiya kodu daha aydın və qısa edir.
- Rekursiya Hanoy Qülləsi, ağac kimi problemlər üçün iterativ yanaşmadan daha yaxşıdır. keçidlər və s.
- Hər funksiya çağırışında yaddaş yığına itələndiyi üçün Rekursiya daha çox yaddaş istifadə edir.
- Rekursiya performansı iterativ yanaşmadan daha yavaşdır.
Nəticə
Rekursiya proqramlaşdırma dilindən asılı olmayaraq proqram təminatında çox vacib anlayışdır. Rekursiya əsasən Hanoy qüllələri, ağac keçidləri, əlaqəli siyahılar və s. kimi verilənlər strukturu problemlərinin həllində istifadə olunur. Daha çox yaddaş tələb etsə də,rekursiya kodu daha sadə və aydın edir.
Biz bu dərslikdə Rekursiya haqqında hər şeyi araşdırdıq. Konsepsiyanı daha yaxşı başa düşmək üçün çoxlu proqramlaşdırma nümunələri də tətbiq etdik.