Šioje išsamioje pamokoje apie rekursiją Java kalba paaiškinama, kas yra rekursija su pavyzdžiais, tipais ir susijusiomis sąvokomis. Joje taip pat aptariama rekursija ir iteracija:
Ankstesnėse "Java" pamokose matėme iteracinį metodą, kai deklaruojame kilpą ir iteraciniu būdu pereiname per duomenų struktūrą imdami po vieną elementą.
Taip pat matėme sąlyginį srautą, kai vėl laikome vieną ciklo kintamąjį ir kartojame kodo dalį tol, kol ciklo kintamasis atitinka sąlygą. Kai kalbama apie funkcijų iškvietimus, taip pat tyrinėjome iteracinį funkcijų iškvietimų metodą.
Šioje pamokoje aptarsime kitokį požiūrį į programavimą, t. y. rekursinį požiūrį.
Kas yra "Java" rekursija?
Rekursija - tai procesas, kurio metu funkcija arba metodas vėl ir vėl kviečia save patį. Ši funkcija, kuri tiesiogiai arba netiesiogiai kviečiama vėl ir vėl, vadinama "rekursine funkcija".
Kad suprastume rekursiją, pamatysime įvairių pavyzdžių. Dabar susipažinkime su rekursijos sintakse.
Rekursijos sintaksė
Bet kuris metodas, įgyvendinantis rekursiją, turi dvi pagrindines dalis:
- Metodo iškvietimas, kuris gali iškviesti pats save, t. y. rekursinis
- Išankstinė sąlyga, kuri sustabdys rekursiją.
Atkreipkite dėmesį, kad išankstinė sąlyga būtina bet kuriam rekursiniam metodui, nes jei nenutrauksime rekursijos, ji bus vykdoma be galo ilgai ir dėl to stekas bus perpildytas.
Bendroji rekursijos sintaksė yra tokia:
methodName (T parametrai...) { if (precondition == true) //precondition arba bazinė sąlyga { return result; } return methodName (T parametrai...); //rekursinis iškvietimas } Atkreipkite dėmesį, kad išankstinė sąlyga dar vadinama bazine sąlyga. Daugiau apie bazinę sąlygą aptarsime kitame skyriuje.
Rekursijos supratimas "Java
Šiame skyriuje pabandysime suprasti rekursijos procesą ir pamatyti, kaip jis vyksta. Sužinosime apie bazinę sąlygą, kamino perpildymą, pamatysime, kaip konkrečią problemą galima išspręsti naudojant rekursiją ir kitas panašias detales.
Rekursijos bazinė sąlyga
Rašydami rekursinę programą, pirmiausia turėtume pateikti bazinio atvejo sprendimą. Tada didesnę problemą išreiškiame mažesnėmis problemomis.
Kaip pavyzdys, galime imtis klasikinio skaičiaus faktorialo apskaičiavimo uždavinio. Turėdami skaičių n, turime rasti n faktorialą, žymimą n!
Dabar įgyvendinkime programą n faktorialiui (n!) apskaičiuoti, naudodami rekursiją.
public class Main{ static int fact(int n) { if (n == 1) // bazinė sąlyga return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Išėjimas
Šioje programoje matome, kad sąlyga (n<=1) yra bazinė sąlyga ir, kai ši sąlyga pasiekiama, funkcija grąžina 1. Funkcijos dalis else yra rekursinis iškvietimas. Tačiau kiekvieną kartą, kai iškviečiamas rekursinis metodas, n mažinamas 1.
Taigi galime daryti išvadą, kad galiausiai n reikšmė taps 1 arba mažesnė už 1 ir tuo metu metodas grąžins reikšmę 1. Ši bazinė sąlyga bus pasiekta ir funkcija bus sustabdyta. Atkreipkite dėmesį, kad n reikšmė gali būti bet kokia, jei ji tenkina bazinę sąlygą.
Problemų sprendimas naudojant rekursiją
Pagrindinė rekursijos naudojimo idėja yra išreikšti didesnę problemą mažesnėmis problemomis. Be to, turime pridėti vieną ar daugiau bazinių sąlygų, kad galėtume išeiti iš rekursijos.
Tai jau buvo pademonstruota pirmiau pateiktame faktorialo pavyzdyje. Šioje programoje n faktorialą (n!) išreiškėme mažesnėmis reikšmėmis ir turėjome bazinę sąlygą (n <=1), kad, n pasiekus 1, galėtume baigti rekursinį metodą.
Stack Overflow klaida rekursijoje
Žinome, kad iškvietus bet kurį metodą ar funkciją, funkcijos būsena saugoma steke ir yra atstatoma, kai funkcija grįžta. Stekas naudojamas ir rekursyviniam metodui.
Tačiau rekursijos atveju gali kilti problemų, jei neapibrėšime bazinės sąlygos arba kai bazinė sąlyga niekaip nepasiekiama ar nevykdoma. Jei tokia situacija susiklosto, gali atsirasti kamino perpildymas.
Panagrinėkime toliau pateiktą faktorialo užrašymo pavyzdį.
Šiuo atveju pateikėme neteisingą bazinę sąlygą - n==100.
public class Main { static int fact(int n) { if (n == 100) // bazinė sąlyga, dėl kurios perpildomas stekas return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Taigi, kai n> 100, metodas grąžins 1, bet rekursija nesustos. n reikšmė mažės neribotą laiką, nes nėra jokios kitos sąlygos, kuri ją sustabdytų. Tai tęsis tol, kol stekas bus perpildytas.
Kitas atvejis bus, kai n reikšmė <100. Šiuo atveju metodas taip pat niekada nevykdys bazinės sąlygos ir dėl to krūva bus perpildyta.
Rekursijos pavyzdžiai "Java
Šiame skyriuje toliau pateiktus pavyzdžius įgyvendinsime naudodami rekursiją.
#1) Fibonačio eilutės naudojant rekursiją
Fibonačio eilutė yra tokia,
1,1,2,3,5,8,13,21,34,55,…
Pirmiau pateikta seka rodo, kad dabartinis elementas yra dviejų ankstesnių elementų suma. Be to, pirmasis Fibonačio eilės elementas yra 1.
Taigi apskritai, jei n yra dabartinis skaičius, tai jį nusako (n-1) ir (n-2) suma. Kadangi dabartinis elementas išreiškiamas ankstesnių elementų terminais, šį uždavinį galime išreikšti naudodami rekursiją.
Toliau pateikiama programa, skirta Fibonačio serijai įgyvendinti:
public class Main { //metodas fibonacci serijai apskaičiuoti 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; //spausdinti pirmuosius 10 fibonacci serijos skaičių System.out.println ("Fibonacci serija: pirmieji 10 skaičių:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Išėjimas
#2) Patikrinkite, ar skaičius yra palindromas, naudodami rekursiją
Palindromas - tai seka, kuri yra vienoda, kai ją skaitome iš kairės į dešinę arba iš dešinės į kairę.
Turėdami skaičių 121, matome, kad skaitant jį iš kairės į dešinę ir iš dešinės į kairę, jis yra vienodas. Vadinasi, skaičius 121 yra palindromas.
Paimkime kitą skaičių - 1242. Kai skaitome jį iš kairės į dešinę, jis yra 1242, o kai skaitome iš dešinės į kairę - 2421. Taigi tai nėra palindromas.
Palindromo programą įgyvendiname sukeisdami skaičių skaitmenis vietomis ir rekursyviai lygindami duotą skaičių su jo atvirkštine reprezentacija.
Toliau pateiktoje programoje įgyvendinama palindromo tikrinimo programa.
import java.io.*; import java.util.*; public class Main { // patikrinti, ar num yra tik vienas skaitmuo 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 { // bazinė sąlyga; return if num=0 if (num == 0) { return revNum; } else { //callnaudingumo funkcija rekursiškai revNum = isPalindrome_util(num / 10, revNum); } // Patikrinkite, ar pirmieji numerio ir revNum skaitmenys yra vienodi if (num % 10 == revNum % 10) { // jei taip, revNum judės kartu su numeriu return revNum / 10; } else { // exit throw new Exception(); } } } //metodas, skirtas patikrinti, ar duotas skaičius yra palindromas, naudojant palindromo naudingumo funkciją public static int isPalindrome(int num) throwsIšimtis { 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("Taip, duotas skaičius " + n + " yra palindromas."); } catch (Išimtis e) { System.out.println("Ne, duotas skaičius " + n + " nėra palindromas."); } n = 1221; try { isPalindrome(n);System.out.println("Taip, duotas skaičius " + n + " yra palindromas."); } catch (Išimtis e) { System.out.println("Ne, duotas skaičius " + n + " nėra palindromas."); } } } } } Išėjimas
#3) Atvirkštinė eilutės rekursija Java
Gavę eilutę "Hello", turime ją pakeisti taip, kad gautoji eilutė būtų "olleH".
Tai atliekama naudojant rekursiją. Pradėdami nuo paskutinio eilutės simbolio, rekursiškai spausdiname kiekvieną simbolį, kol išnaudojame visus eilutės simbolius.
Toliau pateiktoje programoje naudojama rekursija, kad būtų galima pakeisti duotą eilutę.
klasė String_Reverse { //rekursinis metodas duotai eilutei apversti void reverseString(String str) { //bazinė sąlyga; grąžinti, jei eilutė yra nulinė arba turi 1 ar mažiau simbolių if ((str==null)} } } } klasė Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Pateikta eilutė: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Apversta eilutė: "); obj.reverseString(inputstr); } } } } Išėjimas
#4) Dvejetainė paieška "Java" rekursija
Dvejetainis paieškos algoritmas yra žinomas paieškos algoritmas. Šiuo algoritmu, turėdami surūšiuotą n elementų masyvą, ieškome šiame masyve nurodyto raktinio elemento. Pradžioje masyvą padalijame į dvi dalis, surasdami vidurinį masyvo elementą.
Tada, priklausomai nuo to, ar raktas viduryje, paiešką apribojame pirmoje, ar antroje masyvo pusėje. Taip tas pats procesas kartojamas tol, kol randama rakto elementų vieta.
Šį algoritmą įgyvendinsime naudodami rekursiją.
import java.util.*; class Binary_Search { // rekursinė dvejetainė paieška int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //apskaičiuokite masyvo vidurį int mid = left + (right - left) / 2; // jei raktas yra ties viduriu, grąžinkite mid if (numArray[mid] == key) return mid; // jei raktas key) return binarySearch(numArray, left, mid - 1, key); // Kitaip rekursinė paieškaright subarray return binarySearch(numArray, mid + 1, right, key); } // elementų masyve nėra, return -1 return -1; } } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //deklaruokite ir spausdinkite masyvą int numArray[] = { 4,6,12,16,22}; System.out.println("Duotas masyvas : " + Arrays.toString(numArray))); int len = numArray.length; //masyvo ilgisint key = 16; // ieškomas raktas int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Elemento " + key + " nėra"); else System.out.println("Elementas " + key + " rastas indeksu " + result); } } } Išėjimas
#5) Rasti mažiausią reikšmę masyve naudojant rekursiją
Naudodami rekursiją taip pat galime rasti mažiausią reikšmę masyve.
Toliau pateikta "Java" programa, skirta mažiausiai reikšmei masyve rasti.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //grąžinamas pirmas elementas, jei yra tik vienas elementas, arba mažiausias masyvo elementas 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("Duotas masyvas : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Mažiausias masyvo elementas: " + getMin(numArray, 0, n) + "\n"); } } } Išėjimas
Tai keletas rekursijos pavyzdžių. Be šių pavyzdžių, daugelį kitų programinės įrangos problemų galima įgyvendinti naudojant rekursijos metodus.
Rekursijos tipai
Rekursija yra dviejų tipų, atsižvelgiant į tai, kada iškviečiamas rekursinis metodas.
Tai:
#Nr. 1) Rekursija ant uodegos
Kai rekursyvaus metodo iškvietimas yra paskutinis rekursyvaus metodo viduje vykdomas teiginys, tai vadinama "galine rekursija".
Naudojant uodegos rekursiją, rekursinis iškvietimo sakinys paprastai vykdomas kartu su metodo grąžinimo sakiniu.
Toliau pateikiama bendra uodegos rekursijos sintaksė:
methodName ( T parametrai...){ { { if (base_condition == true) { return result; } return methodName (T parametrai...) //tail recursion } #2) Galvos rekursija
Pagrindinė rekursija yra bet koks rekursinis metodas, kuris nėra uodegos rekursija. Taigi net bendroji rekursija yra priekinė rekursija.
Galvos rekursijos sintaksė yra tokia:
methodName (T parametrai...){ if (some_condition == true) { return methodName (T parametrai...); } return result; } Rekursija ir iteracija "Java
| Rekursija | Iteracija |
|---|---|
| Rekursija - tai procesas, kai metodas pats save kviečia pakartotinai, kol įvykdoma pagrindinė sąlyga. | Iteracija - tai procesas, kurio metu kodo fragmentas kartojamas tam tikrą skaičių kartų arba tol, kol įvykdoma tam tikra sąlyga. |
| Ar tai yra funkcijoms skirta paraiška. | Taikoma kilpoms. |
| Gerai veikia mažesnio dydžio kodams. | Gerai tinka didesnio dydžio kodams. |
| Naudojama daugiau atminties, nes kiekvienas rekursinis iškvietimas perkeliamas į steką. | Naudojama palyginti mažiau atminties. |
| Sudėtinga derinti ir prižiūrėti | Lengviau derinti ir prižiūrėti |
| Jei pagrindinė sąlyga nenurodyta arba nepasiekta, atsiranda kamino perpildymas. | Gali būti vykdomas be galo ilgai, bet galiausiai bus sustabdytas, jei bus padaryta atminties klaidų. |
| Laiko sudėtingumas yra labai didelis. | Laiko sudėtingumas yra santykinai mažesnis. |
Dažnai užduodami klausimai
Klausimas Nr. 1) Kaip "Java" veikia rekursija?
Atsakymas: Rekursijos atveju rekursinė funkcija pati save kviečia pakartotinai, kol įvykdoma bazinė sąlyga. Kviečiamos funkcijos atmintis perkeliama į steką, esantį kviečiančiosios funkcijos atminties viršuje. Kiekvienam funkcijos iškvietimui sukuriama atskira vietinių kintamųjų kopija.
Q #2) Kodėl naudojama rekursija?
Atsakymas: Rekursija naudojama sprendžiant tas problemas, kurias galima suskaidyti į mažesnes, o visą problemą galima išreikšti mažesne problema.
Rekursija taip pat naudojama tiems uždaviniams, kurie yra per sudėtingi, kad juos būtų galima išspręsti taikant iteracinį metodą. Be uždavinių, kuriems laiko sudėtingumas nėra problema, naudokite rekursiją.
Q #3) Kokie yra rekursijos privalumai?
Atsakymas:
Rekursijos privalumai:
- Rekursija sumažina nereikalingų funkcijų iškvietimų skaičių.
- Palyginti su iteraciniu metodu, rekursija leidžia lengviau spręsti problemas.
4 klausimas) Kuris iš jų geresnis - rekursija ar iteracija?
Atsakymas: Rekursija atlieka pakartotinius iškvietimus, kol pasiekiama bazinė funkcija. Todėl atsiranda atminties sąnaudos, nes kiekvieno funkcijos iškvietimo atmintis perkeliama į steką.
Kita vertus, iteracija neturi didelių atminties sąnaudų. Rekursijos vykdymas yra lėtesnis nei iteracinis metodas. Rekursija sumažina kodo dydį, o iteracinis metodas padaro kodą didelį.
Q #5) Kokie yra rekursijos pranašumai prieš iteraciją?
Atsakymas:
- Dėl rekursijos kodas tampa aiškesnis ir trumpesnis.
- Rekursija yra geresnė už iteracinį metodą sprendžiant tokias problemas, kaip Hanojos bokštas, medžių kirtimai ir pan.
- Kadangi kiekvieno funkcijos skambučio atmintis perkeliama į steką, rekursija naudoja daugiau atminties.
- Rekursijos veikimas yra lėtesnis nei iteracinis metodas.
Išvada
Rekursija yra labai svarbi programinės įrangos sąvoka, nepriklausomai nuo programavimo kalbos. Rekursija dažniausiai naudojama sprendžiant duomenų struktūros problemas, pavyzdžiui, Hanojos bokštų, medžių naršymo, susietųjų sąrašų ir t. t. Nors rekursija užima daugiau atminties, tačiau kodas tampa paprastesnis ir aiškesnis.
Šioje mokomojoje programoje išnagrinėjome viską apie rekursiją. Taip pat įgyvendinome daug programavimo pavyzdžių, kad geriau suprastumėte šią sąvoką.