Šajā padziļinātajā pamācībā par rekursiju Java valodā ir izskaidrots, kas ir rekursija ar piemēriem, tipiem un saistītiem jēdzieniem. Tā ietver arī rekursiju un iterāciju:
Iepriekšējās Java pamācībās mēs esam redzējuši iteratīvo pieeju, kurā deklarējam cilpu un pēc tam iteratīvi šķērsojam datu struktūru, ņemot pa vienam elementam.
Mēs esam redzējuši arī nosacījuma plūsmu, kur atkal saglabājam vienu cilpas mainīgo un atkārtojam kādu koda daļu, līdz cilpas mainīgais atbilst nosacījumam. Runājot par funkciju izsaukumiem, mēs izpētījām iteratīvo pieeju arī funkciju izsaukumiem.
Šajā pamācībā mēs aplūkosim atšķirīgu pieeju programmēšanai, t. i., rekursīvo pieeju.
Kas ir rekursija programmā Java?
Rekursija ir process, kurā funkcija vai metode izsauc pati sevi atkal un atkal. Šo funkciju, kas tiek izsaukta atkal un atkal tieši vai netieši, sauc par "rekursīvo funkciju".
Mēs apskatīsim dažādus piemērus, lai izprastu rekursiju. Tagad aplūkosim rekursijas sintaksi.
Rekursijas sintakse
Jebkurai metodei, kas īsteno rekursiju, ir divas galvenās daļas:
- Metodes izsaukums, kas var izsaukt pati sevi, t. i., rekursīva metode
- Priekšnosacījums, kas aptur rekursiju.
Ņemiet vērā, ka priekšnosacījums ir nepieciešams jebkurai rekursīvai metodei, jo, ja mēs nepārtrauksim rekursiju, tā turpinās darboties bezgalīgi un izraisīs kaudzes pārpildīšanos.
Vispārējā rekursijas sintakse ir šāda:
methodName (T parametri...) { if (precondition == true) //priekšnosacījums vai bāzes nosacījums { return result; } return methodName (T parametri...); //rekursīvs izsaukums } Ņemiet vērā, ka priekšnosacījumu sauc arī par bāzes nosacījumu. Par bāzes nosacījumu sīkāk runāsim nākamajā sadaļā.
Izpratne par rekursiju programmā Java
Šajā nodaļā mēs mēģināsim izprast rekursijas procesu un apskatīsim, kā tas notiek. Mēs uzzināsim par bāzes nosacījumu, kaudzes pārpildīšanos, redzēsim, kā konkrētu problēmu var atrisināt ar rekursijas palīdzību, un citas šādas detaļas.
Rekursijas pamatnosacījums
Rakstot rekursīvo programmu, vispirms ir jāsniedz risinājums bāzes gadījumam. Pēc tam lielāku problēmu izsakām ar mazākām problēmām.
Kā piemērs, mēs varam apskatīt klasisku skaitļa faktoriāla aprēķināšanas problēmu. Ja ir dots skaitlis n, mums ir jāatrod n faktoriāls, ko apzīmē ar n!
Tagad īstenosim programmu, lai aprēķinātu n faktoriālu (n!), izmantojot rekursiju.
public klase Main{ static int fact(int n) { if (n == 1) // pamatnosacījums return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + rezultāts); } } } } Izvades
Šajā programmā redzams, ka nosacījums (n<=1) ir bāzes nosacījums, un, kad šis nosacījums ir sasniegts, funkcija atgriež 1. Funkcijas daļa else ir rekursīvais izsaukums. Taču katru reizi, kad tiek izsaukta rekursīvā metode, n tiek samazināts par 1.
Tādējādi varam secināt, ka n vērtība galu galā kļūs 1 vai mazāka par 1, un šajā brīdī metode atgriezīs vērtību 1. Šis bāzes nosacījums tiks sasniegts, un funkcija apstāsies. Ņemiet vērā, ka n vērtība var būt jebkāda, ja vien tā atbilst bāzes nosacījumam.
Problēmu risināšana, izmantojot rekursiju
Rekursijas izmantošanas pamatideja ir izteikt lielāku problēmu ar mazākām problēmām. Turklāt mums ir nepieciešams pievienot vienu vai vairākus bāzes nosacījumus, lai mēs varētu iziet no rekursijas.
Tas jau tika demonstrēts iepriekš minētajā faktoriālā piemērā. Šajā programmā mēs izteicām n faktoriālu (n!) ar mazākām vērtībām un mums bija bāzes nosacījums (n <=1), lai, kad n sasniedz 1, mēs varētu pārtraukt rekursīvo metodi.
Stack Overflow kļūda rekursijā
Mēs zinām, ka, izsaucot jebkuru metodi vai funkciju, tās stāvoklis tiek saglabāts kaudzē un tiek atgūts, kad funkcija atgriežas. Kaudzi izmanto arī rekursīvās metodes gadījumā.
Bet rekursijas gadījumā var rasties problēma, ja nav definēts bāzes nosacījums vai ja bāzes nosacījums kaut kādā veidā netiek sasniegts vai izpildīts. Ja šāda situācija rodas, tad var rasties kaudzes pārplūšana.
Aplūkosim turpmāk sniegto faktoriālā apzīmējuma piemēru.
Šeit ir dots nepareizs pamatnosacījums, n = 100.
public klase Main { static int fact(int n) { if (n == 100) // bāzes nosacījums, kas izraisa kaudzes pārpildīšanos return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } } Tātad, kad n> 100, metode atgriezīs 1, bet rekursija neapstāsies. n vērtība turpinās samazināties bezgalīgi, jo nav citu nosacījumu, lai to apturētu. Tas turpināsies, līdz kaudze pārpildīsies.
Cits gadījums būs, ja vērtība n <100. Arī šajā gadījumā metode nekad neizpildīs pamatnosacījumu un izraisīs kaudzes pārpildīšanos.
Rekursijas piemēri programmā Java
Šajā sadaļā mēs īstenosim šādus piemērus, izmantojot rekursiju.
#1) Fibonači sērijas, izmantojot rekursiju
Fibonači rindu veido,
1,1,2,3,5,8,13,21,34,55,…
Iepriekšminētā secība rāda, ka pašreizējais elements ir divu iepriekšējo elementu summa. Arī Fibonači virknes pirmais elements ir 1.
Tātad vispārīgi, ja n ir pašreizējais skaitlis, tad to nosaka (n-1) un (n-2) summa. Tā kā pašreizējais elements ir izteikts ar iepriekšējiem elementiem, mēs varam izteikt šo problēmu, izmantojot rekursiju.
Programma Fibonači sērijas īstenošanai ir dota tālāk:
public class Main { //metode fibonači sērijas aprēķināšanai 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 fibonači sērijas pirmie 10 skaitļi System.out.println ("Fibonači sērija: Pirmie 10 skaitļi:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Izvades
#2) Pārbaudiet, vai skaitlis ir palindroms, izmantojot rekursiju
Palindroms ir secība, kas ir vienāda, lasot to no kreisās puses pa labi vai no labās puses pa kreisi.
Ja dots skaitlis 121, redzam, ka, lasot to no kreisās puses pa labi un no labās puses pa kreisi, tas ir vienāds. Tātad skaitlis 121 ir palindroms.
Ņemsim vēl vienu skaitli, 1242. Lasot to no kreisās puses uz labo, tas ir 1242, bet lasot no labās puses uz kreiso, tas ir 2421. Tādējādi šis nav palindroms.
Mēs īstenojam palindroma programmu, apgriežot skaitļu ciparus un rekursīvi salīdzinot doto skaitli ar tā apgriezto attēlojumu.
Zemāk redzamajā programmā ir ieviesta programma palindroma pārbaudei.
import java.io.*; import java.util.*; public class Main { // pārbaudiet, vai num satur tikai vienu ciparu public static int oneDigit(int num) { if ((num>= 0) &&& (num <10)) return 1; else return 0; } //palindroma utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // bāzes nosacījums; return if num=0 if (num == 0) { return revNum; } else { //calllietderības funkcija rekursīvi revNum = isPalindrome_util(num / 10, revNum); } // Pārbaudiet, vai num un revNum pirmais cipars ir vienāds if (num % 10 == revNum % 10) { // ja jā, revNum pārvietosies kopā ar num return revNum / 10; } else { // izejiet throw new Exception(); } } } //metode, lai pārbaudītu, vai dotais skaitlis ir palindroms, izmantojot palindroma utility funkciju public static int isPalindrome(int num) throwsException { 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("Jā, dotais skaitlis " + n + " ir palindroms."); } catch (Exception e) { System.out.println("Ne, dotais skaitlis " + n + " nav palindroms."); } n = 1221; try { isPalindrome(n);System.out.println("Jā, dotais skaitlis " + n + " ir palindroms."); } catch (Exception e) { System.out.println("Nē, dotais skaitlis " + n + " nav palindroms."); } } } } } Izvades
#3) Reversā virknes rekursija Java
Dotā virkne "Hello" ir jāmaina tā, lai iegūtā virkne būtu "olleH".
Sākot no pēdējās virknes pēdējās rakstzīmes, mēs rekursīvi izdrukājam katru rakstzīmi, līdz visas virknes rakstzīmes ir izsmeltas.
Tālāk redzamajā programmā tiek izmantota rekursija, lai apgrieztu doto virkni.
klase String_Reverse { //rekursīvā metode dotās virknes apgriešanai void reverseString(String str) { //bāzes nosacījums; atgriezt, ja virkne ir nulle vai ar 1 vai mazāk rakstzīmēm if ((str==null)} } } } } klase Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Dotā virkne: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Apvērstā virkne: "); obj.reverseString(inputstr); } } } } Izvades
#4) Binary Search Java Rekursija
Binārais meklēšanas algoritms ir slavens meklēšanas algoritms. Šajā algoritmā, ja dots sakārtots masīvs ar n elementiem, mēs meklējam šajā masīvā doto atslēgas elementu. Sākumā mēs sadalām masīvu divās daļās, atrodot masīva vidējo elementu.
Pēc tam atkarībā no tā, vai atslēga atrodas vidū, mēs ierobežojam meklēšanu masīva pirmajā vai otrajā pusē. Šādā veidā tiek atkārtots tas pats process, līdz tiek atrasta atslēgas elementu atrašanās vieta.
Šeit mēs šo algoritmu īstenosim, izmantojot rekursiju.
import java.util.*; class Binary_Search { // rekursīva bināra meklēšana int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { // aprēķina masīva vidu int mid = left + (right - left) / 2; // ja atslēga ir mid, atgriež mid if (numArray[mid] == key) return mid; // ja atslēga key) return binarySearch(numArray, left, mid - 1, key); // Citādi rekursīvi meklētright subarray return binarySearch(numArray, mid + 1, right, key); } // masīvā nav elementu, return -1 return -1; } } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //deklarē un izdrukā masīvu int numArray[] = { 4,6,6,12,16,22}; System.out.println("Dotais masīvs : " + Arrays.toString(numArray))); int len = numArray.length; //marina garumsint key = 16; //meklējamais atslēga int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Elementa " + key + " nav"); else System.out.println("Elements " + key + " atrasts ar indeksu " + result); } } } Izvades
#5) Atrast minimālo vērtību masīvā, izmantojot rekursiju
Izmantojot rekursiju, mēs varam atrast arī minimālo vērtību masīvā.
Zemāk ir dota Java programma, lai atrastu minimālo vērtību masīvā.
import java.util.*; klase Main { static int getMin(int numArray[], int i, int n) { //atgriež pirmo elementu, ja ir tikai viens elements vai minimums no masīva elementiem 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("Dotais masīvs : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Minimālais masīva elements: " + getMin(numArray, 0, n) + "\n"); } } } Izvades
Šie ir daži no rekursijas piemēriem. Papildus šiem piemēriem daudzas citas programmatūras problēmas var īstenot, izmantojot rekursijas metodes.
Rekursijas tipi
Rekursija ir divu veidu atkarībā no tā, kad tiek izsaukta rekursīvā metode.
Tās ir:
#1) Rekursija uz astes
Ja rekursīvās metodes izsaukums ir pēdējais rekursīvās metodes iekšienē izpildītais izteikums, to sauc par "rekursiju uz beigām".
Izmantojot astes rekursiju, rekursīvā izsaukuma paziņojums parasti tiek izpildīts kopā ar metodes atgriešanas paziņojumu.
Turpmāk ir dota vispārējā astes rekursijas sintakse:
methodName ( T parametri...){ { { if (base_condition == true) { return result; } return methodName (T parametri...) //rekursija uz astes } #2) Vadītāja rekursija
Vadošā rekursija ir jebkura rekursīvā pieeja, kas nav astes rekursija. Tātad pat vispārējā rekursija ir priekšējā rekursija.
Galvas rekursijas sintakse ir šāda:
methodName (T parametri...){ if (some_condition == true) { return methodName (T parametri...); } return result; } } Rekursija un iterācija Java valodā
| Rekursija | Iterācija |
|---|---|
| Rekursija ir process, kurā metode pati sevi izsauc atkārtoti, līdz tiek izpildīts kāds pamatnosacījums. | Iterācija ir process, kurā koda daļa tiek atkārtoti izpildīta noteiktu reižu skaitu vai kamēr tiek izpildīts kāds nosacījums. |
| Vai pieteikums funkcijām. | Attiecas uz cilpām. |
| Labi darbojas mazāka izmēra kodiem. | Labi darbojas arī lielāka izmēra kodiem. |
| Izmanto vairāk atmiņas, jo katrs rekursīvais izsaukums tiek ievietots kaudzē. | Tiek izmantots salīdzinoši mazāk atmiņas. |
| Grūti atkļūdošana un uzturēšana | Vieglāk atkļūdošana un uzturēšana |
| Rezultāts ir kaudzes pārplūšana, ja pamatnosacījums nav norādīts vai nav sasniegts. | Var izpildīt bezgalīgi, bet galu galā pārtrauks izpildi, ja tiks pieļautas jebkādas atmiņas kļūdas. |
| Laika sarežģītība ir ļoti liela. | Laika sarežģītība ir relatīvi zemāka. |
Biežāk uzdotie jautājumi
1. jautājums) Kā Java programmā darbojas rekursija?
Atbilde: Rekursijā rekursīvā funkcija izsauc pati sevi atkārtoti, līdz tiek izpildīts bāzes nosacījums. Izsauktās funkcijas atmiņa tiek ievietota kaudzē izsaucošās funkcijas atmiņas augšpusē. Katram funkcijas izsaukumam tiek izveidota atsevišķa lokālo mainīgo kopija.
Q #2) Kāpēc tiek izmantota rekursija?
Atbilde: Rekursiju izmanto, lai atrisinātu tās problēmas, kuras var sadalīt mazākās un visu problēmu var izteikt ar mazāku problēmu.
Rekursiju izmanto arī tām problēmām, kuras ir pārāk sarežģītas, lai tās atrisinātu, izmantojot iteratīvo pieeju. Papildus problēmām, kurām laika sarežģītība nav problēma, izmantojiet rekursiju.
Q #3) Kādas ir rekursijas priekšrocības?
Atbilde:
Rekursijas priekšrocības:
- Rekursija samazina lieku funkciju izsaukšanu.
- Rekursija ļauj viegli atrisināt problēmas, salīdzinot ar iteratīvo pieeju.
Q #4) Kurš ir labāks - rekursija vai iterācija?
Atbilde: Rekursija veic atkārtotus izsaukumus, līdz tiek sasniegta bāzes funkcija. Tādējādi rodas atmiņas pieskaitāmās izmaksas, jo atmiņa katram funkcijas izsaukumam tiek ievietota kaudzē.
No otras puses, iterācijai nav lielas atmiņas pieskaitāmās izmaksas. Rekursijas izpilde ir lēnāka nekā iteratīvā pieeja. Rekursija samazina koda apjomu, savukārt iteratīvā pieeja padara kodu lielu.
Q #5) Kādas ir rekursijas priekšrocības salīdzinājumā ar iterāciju?
Atbilde:
- Rekursija padara kodu skaidrāku un īsāku.
- Rekursija ir labāka nekā iteratīvā pieeja tādām problēmām kā Hanojas tornis, koku šķērsošana utt.
- Tā kā katram funkcijas izsaukumam kaudzē tiek ievietota atmiņa, rekursija izmanto vairāk atmiņas.
- Rekursijas veiktspēja ir lēnāka nekā iteratīvā pieeja.
Secinājums
Rekursija ir ļoti svarīgs jēdziens programmatūrā neatkarīgi no programmēšanas valodas. Rekursiju galvenokārt izmanto, risinot datu struktūras problēmas, piemēram, Hanojas torņus, koku pārlūkošanu, saistītus sarakstus u. c. Lai gan tā aizņem vairāk atmiņas, rekursija padara kodu vienkāršāku un skaidrāku.
Šajā pamācībā mēs esam izpētījuši visu par rekursiju. Labākai šī jēdziena izpratnei mēs esam ieviesuši arī daudzus programmēšanas piemērus.