Ta poglobljena učna ura o rekurziji v Javi pojasnjuje, kaj je rekurzija s primeri, tipi in sorodnimi koncepti. Zajema tudi rekurzijo in iteracijo:
V prejšnjih učbenikih za Javo smo spoznali iterativni pristop, pri katerem razglasimo zanko in nato iterativno prečesavamo podatkovno strukturo tako, da vzamemo en element naenkrat.
Videli smo tudi pogojni tok, pri katerem spet obdržimo eno spremenljivko zanke in ponavljamo del kode, dokler spremenljivka zanke ne izpolni pogoja. Ko gre za klice funkcij, smo prav tako raziskali iterativni pristop za klice funkcij.
V tem učbeniku bomo obravnavali drugačen pristop k programiranju, tj. rekurzivni pristop.
Kaj je rekurzija v Javi?
Rekurzija je postopek, pri katerem funkcija ali metoda vedno znova pokliče samo sebe. Funkcija, ki se vedno znova neposredno ali posredno pokliče, se imenuje "rekurzivna funkcija".
Za razumevanje rekurzije si bomo ogledali različne primere. Zdaj si oglejmo sintakso rekurzije.
Rekurzivna sintaksa
Vsaka metoda, ki izvaja rekurzijo, ima dva osnovna dela:
- Klic metode, ki lahko kliče samo sebe, tj. rekurzivni klic
- Predpogoj, ki ustavi rekurzijo.
Upoštevajte, da je predpogoj potreben za vsako rekurzivno metodo, saj se bo rekurzija izvajala v neskončnost, če je ne prekinemo, kar bo povzročilo prelivanje sklada.
Splošna sintaksa rekurzije je naslednja:
methodName (T parametri...) { if (predpogoj == true) //predpogoj ali osnovni pogoj { return result; } return methodName (T parametri...); //rekurzivni klic } Upoštevajte, da se predpogoj imenuje tudi osnovni pogoj. Več o osnovnem pogoju bomo povedali v naslednjem razdelku.
Razumevanje rekurzije v Javi
V tem poglavju bomo poskušali razumeti proces rekurzije in videti, kako poteka. Spoznali bomo osnovni pogoj, prelivanje sklada, videli, kako lahko določen problem rešimo z rekurzijo, in druge podobne podrobnosti.
Rekurzija Osnovni pogoj
Pri pisanju rekurzivnega programa moramo najprej podati rešitev za osnovni primer. Nato večji problem izrazimo z manjšimi problemi.
Kot primer, lahko vzamemo klasični problem izračuna faktorja števila. Dano je število n, poiskati moramo faktorij števila n, ki ga označimo z n!
Zdaj implementirajmo program za izračun n-kratnika (n!) z uporabo rekurzije.
javni razred Main{ static int fact(int n) { if (n == 1) // osnovni pogoj return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Izhod
V tem programu vidimo, da je pogoj (n<=1) osnovni pogoj in ko je ta pogoj dosežen, funkcija vrne 1. Del else funkcije je rekurzivni klic. Toda ob vsakem klicu rekurzivne metode se n zmanjša za 1.
Tako lahko sklepamo, da bo na koncu vrednost n postala 1 ali manjša od 1 in na tej točki bo metoda vrnila vrednost 1. Ta osnovni pogoj bo dosežen in funkcija se bo ustavila. Upoštevajte, da je vrednost n lahko poljubna, če izpolnjuje osnovni pogoj.
Reševanje problemov z uporabo rekurzije
Osnovna ideja uporabe rekurzije je, da večji problem izrazimo z manjšimi problemi. Prav tako moramo dodati enega ali več osnovnih pogojev, da lahko izstopimo iz rekurzije.
To je bilo prikazano že v zgornjem primeru faktoriala. V tem programu smo faktorial n (n!) izrazili z manjšimi vrednostmi in imeli osnovni pogoj (n <=1), tako da lahko, ko n doseže 1, zaključimo rekurzivno metodo.
Stack Overflow Napaka v rekurziji
Vemo, da se ob klicu katere koli metode ali funkcije stanje funkcije shrani na zalogovnik in se prikliče, ko se funkcija vrne. Zalogovnik se uporablja tudi za rekurzivno metodo.
Toda v primeru rekurzije lahko pride do težave, če ne določimo osnovnega pogoja ali če osnovni pogoj nekako ni dosežen ali izveden. Če se to zgodi, lahko pride do prepolnitve sklada.
Oglejmo si spodnji primer faktorskega zapisa.
Tu smo podali napačen osnovni pogoj, n==100.
javni razred Main { static int fact(int n) { if (n == 100) // osnovni pogoj, ki povzroči prelivanje sklada return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Ko bo n> 100, bo metoda vrnila 1, vendar se rekurzija ne bo ustavila. Vrednost n se bo zmanjševala v nedogled, saj ni nobenega drugega pogoja, ki bi jo ustavil. To se bo nadaljevalo, dokler se kup ne prepolni.
Drug primer je, ko je vrednost n <100. Tudi v tem primeru metoda ne bo nikoli izvedla osnovnega pogoja in bo povzročila prelivanje sklada.
Primeri rekurzije v javi
V tem razdelku bomo naslednje primere izvedli z uporabo rekurzije.
#1) Fibonaccijeva vrsta z uporabo rekurzije
Fibonaccijeva vrsta je podana z,
1,1,2,3,5,8,13,21,34,55,…
Zgornje zaporedje kaže, da je trenutni element vsota prejšnjih dveh elementov. Prvi element v Fibonaccijevi vrsti je 1.
Če je torej n trenutno število, je na splošno podano z vsoto (n-1) in (n-2). Ker je trenutni element izražen s prejšnjimi elementi, lahko ta problem izrazimo z rekurzijo.
Program za izvajanje Fibonaccijeve vrste je podan spodaj:
public class Main { //metoda za izračun fibonaccijeve serije 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; //izpis prvih 10 številk fibonaccijeve serije System.out.println ("Fibonaccijeva serija: prvih 10 številk:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Izhod
#2) Preverite, ali je število palindrom z uporabo rekurzije
Palindrom je zaporedje, ki je enako, če ga beremo od leve proti desni ali od desne proti levi.
Dano je število 121. Vidimo, da je, če ga beremo od leve proti desni in od desne proti levi, enako. Zato je število 121 palindrom.
Vzemimo drugo število, 1242. Ko ga beremo od leve proti desni, je 1242, ko pa ga beremo od desne proti levi, je 2421. To torej ni palindrom.
Program za palindrome izvedemo tako, da obrnemo števke števil in rekurzivno primerjamo dano število z njegovim obrnjenim prikazom.
Spodnji program izvaja program za preverjanje palindroma.
import java.io.*; import java.util.*; public class Main { // preveri, ali num vsebuje samo eno številko 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 { //calluporabna funkcija rekurzivno revNum = isPalindrome_util(num / 10, revNum); } // Preverite, ali sta prvi številki num in revNum enaki if (num % 10 == revNum % 10) { // če da, se revNum premakne s num return revNum / 10; } else { // izhod throw new Exception(); } } } //metoda za preverjanje, ali je dano število palindrom z uporabo uporabne funkcije palindrom public static int isPalindrome(int num) throwsIzjema { 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("Da, dano število " + n + " je palindrom."); } catch (Exception e) { System.out.println("Ne, dano število " + n + " ni palindrom."); } n = 1221; try { isPalindrome(n);System.out.println("Da, dano število " + n + " je palindrom."); } catch (Izjema e) { System.out.println("Ne, dano število " + n + " ni palindrom."); } } } } Izhod
#3) Povratna rekurzija nizov Java
Dani niz "Hello" moramo obrniti tako, da je dobljeni niz "olleH".
To storimo z rekurzijo. Začnemo z zadnjim znakom v nizu in rekurzivno izpišemo vsak znak, dokler ne izčrpamo vseh znakov v nizu.
Spodnji program uporablja rekurzijo za obrnitev danega niza.
razred String_Reverse { //rekurzivna metoda za obrnitev danega niza void reverseString(String str) { //osnovni pogoj; vrni, če je niz nič ali ima 1 ali manj znakov if ((str==null)} } } razred Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Podani niz: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Obrnjeni niz: "); obj.reverseString(inputstr); } } } Izhod
#4) Binarno iskanje Java Rekurzija
Algoritem binarnega iskanja je znan algoritem za iskanje. Pri tem algoritmu, če imamo na voljo razvrščeno polje z n elementi, v tem polju iščemo dani ključni element. Na začetku polje razdelimo na dve polovici tako, da poiščemo srednji element polja.
Nato glede na to, ali je ključ sredi, omejimo iskanje v prvi ali drugi polovici polja. Na ta način isti postopek ponavljamo, dokler ne najdemo lokacije ključnih elementov.
Ta algoritem bomo izvedli s pomočjo rekurzije.
import java.util.*; class Binary_Search { // rekurzivno binarno iskanje int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //izračunaj sredino polja int mid = left + (right - left) / 2; // če je ključ na sredini, vrni mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // V nasprotnem primeru rekurzivno poiščemo vdesno podpolje return binarySearch(numArray, mid + 1, right, key); } // v polju ni elementov, vrnite -1 return -1; } } } razred Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //deklaracija in izpis polja int numArray[] = { 4,6,12,16,22}; System.out.println("Dano polje : " + Arrays.toString(numArray)); int len = numArray.length; //daljina poljaint key = 16; //ključ za iskanje int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Elementa " + key + " ni"); else System.out.println("Element " + key + " najden pri indeksu " + result); } } Izhod
#5) Najdi najmanjšo vrednost v polju z uporabo rekurzije
Z rekurzijo lahko poiščemo tudi najmanjšo vrednost v polju.
Program Java za iskanje najmanjše vrednosti v polju je podan spodaj.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //vrni prvi element, če je le en element ali minimum elementov polja 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("Dano polje : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Najmanjši element polja: " + getMin(numArray, 0, n) + "\n"); } } Izhod
To so nekateri primeri rekurzije. Poleg teh primerov je mogoče z rekurzivnimi tehnikami izvesti še veliko drugih problemov v programski opremi.
Vrste rekurzije
Rekurzija je dveh vrst glede na to, kdaj je klicana rekurzivna metoda.
To so:
#1) Rekurzija na repu
Kadar je klic rekurzivne metode zadnja izjava, ki se izvede znotraj rekurzivne metode, se to imenuje "rekurzija na repu".
Pri rekurziji na repu se rekurzivni klicni stavek običajno izvede skupaj s stavkom o vrnitvi metode.
Splošna sintaksa za rekurzijo repa je podana spodaj:
methodName ( T parametri...){ { if (base_condition == true) { return result; } return methodName (T parametri...) //tail rekurzija } #2) Rekurzija glave
Glavna rekurzija je vsak rekurzivni pristop, ki ni repna rekurzija. Torej je tudi splošna rekurzija prednja rekurzija.
Sintaksa rekurzije glave je naslednja:
methodName (T parametri...){ if (some_condition == true) { return methodName (T parametri...); } return result; } Rekurzija in iteracija v Javi
| Rekurzija | Iteracija |
|---|---|
| Rekurzija je postopek, pri katerem se metoda večkrat pokliče, dokler ni izpolnjen osnovni pogoj. | Iteracija je postopek, pri katerem se del kode izvaja določeno število krat ali dokler ni izpolnjen pogoj. |
| Je aplikacija za funkcije. | Uporablja se za zanke. |
| Dobro deluje pri manjši velikosti kode. | Dobro deluje pri večji velikosti kode. |
| Uporablja več pomnilnika, saj se vsak rekurzivni klic potisne na kup | Uporablja se sorazmerno manj pomnilnika. |
| Težko odpravljanje napak in vzdrževanje | Lažje odpravljanje napak in vzdrževanje |
| Če osnovni pogoj ni določen ali ni dosežen, pride do prepolnitve sklada. | Lahko se izvaja v neskončnost, vendar se bo ob morebitnih pomnilniških napakah izvajanje ustavilo. |
| Časovna zahtevnost je zelo visoka. | Časovna zahtevnost je relativno nižja. |
Pogosto zastavljena vprašanja
V #1) Kako deluje rekurzija v Javi?
Odgovor: Pri rekurziji rekurzivna funkcija večkrat pokliče samo sebe, dokler ni izpolnjen osnovni pogoj. Pomnilnik za klicano funkcijo se pomakne na sklad na vrh pomnilnika za kličočo funkcijo. Za vsak klic funkcije se naredi ločena kopija lokalnih spremenljivk.
Q #2) Zakaj se uporablja rekurzija?
Odgovor: Rekurzija se uporablja za reševanje tistih problemov, ki jih je mogoče razdeliti na manjše in celoten problem izraziti z manjšim problemom.
Rekurzija se uporablja tudi za tiste probleme, ki so preveč zapleteni, da bi jih lahko rešili z iterativnim pristopom. Poleg problemov, pri katerih časovna zapletenost ni problem, uporabite tudi rekurzijo.
Q #3) Kakšne so prednosti rekurzije?
Odgovor:
Prednosti rekurzije so:
- Rekurzija zmanjšuje odvečno klicanje funkcij.
- Rekurzija nam v primerjavi z iterativnim pristopom omogoča lažje reševanje problemov.
V #4) Katera možnost je boljša - rekurzija ali iteracija?
Odgovor: Rekurzija ponavlja klice, dokler se ne doseže osnovna funkcija. Tako se poveča količina pomnilnika, saj se pomnilnik za vsak klic funkcije potisne na sklad.
Iteracija po drugi strani nima veliko režijskega pomnilnika. Izvajanje rekurzije je počasnejše od iterativnega pristopa. Rekurzija zmanjša velikost kode, medtem ko iterativni pristop naredi kodo veliko.
Q #5) Katere so prednosti rekurzije pred iteracijo?
Odgovor:
- Zaradi rekurzije je koda jasnejša in krajša.
- Rekurzija je boljša od iterativnega pristopa pri problemih, kot so Hanojski stolp, obhodi dreves itd.
- Ker se pri vsakem klicu funkcije pomnilnik prenese na sklad, rekurzija porabi več pomnilnika.
- Rekurzija je počasnejša od iterativnega pristopa.
Zaključek
Rekurzija je zelo pomemben koncept v programski opremi ne glede na programski jezik. Rekurzija se večinoma uporablja pri reševanju problemov podatkovnih struktur, kot so Hanojski stolpi, obhodi dreves, povezani seznami itd. Rekurzija sicer zahteva več pomnilnika, vendar je zaradi nje koda enostavnejša in jasnejša.
V tem učbeniku smo raziskali vse o rekurziji. Za boljše razumevanje koncepta smo izvedli tudi številne primere programiranja.