Гэты падручнік па рэкурсіі ў 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
Улічваючы радок «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
Алгарытм бінарнага пошуку з'яўляецца вядомым алгарытмам пошуку. У гэтым алгарытме, улічваючы адсартаваны масіў з 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) Знайдзіце мінімальнае значэнне ў масіве з дапамогай рэкурсіі
З дапамогай рэкурсіі мы таксама можам знайсці мінімальнае значэнне ў масіве.
Праграма 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
| Рэкурсія | Ітэрацыя |
|---|---|
| Рэкурсія - гэта працэс, у якім метад выклікае сам сябе паўторна, пакуль не будзе выканана базавая ўмова. | Ітэрацыя - гэта працэс, з дапамогай якога фрагмент кода паўторна выконваецца канечную колькасць разоў або пакуль не будзе выканана ўмова. |
| Гэта дадатак для функцый. | Дастасавальна для завес. |
| Добра працуе дляменшы памер кода. | Добра працуе для большага памеру кода. |
| Выкарыстоўвае больш памяці, паколькі кожны рэкурсіўны выклік адпраўляецца ў стэк | Параўнальна менш памяці выкарыстоўваецца. |
| Цяжка адладжваць і абслугоўваць | Лягчэй адладжваць і абслугоўваць |
| Прыводзіць да перапаўнення стэка, калі база умова не вызначана або не дасягнута. | Можа выконваць бясконцасць, але ў канчатковым выніку спыніць выкананне пры любых памылках памяці |
| Часовая складанасць вельмі высокая. | Часовая складанасць адносна меншая. |
Часта задаюць пытанні
Пытанне #1) Як рэкурсія працуе ў Java?
Адказ: Пры рэкурсіі рэкурсіўная функцыя выклікае саму сябе некалькі разоў, пакуль не будзе выканана базавая ўмова. Памяць для выкліканай функцыі перамяшчаецца ў стэк у верхняй частцы памяці для выклікаючай функцыі. Для кожнага выкліку функцыі ствараецца асобная копія лакальных зменных.
Q #2) Чаму выкарыстоўваецца рэкурсія?
Адказ: Рэкурсія выкарыстоўваецца для вырашэння тых праблем, якія можна разбіць на больш дробныя, і ўся праблема можа быць выказана ў тэрмінах меншай задачы.
Рэкурсія таксама выкарыстоўваецца для тых праблем, якія занадта комплекс, які трэба вырашыць з дапамогай ітэрацыйнага падыходу. Акрамя праблем, для якіх часовая складанасць не з'яўляецца праблемай, выкарыстоўвайце рэкурсію.
Q #3) Якія перавагіРэкурсія?
Адказ:
Перавагі рэкурсіі ўключаюць:
- Рэкурсія памяншае лішнія выклікі функцыі.
- Рэкурсія дазваляе нам лёгка вырашаць праблемы ў параўнанні з ітэрацыйным падыходам.
Пытанне №4) Што лепш - рэкурсія ці ітэрацыя?
Адказ: Рэкурсія робіць паўторныя выклікі, пакуль не будзе дасягнута базавая функцыя. Такім чынам, ёсць накладныя выдаткі на памяць, паколькі памяць для кожнага выкліку функцыі перамяшчаецца ў стэк.
З іншага боку, ітэрацыя не мае вялікіх накладных выдаткаў на памяць. Выкананне рэкурсіі павольней, чым ітэрацыйны падыход. Рэкурсія памяншае памер кода, у той час як ітэрацыйны падыход робіць код вялікім.
Пытанне №5) Якія перавагі рэкурсіі перад ітэрацыяй?
Адказ:
- Рэкурсія робіць код больш зразумелым і карацейшым.
- Рэкурсія лепш, чым ітэрацыйны падыход для такіх праблем, як Ханойская вежа, дрэва абыходы і г.д.
- Паколькі кожны выклік функцыі змяшчае памяць у стэк, рэкурсія выкарыстоўвае больш памяці.
- Прадукцыйнасць рэкурсіі ніжэй, чым ітэрацыйны падыход.
Выснова
Рэкурсія з'яўляецца вельмі важнай канцэпцыяй у праграмным забеспячэнні, незалежна ад мовы праграмавання. Рэкурсія ў асноўным выкарыстоўваецца для вырашэння праблем са структурай даных, такіх як Ханойскія вежы, абыход дрэў, звязаныя спісы і г.д. Хоць яна займае больш памяці,рэкурсія робіць код больш простым і зразумелым.
У гэтым уроку мы вывучылі ўсё пра рэкурсію. Мы таксама рэалізавалі мноства прыкладаў праграмавання для лепшага разумення канцэпцыі.