Бұл Java тіліндегі рекурсия бойынша тереңдетілген оқулық мысалдармен, түрлермен және қатысты ұғымдармен рекурсия деген не екенін түсіндіреді. Ол сондай-ақ Рекурсия мен Итерацияны қамтиды:
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. Бұл жағдайда әдіс ешқашан негізгі шартты орындамайды және стек толып кетуіне әкеледі.
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
«Сәлеметсіз бе» жолы берілгенде, біз оны кері айналдыруымыз керек, осылайша нәтиже жолы – “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 рекурсиясы
Екілік іздеу алгоритмі - іздеудің әйгілі алгоритмі. Бұл алгоритмде 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) Рекурсия көмегімен массивтің минималды мәнін табу
Рекурсияны пайдаланып, массивтегі ең аз мәнді де таба аламыз.
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) Құйрық рекурсиясы
Рекурсивті әдіске шақыру соңғы оператор болған кезде. рекурсивті әдістің ішінде орындалады, ол «Құйрықты рекурсия» деп аталады.
Тайымды рекурсияда рекурсивті шақыру операторы әдетте әдістің қайтару операторымен бірге орындалады.
Құйрық рекурсиясы үшін жалпы синтаксис төменде берілген:
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; } Java тіліндегі рекурсия және итерация
| Рекурсия | Итерация |
|---|---|
| Рекурсия - бұл негізгі шарт орындалғанға дейін әдіс өзін қайта-қайта шақыратын процесс. | Итерация код бөлігі соңғы рет немесе шарт орындалғанға дейін қайталанып орындалатын процесс. |
| Функцияларға арналған қолданба ма. | Қолданылады for циклдері. |
| үшін жақсы жұмыс істейдікішірек код өлшемі. | Үлкенірек код өлшемі үшін жақсы жұмыс істейді. |
| Әр рекурсивті қоңырау стекке жіберілетіндіктен көбірек жадты пайдаланады | Салыстырмалы түрде аз жад пайдаланылады. |
| Түзету және жөндеу қиын | Оңай жөндеу және жөндеу |
| Нәтижелері негіз болса, стек толып кетеді. шарт көрсетілмеген немесе оған қол жеткізілмеген. | Шексіз орындалуы мүмкін, бірақ соңында кез келген жад қателерімен орындауды тоқтатады |
| Уақыт күрделілігі өте жоғары. | Уақыттың күрделілігі салыстырмалы түрде төменгі жағында. |
Жиі қойылатын сұрақтар
С №1) Java тілінде рекурсия қалай жұмыс істейді?
Жауабы: Рекурсияда рекурсивті функция негізгі шарт орындалғанша өзін қайта-қайта шақырады. Шақырылатын функцияның жады шақырылатын функцияның жадының жоғарғы жағындағы стекке итеріледі. Әрбір функция шақыруы үшін жергілікті айнымалылардың жеке көшірмесі жасалады.
2-сұрақ) Рекурсия не үшін қолданылады?
Жауап: Рекурсия кішірек есептерге бөлуге болатын және барлық мәселені кішірек есеппен көрсетуге болатын есептерді шешу үшін қолданылады.
Рекурсия тым көп есептер үшін де қолданылады. күрделі итеративті тәсілді қолдану арқылы шешіледі. Уақыттың күрделілігі мәселе болып табылмайтын есептерден басқа рекурсияны пайдаланыңыз.
С №3) Қандай артықшылықтар барРекурсия?
Жауап:
Рекурсияның артықшылықтарына мыналар жатады:
- Рекурсия артық шақыруды азайтады. функцияның.
- Рекурсия итерациялық тәсілмен салыстырғанда есептерді оңай шешуге мүмкіндік береді.
С №4) Қайсысы жақсы – Рекурсия немесе Итерация?
Жауап: Рекурсия негізгі функцияға жеткенше қайталанатын қоңырауларды жасайды. Осылайша, әрбір функция шақыруының жады стекке итерілетіндіктен үстеме жады бар.
Екінші жағынан, итерацияда көп жад шығыны болмайды. Рекурсияның орындалуы итерациялық тәсілге қарағанда баяу. Рекурсия кодтың өлшемін азайтады, ал итерациялық тәсіл кодты үлкен етеді.
С №5) Итерациядан рекурсияның артықшылығы қандай?
Жауап:
- Рекурсия кодты айқынырақ және қысқа етеді.
- Рекурсия Ханой мұнарасы, ағаш сияқты мәселелерге қайталанатын тәсілге қарағанда жақсырақ. өтулер және т.б.
- Әрбір функция шақыруында стекке итерілген жад болғандықтан, Рекурсия көбірек жадты пайдаланады.
- Рекурсияның өнімділігі итеративті тәсілге қарағанда баяуырақ.
Қорытынды
Рекурсия программалау тіліне қарамастан бағдарламалық жасақтамадағы өте маңызды ұғым. Рекурсия көбінесе Ханой мұнаралары, ағаштар өтуі, байланыстырылған тізімдер және т.б. сияқты деректер құрылымы мәселелерін шешуде қолданылады. Ол көбірек жадты қажет етеді,рекурсия кодты қарапайым және түсінікті етеді.
Біз бұл оқулықта Рекурсия туралы барлығын зерттедік. Тұжырымдаманы жақсырақ түсіну үшін біз көптеген бағдарламалау мысалдарын енгіздік.