Овај детаљни водич о рекурзији у Јави објашњава шта је рекурзија са примерима, типовима и сродним концептима. Такође покрива рекурзију против итерације:
Из наших ранијих туторијала у Јави, видели смо итеративни приступ у коме декларишемо петљу, а затим прелазимо кроз структуру података на итеративни начин узимајући један елемент на време.
Такође смо видели условни ток где опет задржавамо једну променљиву петље и понављамо део кода док променљива петље не испуни услов. Када је реч о позивима функција, истражили смо итеративни приступ за позиве функција.
У овом водичу ћемо разговарати о другачијем приступу програмирању, тј. рекурзивном приступу.
Шта је рекурзија у Јави?
Рекурзија је процес којим функција или метода позива себе изнова и изнова. Ова функција која се позива изнова и изнова, директно или индиректно, назива се „рекурзивна функција“.
Видећемо разне примере да бисмо разумели рекурзију. Сада да видимо синтаксу рекурзије.
Синтакса рекурзије
Сваки метод који имплементира рекурзију има два основна дела:
- Позив методе који може сам себе назвати, тј. рекурзивни
- Предуслов који ће зауставити рекурзију.
Имајте на уму да је предуслов неопходан за било коју рекурзивну методу као, ако не бреак тхерекурзија онда ће наставити да ради бесконачно и резултираће преливањем стека.
Општа синтакса рекурзије је следећа:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Имајте на уму да се предуслов такође назива основно стање. Више о основном услову ћемо разговарати у следећем одељку.
Разумевање рекурзије у Јави
У овом одељку ћемо покушати да разумемо процес рекурзије и видимо како се он одвија. Научићемо о основном стању, прекорачењу стека и видети како се одређени проблем може решити рекурзијом и другим сличним детаљима.
Основни услов рекурзије
Док пишемо рекурзивни програм, требало би да прво обезбедите решење за основни случај. Тада већи проблем изражавамо у терминима мањих проблема.
Као пример, можемо узети класични проблем израчунавања факторијела броја. С обзиром на број н, морамо пронаћи факторијел од н означен са н!
Сада имплементирајмо програм за израчунавање н факторијела (н!) користећи рекурзију.
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); } }Оутпут
У овом програму можемо видети да је услов (н&лт;=1) основни услов и када се овај услов достигне, функција враћа 1 Други део функције је рекурзивни позив. Али сваки пут када се позове рекурзивна метода, н се смањује за 1.
Тако можемо закључити да ће на крају вредност н постати 1 или мања од 1 и на овомтачка, метод ће вратити вредност 1. Овај основни услов ће бити достигнут и функција ће се зауставити. Имајте на уму да вредност н може бити било шта све док задовољава основни услов.
Решавање проблема помоћу рекурзије
Основна идеја иза употребе рекурзије је да се изрази већи проблем у смислу мањи проблеми. Такође, морамо да додамо један или више основних услова да бисмо могли да изађемо из рекурзије.
Ово је већ демонстрирано у горњем примеру факторијала. У овом програму, изразили смо факторијел н (н!) у терминима мањих вредности и имали смо основни услов (н &лт;=1) тако да када н достигне 1, можемо напустити рекурзивни метод.
Грешка прекорачења стека у рекурзији
Свесни смо да када се позове било која метода или функција, стање функције се чува у стеку и преузима када се функција врати. Стек се користи и за рекурзивну методу.
Али у случају рекурзије, може доћи до проблема ако не дефинишемо основни услов или када основни услов на неки начин није достигнут или извршен. Ако дође до ове ситуације, може доћи до прекорачења стека.
Размотримо доњи пример факторске нотације.
Овде смо дали погрешан основни услов, н==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); } }Дакле, када је н &гт; 100 метода ће вратити 1, али рекурзија се неће зауставити. Вредност н ће наставити да се смањује на неодређено временема другог услова да се то заустави. Ово ће се наставити све док се стек не препуни.
Други случај ће бити када вредност н &лт; 100. У овом случају, такође, метода никада неће извршити основни услов и резултирати прекорачењем стека.
Примери рекурзије у Јави
У овом одељку ћемо имплементирати следеће примере користећи рекурзија.
#1) Фибоначијев низ који користи рекурзију
Фибоначијев низ је дат са,
1,1,2,3,5,8,13,21, 34,55,…
Наведени низ показује да је тренутни елемент збир претходна два елемента. Такође, први елемент у Фибоначијевом низу је 1.
Дакле, генерално, ако је н тренутни број, онда је дат збиром (н-1) и (н-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) Обрнута рекурзија стрингова Јава
С обзиром на низ „Здраво“ морамо га обрнути тако да резултујући стринг је “оллеХ”.
Ово се ради помоћу рекурзије. Почевши од последњег знака у стрингу, рекурзивно штампамо сваки знак све док се сви карактери у стрингу не исцрпе.
Програм у наставку користи рекурзију да преокрене дати низ.
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) Јава рекурзија бинарног претраживања
Алгоритам бинарне претраге је познати алгоритам за претраживање. У овом алгоритму, дат сортирани низ од н елемената, тражимо овај низ за дати кључни елемент. У почетку делимо низ на две половине проналажењем средњег елемента низа.
Затим у зависности од тога да ли је кључ у средини ограничавамо нашу претрагу у првој или другој половини низа. На овај начин се исти процес понавља док се не пронађе локација кључних елемената.
Овај алгоритам ћемо имплементирати користећи рекурзију овде.
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) Пронађите минималну вредност у низу помоћу рекурзије
Помоћу рекурзије такође можемо пронаћи минималну вредност у низу.
ТхеЈава програм за проналажење минималне вредности у низу је дат испод.
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; } Рекурзија против итерације у Јави
| Рекурзија | Итерација |
|---|---|
| Рекурзија је процес у којем метода позива себе више пута док се не испуни основни услов. | Итерација је процес којим се део кода више пута извршава коначан број пута или док се не испуни услов. |
| Да ли је апликација за функције. | Да ли је применљива за петље. |
| Добро ради замања величина кода. | Добро функционише за већу величину кода. |
| Користи више меморије пошто се сваки рекурзивни позив гура у стек | Релативно мање меморије се користи. |
| Тешко за отклањање грешака и одржавање | Лакше за отклањање грешака и одржавање |
| Резултира прекорачењем стека ако је основа услов није наведен или није достигнут. | Може да се извршава бесконачно, али ће на крају зауставити извршење са било каквим меморијским грешкама |
| Временска сложеност је веома висока. | Временска сложеност је релативно нижа. |
Често постављана питања
П #1) Како рекурзија ради у Јави?
Одговор: У рекурзији, рекурзивна функција позива себе више пута све док основни услов није задовољен. Меморија за позвану функцију се гура на стек на врху меморије за функцију која позива. За сваки позив функције прави се посебна копија локалних променљивих.
П #2) Зашто се користи рекурзија?
Одговор: Рекурзија се користи за решавање оних проблема који се могу поделити на мање и цео проблем се може изразити у терминима мањег проблема.
Рекурзија се такође користи за оне проблеме који су превише комплекса који се решава коришћењем итеративног приступа. Поред проблема за које временска сложеност није проблем, користите рекурзију.
П #3) Које су предностиРекурзија?
Одговор:
Предности рекурзије укључују:
- Рекурзија смањује сувишно позивање функције.
- Рекурзија нам омогућава да лако решавамо проблеме у поређењу са итеративним приступом.
П #4) Шта је боље – рекурзија или итерација?
Одговор: Рекурзија врши поновљене позиве док се не достигне основна функција. Дакле, постоји надоптерећење меморије јер се меморија за сваки позив функције гура у стек.
Итерација са друге стране нема много меморије. Извршење рекурзије је спорије од итеративног приступа. Рекурзија смањује величину кода док итеративни приступ чини код великим.
П #5) Које су предности рекурзије у односу на итерацију?
Одговор:
- Рекурзија чини код јаснијим и краћим.
- Рекурзија је боља од итеративног приступа за проблеме као што је Ханојска кула, дрво обилажења итд.
- Пошто сваки позив функције има меморију гурнуту у стек, рекурзија користи више меморије.
- Перформансе рекурзије су спорије од итеративног приступа.
Закључак
Рекурзија је веома важан концепт у софтверу без обзира на програмски језик. Рекурзија се углавном користи у решавању проблема са структуром података као што су торњеви Ханоја, обилажење стабала, повезане листе, итд. Иако захтева више меморије,рекурзија чини код једноставнијим и јаснијим.
Истражили смо све о рекурзији у овом водичу. Такође смо имплементирали бројне примере програмирања за боље разумевање концепта.