ეს სიღრმისეული გაკვეთილი ჯავაში რეკურსიის შესახებ განმარტავს რა არის რეკურსია მაგალითებით, ტიპებითა და დაკავშირებული ცნებებით. ის ასევე მოიცავს Recursion vs Iteration:
ჩვენი ადრინდელი გაკვეთილებიდან Java-ში, ჩვენ ვნახეთ განმეორებითი მიდგომა, რომლის დროსაც ჩვენ ვაცხადებთ ციკლს და შემდეგ გავდივართ მონაცემთა სტრუქტურაში განმეორებითი გზით, ერთი ელემენტის აღებით დრო.
ჩვენ ასევე ვნახეთ პირობითი ნაკადი, სადაც კვლავ ვინახავთ ერთ მარყუჟის ცვლადს და ვიმეორებთ კოდის ნაწილს მანამ, სანამ მარყუჟის ცვლადი დააკმაყოფილებს პირობას. რაც შეეხება ფუნქციის გამოძახებას, ჩვენ გამოვიკვლიეთ ფუნქციის გამოძახების განმეორებითი მიდგომაც.
ამ გაკვეთილზე განვიხილავთ პროგრამირების განსხვავებულ მიდგომას, ანუ რეკურსიულ მიდგომას.
რა არის რეკურსია ჯავაში?
რეკურსია არის პროცესი, რომლითაც ფუნქცია ან მეთოდი კვლავ და ისევ იძახებს საკუთარ თავს. ამ ფუნქციას, რომელიც იწოდება ისევ და ისევ პირდაპირ ან ირიბად, ეწოდება "რეკურსიული ფუნქცია".
ჩვენ ვნახავთ სხვადასხვა მაგალითებს რეკურსიის გასაგებად. ახლა ვნახოთ რეკურსიის სინტაქსი.
რეკურსიის სინტაქსი
ნებისმიერი მეთოდი, რომელიც ახორციელებს რეკურსიას, აქვს ორი ძირითადი ნაწილი:
- მეთოდის გამოძახება, რომელსაც შეუძლია თავის თავს უწოდოს ე.ი. რეკურსიული
- წინაპირობა, რომელიც შეაჩერებს რეკურსიას.
გაითვალისწინეთ, რომ წინაპირობა აუცილებელია ნებისმიერი რეკურსიული მეთოდისთვის, თუ ჩვენ არ გავაკეთებთ დაარღვიერეკურსიის შემდეგ ის გააგრძელებს მუშაობას უსასრულოდ და გამოიწვევს სტეკის გადაფარვას.
რეკურსიის ზოგადი სინტაქსი ასეთია:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } გაითვალისწინეთ, რომ წინაპირობა ასევე ე.წ. ბაზის მდგომარეობა. საბაზისო მდგომარეობის შესახებ უფრო მეტს განვიხილავთ შემდეგ განყოფილებაში.
რეკურსიის გაგება Java-ში
ამ განყოფილებაში შევეცდებით გავიგოთ რეკურსიის პროცესი და ვნახოთ, როგორ ხდება იგი. ჩვენ გავეცნობით საბაზისო მდგომარეობას, სტეკის გადინებას და ვნახავთ, როგორ შეიძლება კონკრეტული პრობლემის გადაჭრა რეკურსიით და სხვა მსგავსი დეტალებით.
რეკურსიის საბაზისო მდგომარეობა
რეკურსიული პროგრამის დაწერისას, ჩვენ უნდა პირველ რიგში მიეცით გამოსავალი საბაზისო საქმისთვის. შემდეგ ჩვენ გამოვხატავთ უფრო დიდ პრობლემას მცირე ამოცანების მიხედვით.
როგორც მაგალითი, შეგვიძლია ავიღოთ რიცხვის ფაქტორების გამოთვლის კლასიკური ამოცანა. მოცემული რიცხვი n, ჩვენ უნდა ვიპოვოთ n-ის ფაქტორიალი, რომელიც აღინიშნება n-ით!
ახლა განვახორციელოთ პროგრამა, რომ გამოვთვალოთ n ფაქტორიალი (n!) რეკურსიის გამოყენებით.
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); } }გამომავალი
ამ პროგრამაში ჩვენ ვხედავთ, რომ პირობა (n=1) არის საბაზისო პირობა და როდესაც ეს მდგომარეობა მიიღწევა, ფუნქცია აბრუნებს 1-ს. ფუნქციის სხვა ნაწილი არის რეკურსიული ზარი. მაგრამ ყოველ ჯერზე, როცა რეკურსიული მეთოდი გამოიძახება, n მცირდება 1-ით.
ამგვარად შეგვიძლია დავასკვნათ, რომ საბოლოო ჯამში n-ის მნიშვნელობა გახდება 1 ან 1-ზე ნაკლები და ამ დროსწერტილი, მეთოდი დააბრუნებს მნიშვნელობას 1. ეს საბაზისო მდგომარეობა მიიღწევა და ფუნქცია შეჩერდება. გაითვალისწინეთ, რომ n-ის მნიშვნელობა შეიძლება იყოს ნებისმიერი რამ, სანამ ის აკმაყოფილებს საბაზისო პირობას.
პრობლემის გადაჭრა რეკურსიის გამოყენებით
რეკურსიის გამოყენების ძირითადი იდეა არის უფრო დიდი პრობლემის გამოხატვა უფრო მცირე პრობლემები. ასევე, ჩვენ უნდა დავამატოთ ერთი ან მეტი საბაზისო პირობა, რათა გამოვიდეთ რეკურსიიდან.
ეს უკვე აჩვენა ზემოთ მოცემულ ფაქტორულ მაგალითში. ამ პროგრამაში ჩვენ გამოვხატეთ n ფაქტორიალი (n!) უფრო მცირე მნიშვნელობებით და გვქონდა საბაზისო პირობა (n =1), ასე რომ, როდესაც n მიაღწევს 1-ს, შეგვიძლია გამოვტოვოთ რეკურსიული მეთოდი.
Stack Overflow Error In Recursion
ჩვენ ვიცით, რომ ნებისმიერი მეთოდის ან ფუნქციის გამოძახებისას, ფუნქციის მდგომარეობა ინახება დასტაზე და აღიქმება ფუნქციის დაბრუნებისას. სტეკი გამოიყენება რეკურსიული მეთოდისთვისაც.
მაგრამ რეკურსიის შემთხვევაში, პრობლემა შეიძლება წარმოიშვას, თუ არ განვსაზღვრავთ საბაზისო მდგომარეობას ან როდესაც საბაზისო მდგომარეობა რატომღაც არ არის მიღწეული ან შესრულებული. თუ ეს სიტუაცია მოხდა, შეიძლება წარმოიშვას სტეკის გადინება.
მოდით განვიხილოთ ფაქტორული აღნიშვნის ქვემოთ მოცემული მაგალითი.
აქ ჩვენ მივეცით არასწორი საბაზისო პირობა, 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); } }ასე რომ, როდესაც n > 100 მეთოდი დააბრუნებს 1-ს, მაგრამ რეკურსია არ შეჩერდება. n-ის მნიშვნელობა განუსაზღვრელი ვადით მცირდება, როგორც იქსხვა პირობა არ არის მის შესაჩერებლად. ეს გაგრძელდება მანამ, სანამ დასტა არ გადაიწურება.
სხვა შემთხვევა იქნება, როდესაც მნიშვნელობა n 100. ამ შემთხვევაშიც, მეთოდი არასოდეს შეასრულებს საბაზისო მდგომარეობას და გამოიწვევს სტეკის გადატვირთვას.
რეკურსიის მაგალითები Java-ში
ამ განყოფილებაში განვახორციელებთ შემდეგ მაგალითებს გამოყენებით რეკურსია.
#1) ფიბონაჩის სერიები რეკურსიის გამოყენებით
ფიბონაჩის სერია მოცემულია,
1,1,2,3,5,8,13,21, 34,55,…
ზემოხსენებული თანმიმდევრობა აჩვენებს, რომ მიმდინარე ელემენტი არის წინა ორი ელემენტის ჯამი. ასევე, ფიბონაჩის სერიების პირველი ელემენტია 1.
ასე რომ ზოგადად, თუ n არის მიმდინარე რიცხვი, მაშინ იგი მოცემულია (n-1) და (n-2) ჯამით. ვინაიდან მიმდინარე ელემენტი გამოიხატება წინა ელემენტებით, ჩვენ შეგვიძლია გამოვხატოთ ეს პრობლემა რეკურსიის გამოყენებით.
ფიბონაჩის სერიის განხორციელების პროგრამა მოცემულია ქვემოთ:
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) + " "); } } } გამომავალი
#2) შეამოწმეთ არის თუ არა რიცხვი პალინდრომი რეკურსიის გამოყენებით
პალინდრომი არის მიმდევრობა, რომელიც ტოლია, როდესაც ჩვენ წაიკითხეთ იგი მარცხნიდან მარჯვნივ ან მარჯვნიდან მარცხნივ.
121 რიცხვის გათვალისწინებით, ჩვენ ვხედავთ, რომ როდესაც ვკითხულობთ მარცხნიდან მარჯვნივ და მარჯვნიდან მარცხნივ, ის ტოლია. მაშასადამე, რიცხვი 121 არის პალინდრომი.
ავიღოთ სხვა რიცხვი, 1242. როცა მას მარცხნიდან მარჯვნივ ვკითხულობთ, არის 1242, ხოლო როდესაც წავიკითხავთ მარჯვნიდან მარცხნივ, იკითხება როგორც 2421. ამრიგად, ეს არ არის პალინდრომი.
ჩვენგანახორციელეთ პალინდრომის პროგრამა რიცხვების ციფრების შებრუნებით და რეკურსიულად შეადარეთ მოცემული რიცხვი მის შებრუნებულ წარმოდგენას.
ქვემოთ მოცემული პროგრამა ახორციელებს პროგრამას პალინდრომის შესამოწმებლად.
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."); } } }გამომავალი
#3) საპირისპირო სტრიქონის რეკურსია Java
სტრიქონის "Hello"-ს მიცემით, ჩვენ უნდა შევცვალოთ ის ისე, რომ შედეგიანი სტრიქონი არის "olleH".
ეს კეთდება რეკურსიის გამოყენებით. სტრიქონის ბოლო სიმბოლოდან დაწყებული, ჩვენ რეკურსიულად ვბეჭდავთ თითოეულ სიმბოლოს, სანამ სტრიქონის ყველა სიმბოლო არ ამოიწურება.
ქვემოთ მოცემული პროგრამა იყენებს რეკურსიას მოცემული სტრიქონის დასაბრუნებლად.
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); } } გამომავალი
#4) ორობითი ძებნა Java Recursion
ორობითი ძიების ალგორითმი არის ძებნის ცნობილი ალგორითმი. ამ ალგორითმში, მოცემული n ელემენტის დახარისხებული მასივის გათვალისწინებით, ამ მასივში ვეძებთ მოცემულ საკვანძო ელემენტს. დასაწყისში მასივს ორ ნაწილად ვყოფთ მასივის შუა ელემენტის მოძიებით.
შემდეგ, იმის მიხედვით, არის თუ არა გასაღები შუა, ჩვენ ვზღუდავთ ძიებას მასივის პირველ ან მეორე ნახევარში. ამ გზით იგივე პროცესი მეორდება მანამ, სანამ არ მოიძებნება ძირითადი ელემენტების მდებარეობა.
ამ ალგორითმს განვახორციელებთ აქ რეკურსიის გამოყენებით.
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); } } გამომავალი
#5) იპოვეთ მინიმალური მნიშვნელობა მასივში რეკურსიის გამოყენებით
რეკურსიის გამოყენებით ჩვენ ასევე შეგვიძლია ვიპოვოთ მინიმალური მნიშვნელობა მასივში.
0> მასივში მინიმალური მნიშვნელობის საპოვნელად Java პროგრამა მოცემულია ქვემოთ.
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"); } }გამომავალი
ეს არის რამდენიმე რეკურსიის მაგალითები. ამ მაგალითების გარდა, პროგრამულ უზრუნველყოფაში ბევრი სხვა პრობლემის დანერგვა შესაძლებელია რეკურსიული ტექნიკის გამოყენებით.
რეკურსიის ტიპები
რეკურსიის ორი ტიპია, იმის მიხედვით, თუ როდის განხორციელდება ზარი რეკურსიული მეთოდი.
ესენია:
#1) კუდის რეკურსია
როცა რეკურსიულ მეთოდზე ზარი არის ბოლო განცხადება შესრულებული რეკურსიული მეთოდის შიგნით, მას ეწოდება "Tail Recursion".
კუდის რეკურსიაში, რეკურსიული ზარის განცხადება ჩვეულებრივ შესრულებულია მეთოდის დაბრუნების განცხადებასთან ერთად.
კუდის რეკურსიის ზოგადი სინტაქსი მოცემულია ქვემოთ:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Head Recursion
Head recursion არის ნებისმიერი რეკურსიული მიდგომა, რომელიც არ არის კუდის რეკურსია. ასე რომ, ზოგადი რეკურსიაც კი წინა რეკურსიაა.
თავის რეკურსიის სინტაქსი ასეთია:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } რეკურსია vs გამეორება ჯავაში
| რეკურსია | იტერაცია |
|---|---|
| რეკურსია არის პროცესი, სადაც მეთოდი თავის თავს განმეორებით იძახებს, სანამ საბაზისო პირობა არ დაკმაყოფილდება. | გამეორება არის პროცესი, რომლითაც კოდის ნაწილი განმეორებით სრულდება სასრული რაოდენობის ჯერ ან პირობის დაკმაყოფილებამდე. |
| აპლიკაცია ფუნქციებისთვის. | გამოიყენება მარყუჟებისთვის. |
| კარგად მუშაობსკოდის მცირე ზომა. | კარგად მუშაობს უფრო დიდი კოდის ზომით. |
| იყენებს მეტ მეხსიერებას, რადგან ყოველი რეკურსიული ზარი გადადის დასტაზე | შედარებით ნაკლები მეხსიერება გამოიყენება. |
| ძნელია გამართვა და შენარჩუნება | უფრო ადვილია გამართვა და შენახვა |
| შედეგად მიდის სტეკის გადატვირთვაში, თუ ბაზის მდგომარეობა არ არის მითითებული ან მიუღწეველია. | შეიძლება შესრულდეს უსასრულოდ, მაგრამ საბოლოოდ შეწყვეტს შესრულებას მეხსიერების ნებისმიერი შეცდომით |
| დროის სირთულე ძალიან მაღალია. | დროის სირთულე შედარებით დაბალია. |
ხშირად დასმული კითხვები
Q #1) როგორ მუშაობს რეკურსია ჯავაში?
პასუხი: რეკურსიის დროს, რეკურსიული ფუნქცია თავის თავს განმეორებით იძახებს, სანამ საბაზისო პირობა არ დაკმაყოფილდება. გამოძახებული ფუნქციის მეხსიერება გადადის დასტაზე, მეხსიერების ზედა ნაწილში, გამოძახების ფუნქციისთვის. თითოეული ფუნქციის გამოძახებისთვის კეთდება ლოკალური ცვლადების ცალკე ასლი.
Q #2) რატომ გამოიყენება რეკურსია?
პასუხი: რეკურსია გამოიყენება იმ პრობლემების გადასაჭრელად, რომლებიც შეიძლება დაიყოს უფრო მცირედ და მთელი პრობლემა შეიძლება გამოიხატოს უფრო მცირე პრობლემის სახით. კომპლექსი უნდა გადაწყდეს განმეორებითი მიდგომის გამოყენებით. პრობლემების გარდა, რომლებშიც დროის სირთულის პრობლემა არ არის, გამოიყენეთ რეკურსი.
Q #3) რა სარგებელი მოაქვსრეკურსია?
პასუხი:
რეკურსიის უპირატესობებში შედის:
- რეკურსია ამცირებს ზედმეტ დარეკვას ფუნქციის.
- რეკურსია საშუალებას გვაძლევს მარტივად გადავჭრათ პრობლემები იტერაციულ მიდგომასთან შედარებით.
Q #4) რომელია უკეთესი - რეკურსია თუ გამეორება?
პასუხი: რეკურსია ახორციელებს განმეორებით ზარებს საბაზისო ფუნქციის მიღწევამდე. ამრიგად, არსებობს მეხსიერების ზედმეტად, რადგან მეხსიერების თითოეული ფუნქციის გამოძახება ხდება დასტაზე.
მეორე მხრივ, გამეორებას არ აქვს ბევრი მეხსიერების ზედნადები. რეკურსიის შესრულება უფრო ნელია, ვიდრე განმეორებითი მიდგომა. რეკურსია ამცირებს კოდის ზომას, ხოლო განმეორებითი მიდგომა კოდს დიდს ხდის.
Q #5) რა უპირატესობები აქვს რეკურსიას გამეორებასთან შედარებით?
პასუხი:
- რეკურსია კოდს უფრო ნათელს და მოკლეს ხდის.
- რეკურსია უკეთესია, ვიდრე განმეორებითი მიდგომა პრობლემებისთვის, როგორიცაა ჰანოის კოშკი, ხე. ტრავერსიები და ა.შ.
- რადგან ყველა ფუნქციის გამოძახებას აქვს მეხსიერება ჩართული დასტაზე, რეკურსი იყენებს მეტ მეხსიერებას.
- რეკურსიის შესრულება უფრო ნელია, ვიდრე განმეორებითი მიდგომა.
დასკვნა
რეკურსია არის ძალიან მნიშვნელოვანი კონცეფცია პროგრამულ უზრუნველყოფაში პროგრამირების ენის მიუხედავად. რეკურსია ძირითადად გამოიყენება მონაცემთა სტრუქტურის პრობლემების გადასაჭრელად, როგორიცაა ჰანოის კოშკები, ხეების გადაკვეთა, დაკავშირებული სიები და ა.შ. თუმცა მას მეტი მეხსიერება სჭირდება,რეკურსია კოდს უფრო მარტივს და ნათელს ხდის.
ჩვენ შევისწავლეთ ყველაფერი რეკურსიის შესახებ ამ სახელმძღვანელოში. ჩვენ ასევე განვახორციელეთ პროგრამირების მრავალი მაგალითი კონცეფციის უკეთ გასაგებად.