Жава хэл дээрх рекурсын талаарх энэхүү гүнзгий заавар нь рекурс гэж юу болохыг жишээ, төрөл, холбогдох ойлголтоор тайлбарласан болно. Энэ нь мөн Recursion Vs Iteration-ыг хамардаг:
Бид Java хэл дээрх өмнөх хичээлүүдээс бид давталттай хандлагыг олж харсан бөгөөд үүнд бид давталт зарлаж, дараа нь нэг элементийг авч давталттайгаар өгөгдлийн бүтцээр дамждаг. цаг.
Мөн бид нэг давталтын хувьсагчийг дахин хадгалж, давталтын хувьсагч нөхцөлийг хангах хүртэл кодыг давтдаг нөхцөлт урсгалыг харсан. Функцийн дуудлагын тухайд бид функцийн дуудлагын давталтын аргыг мөн судалсан.
Энэхүү зааварт бид програмчлалын өөр хандлагыг тухайлбал рекурсив аргыг авч үзэх болно.
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-д хүрэхэд рекурсив аргыг орхиж болно.
Рекурсын стек халих алдаа
Аливаа арга эсвэл функцийг дуудах үед функцийн төлөв нь стек дээр хадгалагдаж, функц буцаж ирэхэд сэргээгддэг гэдгийг бид мэднэ. Стекийг рекурсив аргад мөн ашигладаг.
Гэхдээ рекурсын хувьд суурь нөхцөлийг тодорхойлоогүй эсвэл үндсэн нөхцөл нь ямар нэгэн байдлаар хүрээгүй эсвэл биелээгүй үед асуудал үүсч болзошгүй. Хэрэв ийм нөхцөл байдал үүсвэл стекийн хэт ачаалал үүсч болзошгүй.
Доорх хүчин зүйлийн тэмдэглэгээний жишээг авч үзье.
Энд бид 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. Мөн энэ тохиолдолд уг арга нь үндсэн нөхцөлийг хэзээ ч гүйцэтгэхгүй бөгөөд стек халихад хүргэдэг.
Жава хэл дээрх рекурсын жишээ
Энэ хэсэгт бид дараах жишээнүүдийг ашиглан хэрэгжүүлнэ. рекурс.
#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
“Сайн уу” гэсэн мөр өгөгдсөн бол бид үүнийг буцаах ёстой. Үр дүнгийн мөр нь “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> TheМассив дахь хамгийн бага утгыг олох 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) Толгойн рекурсион
Толгойн рекурс нь сүүлний рекурс биш аливаа рекурсив хандлага юм. Тэгэхээр ерөнхий рекурс нь хүртэл рекурсын өмнө байна.
Толгойн рекурсын синтакс дараах байдалтай байна:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Жава хэл дээрх рекурс Vs давталт
| Recursion | Давталт |
|---|---|
| Recursion нь үндсэн нөхцөл хангагдтал арга нь өөрийгөө дахин дахин дуудах үйл явц юм. | Давталт Хэсэг кодын хязгаарлагдмал тооны хугацаанд эсвэл нөхцөл биелэх хүртэл давтан гүйцэтгэх процесс. |
| Функцуудад зориулсан програм мөн үү. | Хэрэглэх боломжтой for loops. |
| Сайн ажилладагжижиг кодын хэмжээ. | Илүү том хэмжээтэй кодын хувьд сайн ажилладаг. |
| Рекурсив дуудлага бүрийг стек рүү түлхэх үед илүү их санах ой ашигладаг | Харьцангуй бага санах ой ашиглаж байна. |
| Дбаг хийх, засварлахад хэцүү | Дбаг хийх, засварлахад хялбар |
| Хэрэв суурь нь стек халихад хүргэдэг. нөхцөл тодорхойлогдоогүй эсвэл хүрээгүй байна. | Хязгааргүй гүйцэтгэлтэй байж болох ч эцсийн дүндээ санах ойн алдаа гарвал гүйцэтгэлийг зогсооно |
| Цаг хугацааны нарийн төвөгтэй байдал маш өндөр байна. | Цагийн нарийн төвөгтэй байдал нь харьцангуй доод талдаа байна. |
Түгээмэл асуултууд
Асуулт #1) Жава хэл дээр рекурс хэрхэн ажилладаг вэ?
Хариулт: Рекурсын үед рекурсив функц нь үндсэн нөхцөл хангагдах хүртэл өөрийгөө дахин дахин дууддаг. Дуудагдсан функцийн санах ойг дуудаж буй функцийн санах ойн дээд талд байрлах стек рүү түлхдэг. Функцийн дуудлага бүрийн хувьд локал хувьсагчийн тусдаа хуулбарыг хийдэг.
Асуулт #2) Яагаад Рекурсийг ашигладаг вэ?
Хариулт: Рекурсийг жижиг асуудалд хувааж, бүхэл бүтэн асуудлыг жижиг бодлогоор илэрхийлж болох асуудлуудыг шийдвэрлэхэд ашигладаг.
Хэтэрхий том асуудлуудад рекурсийг ашигладаг. давталтын аргыг ашиглан шийдвэрлэх цогц . Цагийн нарийн төвөгтэй байдал нь асуудал биш асуудлуудаас гадна рекурсийг ашигла.
Асуулт #3) Ямар давуу талтай вэ?Рекурс хийх үү?
Хариулт:
Рекурсын давуу талууд нь:
- Рекурс нь илүүдэл дуудлагыг багасгадаг. функцийн.
- Рекурс нь давталтын аргатай харьцуулахад асуудлыг хялбар шийдвэрлэх боломжийг олгодог.
Асуулт №4) Аль нь илүү дээр вэ – Рекурс эсвэл давталт уу?
Хариулт: Recursion нь үндсэн функцэд хүрэх хүртэл давтан дуудлага хийдэг. Функцын дуудлагын санах ойг стек рүү шахдаг тул санах ойн ачаалал бий болно.
Нөгөө талаас давталт нь санах ойн ачаалал ихтэй байдаггүй. Рекурсын гүйцэтгэл нь давталтын аргаас удаан байдаг. Рекурс нь кодын хэмжээг багасгадаг бол давталтын арга нь кодыг том болгодог.
Асуулт №5) Давталтаас давтагдах нь ямар давуу талтай вэ?
Хариулт:
- Рекурс нь кодыг илүү ойлгомжтой, богино болгодог.
- Рекурс нь Ханой цамхаг, мод зэрэг асуудлуудын давталтын аргаас илүү сайн байдаг. дамжуулалт гэх мэт.
- Функцын дуудлага бүр санах ойг стек рүү шилжүүлдэг тул Рекурс нь илүү их санах ой ашигладаг.
- Рекурсын гүйцэтгэл нь давталтын аргаас удаан байдаг.
Дүгнэлт
Рекурс нь програмчлалын хэлээс үл хамааран програм хангамжид маш чухал ойлголт юм. Рекурсийг ихэвчлэн Ханойн цамхаг, мод гатлах, холбосон жагсаалт гэх мэт өгөгдлийн бүтцийн асуудлыг шийдвэрлэхэд ашигладаг. Хэдийгээр илүү их санах ой зарцуулдаг.рекурс нь кодыг илүү энгийн бөгөөд ойлгомжтой болгодог.
Бид энэ зааварт Рекурсын тухай бүгдийг судалсан. Бид мөн ойлголтыг илүү сайн ойлгохын тулд програмчлалын олон жишээг хэрэгжүүлсэн.