Javako Errekurtsioari buruzko Tutorial Sakon honek Errekurtsioa zer den azaltzen du Adibideekin, Motekin eta erlazionatutako kontzeptuekin. Errekurtsioa Vs Iterazioa ere hartzen du:
Java-ko lehen tutoretzatik, begizta bat deklaratzen dugun eta gero datu-egitura bat modu iteratibo batean zeharkatzen dugun ikuspegi iteratiboa ikusi dugu, elementu bat hartuz. denbora bat.
Baldintzazko fluxua ere ikusi dugu non berriro begizta aldagai bat mantentzen dugun eta kode zati bat errepikatzen dugu begizta aldagaiak baldintza betetzen duen arte. Funtzio-deiei dagokienez, funtzio-deien ikuspegi iteratiboa ere aztertu dugu.
Tutorial honetan, programazioaren beste ikuspegi bat eztabaidatuko dugu, hau da, ikuspegi errekurtsiboa.
Zer da errekurtsioa Javan?
Errekurtsioa funtzio edo metodo batek bere burua behin eta berriro deitzen duen prozesu bat da. Zuzenean edo zeharka behin eta berriro deitzen den funtzio honi “funtzio errekurtsiboa” deitzen zaio.
Errekurtsioa ulertzeko hainbat adibide ikusiko ditugu. Ikus dezagun orain errekurtsioaren sintaxia.
Errekursioaren sintaxia
Errecurtsioa ezartzen duen edozein metodo oinarrizko bi zati ditu:
- Bere burua dei dezakeen metodo-deia, hau da, errekurtsiboa.
- Errekurtsiboa geldiaraziko duen aurrebaldintza bat.
Kontuan izan edozein metodo errekurtsiborako aurrebaldintza beharrezkoa dela, hala egiten ez badugu. hautsierrekurtsioa, gero infinituan exekutatzen jarraituko du eta pila gainezkatzea eragingo du.
Errekurtsioaren sintaxi orokorra honako hau da:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Kontuan izan aurrebaldintza ere deitzen dela. oinarrizko egoera. Oinarrizko baldintzari buruz gehiago eztabaidatuko dugu hurrengo atalean.
Errekurtsioa Javan ulertzea
Atal honetan, errekurtsio-prozesua ulertzen saiatuko gara eta nola gertatzen den ikusiko dugu. Oinarrizko baldintzari buruz ikasiko dugu, pila gainezkatzea, eta arazo jakin bat errekurtsioarekin eta horrelako beste xehetasun batzuekin nola konpon daitekeen ikusiko dugu.
Errekurtsioaren oinarri-baldintza
Programa errekurtsiboa idazten ari zaren bitartean, beharko genuke. lehenik, oinarrizko kasurako irtenbidea eman. Ondoren, problema handiagoa problema txikiagoen arabera adierazten dugu.
Adibide gisa, zenbaki baten faktoriala kalkulatzeko problema klasiko bat har dezakegu. n zenbaki bat emanda, n-z adierazitako n faktore bat aurkitu behar dugu!
Orain inplementa dezagun programa errekurtsioa erabiliz n faktorea (n!) kalkulatzeko.
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); } }Irteera
Programa honetan, baldintza (n=1) oinarrizko baldintza dela ikus dezakegu eta baldintza horretara iristen denean, funtzioak 1 itzultzen du. Funtzioaren beste zatia dei errekurtsiboa da. Baina metodo errekurtsiboari deitzen zaion bakoitzean, n 1ean gutxitzen da.
Horrela ondoriozta dezakegu azkenean n-ren balioa 1 edo 1 baino txikiagoa izango dela eta honetanpuntua, metodoak 1. balioa itzuliko du. Oinarrizko baldintza horretara iritsiko da eta funtzioa geldituko da. Kontuan izan n-ren balioa edozein izan daitekeela, betiere oinarri-baldintza betetzen badu.
Arazoak ebaztea Errekurtsioa erabiliz
Errekurtsioa erabiltzearen atzean dagoen oinarrizko ideia arazo handiagoaren terminoetan adieraztea da. arazo txikiagoak. Gainera, oinarri-baldintza bat edo gehiago gehitu behar ditugu, errekurtsiotik atera gaitezen.
Hori lehendik ere frogatu zen goiko adibide faktorean. Programa honetan, n faktoriala (n!) balio txikiagoen arabera adierazi dugu eta oinarrizko baldintza (n =1) genuen, n 1era iristen denean, metodo errekurtsibotik irten ahal izateko.
Stack Overflow Error in Recursion
Jakitun gara edozein metodo edo funtzio deitzen denean, funtzioaren egoera pila batean gordetzen dela eta funtzioa itzultzen denean berreskuratzen dela. Pila metodo errekurtsiborako ere erabiltzen da.
Baina errekurtsioaren kasuan, arazo bat gerta liteke oinarri-baldintza definitzen ez badugu edo oinarri-baldintza nolabait iristen edo exekutatzen ez denean. Egoera hau gertatzen bada, pila gainezkatzea sor daiteke.
Kontuan izan dezagun beheko idazkera faktorialaren adibidea.
Hemen oinarri-baldintza oker bat eman dugu, 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); } }Beraz, n > 100 metodoak 1 itzuliko du baina errekurtsioa ez da geldituko. n-ren balioa mugagabean murrizten joango da han bezalaez da gelditzeko beste baldintzarik. Honek pilak gainezka egin arte iraungo du.
Beste kasu bat n-ren balioa 100. Kasu honetan, gainera, metodoak ez du inoiz oinarri-baldintza exekutatuko eta pila gainezkatzea eragingo.
Errekurtsio-adibideak Javan
Atal honetan, honako adibide hauek inplementatuko ditugu erabiliz. errekurtsioa.
#1) Fibonacciren seriea Errekurtsioa erabiliz
Fibonacciren seriea,
1,1,2,3,5,8,13,21, honela ematen da. 34,55,…
Goiko sekuentziak erakusten du uneko elementua aurreko bi elementuen batura dela. Gainera, Fibonacci serieko lehen elementua 1 da.
Beraz, oro har, n uneko zenbakia bada, orduan (n-1) eta (n-2) batuketak ematen du. Uneko elementua aurreko elementuen arabera adierazten denez, problema hau errekurtsioa erabiliz adieraz dezakegu.
Fibonacci seriea ezartzeko programa jarraian ematen da:
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) + " "); } } } Irteera
#2) Egiaztatu zenbaki bat palindromoa den errekurtsioa erabiliz
Palindromoa berdina den sekuentzia bat da. irakurri ezkerretik eskuinera edo eskuinera ezkerrera.
121 zenbakia emanda, ikusten dugu ezkerretik eskuinera eta eskuinetik ezkerrera irakurtzen dugunean berdina dela. Beraz, 121 zenbakia palindromoa da.
Har dezagun beste zenbaki bat, 1242. Ezkerretik eskuinera irakurtzen dugunean 1242 da eta eskuinetik ezkerrera irakurtzean 2421. Beraz, hau ez da palindromo bat.
Guinplementatu palindromo programa zenbakien zifrak alderantziz eta errekurtsiboki alderatu emandako zenbakia bere alderantzizko irudikapenarekin.
Beheko programak palindromoa egiaztatzeko programa inplementatzen du.
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."); } } }Irteera
#3) Alderantzizko katearen errekurtsioa Java
"Kaixo" kate bat emanda alderantzikatu egin behar dugu, ondoriozko katea “olleH” da.
Hau errekurtsioa erabiliz egiten da. Katearen azken karakteretik hasita karaktere bakoitza modu errekurtsiboan inprimatzen dugu katearen karaktere guztiak agortu arte.
Beheko programak errekurtsioa erabiltzen du kate jakin bat alderantzikatzeko.
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); } } Irteera
#4) Bilaketa Binary Java Recursion
Bilaketa algoritmo bitar bat bilaketa egiteko algoritmo ospetsua da. Algoritmo honetan, n elementuz osatutako array ordenatua emanda, matrize hau bilatzen dugu emandako gako-elementua. Hasieran, matrizea bi erditan zatitzen dugu matrizearen erdiko elementua aurkituz.
Ondoren, gakoa erdialdean dagoenaren arabera, gure bilaketa mugatuko dugu matrizearen lehen edo bigarren erdian. Modu honetan prozesu bera errepikatzen da funtsezko elementuen kokapena aurkitu arte.
Algoritmo hau errekurtsioa erabiliz inplementatuko dugu hemen.
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); } } Irteera
#5) Bilatu gutxieneko balioa matrizean Errekurtsioa erabiliz
Errekurtsioa erabiliz, matrizean gutxieneko balioa ere aurki dezakegu.
TheArray-n gutxieneko balioa aurkitzeko Java programa behean ematen da.
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"); } }Irteera
Hauek dira. errekurtsioaren adibideak. Adibide horiez gain, softwareko beste arazo asko inplementa daitezke teknika errekurtsiboen bidez.
Errekurtsio motak
Errecurtsioa bi motatakoa da deia noiz egiten den kontuan hartuta. metodo errekurtsiboa.
Hauek dira:
#1) Buztan errekurtsioa
Metodo errekurtsiborako deia azken adierazpena denean. metodo errekurtsiboaren barruan exekutatuta, “Tail Recursion” deitzen da.
Butsean errekurtsioan, dei errekurtsiboaren instrukzioa metodoaren return instrukzioarekin batera exekutatzen da normalean.
The Isats-errekurtsiorako sintaxi orokorra behean ematen da:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Buru-errekurtsioa
Buru-errekurtsioa isats-errekurtsioa ez den edozein ikuspegi errekurtsibo da. Beraz, errekurtsio orokorra ere errekurtsioaren aurretik dago.
Buruaren errekurtsioaren sintaxia hau da:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Errekurtsioa Vs Iterazioa Javan
| Errekurtsioa | Iterazioa |
|---|---|
| Errecurtsioa metodo batek bere burua behin eta berriz deitzen duen prozesu bat da, oinarrizko baldintza bat bete arte. | Iterazioa da. kode-zati bat behin eta berriz exekutatzen den prozesu bat aldiz kopuru finitu batean edo baldintza bat bete arte. |
| Funtzioen aplikazioa al da. | Aplikatzen da. begiztak egiteko. |
| Ondo funtzionatzen dukode-tamaina txikiagoa. | Ondo funtzionatzen du kode-tamaina handiagorako. |
| Memoria gehiago erabiltzen du dei errekurtsibo bakoitza pilara eramaten den heinean | Konparatiboki memoria gutxiago erabiltzen da. |
| Araztu eta mantentzea zaila da | Araztu eta mantentzea errazagoa |
| Pila gainezkatzea eragiten du oinarria bada. baldintza ez da zehaztu edo ez da iristen. | Infinitu gabe exekutatu daiteke, baina memoria-akatsekin exekuzioa geldituko da azkenean. |
| Denboraren konplexutasuna oso handia da. | Denboraren konplexutasuna nahiko behealdean dago. |
Maiz egiten diren galderak
G #1) Nola funtzionatzen du Errekurtsioak Javan?
Erantzuna: Errekurtsioan, funtzio errekurtsiboak bere buruari behin eta berriz deitzen dio oinarrizko baldintza bat bete arte. Deitutako funtzioaren memoria deitzeko funtzioaren memoriaren goialdean dagoen pilara bultzatzen da. Funtzio-dei bakoitzeko, aldagai lokalen kopia bereizia egiten da.
Q #2) Zergatik erabiltzen da Errekurtsioa?
Erantzuna: Errekurtsioa txikiagotan banatu daitezkeen arazo horiek konpontzeko erabiltzen da eta arazo osoa arazo txikiago baten moduan adieraz daiteke.
Errecurtsioa gehiegi diren arazo horietarako ere erabiltzen da. konplexua ebatzi beharreko ikuspegi iteratiboa erabiliz. Denboraren konplexutasuna arazoa ez den arazoez gain, erabili errekurtsioa.
G #3) Zer onura ditu.Errekurtsioa?
Erantzuna:
Errekursioaren abantailen artean daude:
- Erantzunak dei erredundanteak murrizten ditu. funtzioaren.
- Errecurtsioak arazoak erraz ebazteko aukera ematen digu ikuspegi iteratiboarekin alderatuta.
G #4) Zein da hobea – Errekurtsioa ala Iterazioa?
Erantzuna: Recursion-ek behin eta berriz deiak egiten ditu oinarrizko funtziora iritsi arte. Beraz, memoria gainkarga bat dago funtzio-dei bakoitzeko memoria bat pilara bultzatzen den heinean.
Iterazioek, aldiz, ez du memoria gehiegirik. Errekurtsioaren exekuzioa ikuspegi iteratiboa baino motelagoa da. Errekurtsioak kodearen tamaina murrizten du, ikuspegi iteratiboak, berriz, kodea handitzen du.
G #5) Zein dira Errekurtsioaren abantailak iterazioarekiko?
Erantzuna:
- Errekurtsioak kodea argiago eta laburragoa egiten du.
- Errecurtsioa ikuspegi iteratiboa baino hobea da Hanoiko dorrea, zuhaitza bezalako arazoetarako. zeharkaldiak, etab.
- Funtzio-dei bakoitzak memoria pilara bultzatzen duenez, Recursion-ek memoria gehiago erabiltzen du.
- Errekurtsoaren errendimendua motelagoa da ikuspegi iteratiboa baino.
Ondorioa
Errecurtsioa oso kontzeptu garrantzitsua da softwarean programazio-lengoaia edozein dela ere. Errekurtsioa datu-egiturako arazoak konpontzeko erabiltzen da batez ere Hanoiko dorreak, zuhaitzen zeharkaldiak, estekatutako zerrendak, etab. Memoria gehiago behar duen arren,Errekurtsioak kodea errazagoa eta argiagoa egiten du.
Tutorial honetan Errekurtsioari buruzko guztia aztertu dugu. Programazio-adibide ugari ere ezarri ditugu kontzeptua hobeto ulertzeko.