Tämä syvällinen opetusohjelma rekursiosta Javassa selittää, mitä rekursio on esimerkkien, tyyppien ja siihen liittyvien käsitteiden avulla. Se kattaa myös rekursio vs. toistaminen:
Aikaisemmissa Javan opetusohjelmissamme olemme nähneet iteratiivisen lähestymistavan, jossa ilmoitamme silmukan ja käymme sitten läpi tietorakenteen iteratiivisesti ottamalla yhden elementin kerrallaan.
Olemme nähneet myös ehdollisen virtauksen, jossa säilytämme jälleen yhden silmukkamuuttujan ja toistamme koodinpätkän, kunnes silmukkamuuttuja täyttää ehdon. Kun on kyse funktiokutsuista, tutkimme myös iteratiivista lähestymistapaa funktiokutsuihin.
Tässä opetusohjelmassa käsittelemme erilaista lähestymistapaa ohjelmointiin eli rekursiivista lähestymistapaa.
Mikä on rekursio Javassa?
Rekursio on prosessi, jossa funktio tai menetelmä kutsuu itseään uudelleen ja uudelleen. Tätä funktiota, jota kutsutaan uudelleen ja uudelleen joko suoraan tai epäsuorasti, kutsutaan "rekursiiviseksi funktioksi".
Näemme erilaisia esimerkkejä rekursiivisuuden ymmärtämiseksi. Katsotaanpa nyt rekursiivisuuden syntaksia.
Rekursion syntaksi
Kaikissa rekursiota toteuttavissa menetelmissä on kaksi perusosaa:
- Menetelmäkutsu, joka voi kutsua itseään eli rekursiivinen.
- Ennakkoehto, joka pysäyttää rekursion.
Huomaa, että ennakkoehto on välttämätön kaikissa rekursiivisissa menetelmissä, sillä jos emme katkaise rekursiota, se jatkuu loputtomiin ja johtaa pinon ylivuotoon.
Rekursion yleinen syntaksi on seuraava:
methodName (T parametrit...) { if (precondition == true) //precondition tai perusehto { return result; } return methodName (T parametrit...); //rekursiivinen kutsu } Huomaa, että ennakkoehtoa kutsutaan myös perusehdoksi. Käsittelemme perusehtoa tarkemmin seuraavassa luvussa.
Rekursion ymmärtäminen Javassa
Tässä osiossa yritämme ymmärtää rekursioprosessia ja nähdä, miten se tapahtuu. Opimme perusehdosta, pinon ylivuodosta ja näemme, miten tietty ongelma voidaan ratkaista rekursiolla ja muilla vastaavilla yksityiskohdilla.
Rekursio Perusehto
Kun kirjoitamme rekursiivista ohjelmaa, meidän on ensin annettava ratkaisu perustapaukselle. Sitten ilmaisemme suuremman ongelman pienempien ongelmien avulla.
Koska esimerkki, voimme ottaa klassisen ongelman, joka koskee luvun faktoriaalin laskemista. Kun on annettu luku n, meidän on löydettävä n:n faktoriaali, jota merkitään n!
Toteutetaan nyt ohjelma, joka laskee n:n faktoriaalin (n!) käyttämällä rekursiota.
public class Main{ static int fact(int n) { if (n == 1) // perusehto return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! =" + result); } } Lähtö
Tässä ohjelmassa näemme, että ehto (n<=1) on perusehto, ja kun tämä ehto saavutetaan, funktio palauttaa arvon 1. Funktion else-osa on rekursiivinen kutsu. Mutta joka kerta, kun rekursiivista menetelmää kutsutaan, n pienenee 1:llä.
Voimme siis päätellä, että lopulta n:n arvoksi tulee 1 tai pienempi kuin 1, ja tässä vaiheessa metodi palauttaa arvon 1. Tämä perusehto saavutetaan ja funktio pysähtyy. Huomaa, että n:n arvo voi olla mikä tahansa, kunhan se täyttää perusehdon.
Ongelmanratkaisu rekursion avulla
Rekursion käytön perusajatuksena on ilmaista suurempi ongelma pienempien ongelmien avulla. Lisäksi meidän on lisättävä yksi tai useampi perusehto, jotta pääsemme pois rekursiosta.
Tämä osoitettiin jo edellä olevassa faktoriaaliesimerkissä. Tässä ohjelmassa ilmaisimme n faktoriaalin (n!) pienempien arvojen avulla ja meillä oli perusehto (n <=1), jotta kun n saavuttaa arvon 1, voimme lopettaa rekursiivisen menetelmän.
Stack Overflow -virhe rekursiossa
Tiedämme, että kun mitä tahansa metodia tai funktiota kutsutaan, funktion tila tallennetaan pinoon ja haetaan takaisin, kun funktio palaa. Pino on käytössä myös rekursiivisessa metodissa.
Rekursiossa voi kuitenkin syntyä ongelma, jos emme määrittele perusehtoa tai jos perusehtoa ei jollakin tavalla saavuteta tai suoriteta. Jos näin käy, pino voi ylivuotaa.
Tarkastellaan alla olevaa esimerkkiä faktoriaalin merkitsemisestä.
Tässä on annettu väärä perusehto, n==100.
public class Main { static int fact(int n) { if (n == 100) // perusehto johtaa pinon ylivuotoon return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Joten kun n> 100 metodi palauttaa 1, mutta rekursio ei lopu. n:n arvo pienenee loputtomiin, koska mikään muu ehto ei pysäytä sitä. Tämä jatkuu, kunnes pino täyttyy.
Toinen tapaus on, kun arvo n <100. Myös tässä tapauksessa menetelmä ei koskaan suorita perusehtoa ja johtaa pinon ylivuotoon.
Rekursion esimerkkejä Javassa
Tässä osassa toteutetaan seuraavat esimerkit rekursiota käyttäen.
#1) Fibonacci-sarja rekursion avulla
Fibonacci-sarja saadaan seuraavasti,
1,1,2,3,5,8,13,21,34,55,…
Yllä oleva sarja osoittaa, että nykyinen alkio on kahden edellisen alkion summa. Myös Fibonaccin sarjan ensimmäinen alkio on 1.
Jos siis n on nykyinen luku, se saadaan (n-1) ja (n-2) summana. Koska nykyinen alkio ilmaistaan aikaisempien alkioiden suhteen, voimme ilmaista tämän ongelman käyttämällä rekursiota.
Fibonaccin sarjan toteuttamiseen tarkoitettu ohjelma on esitetty alla:
public class Main { //menetelmä fibonaccisarjan laskemiseksi 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; // tulostaa fibonaccisarjan 10 ensimmäistä numeroa System.out.println ("Fibonaccisarja: 10 ensimmäistä numeroa:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Lähtö
#2) Tarkista, onko numero palindromi käyttämällä rekursiota.
Palindromi on merkkijono, joka on sama, kun sitä luetaan vasemmalta oikealle tai oikealta vasemmalle.
Jos luku 121 luetaan vasemmalta oikealle ja oikealta vasemmalle, se on yhtä suuri. 121 on siis palindromi.
Otetaan toinen luku, 1242. Kun sitä luetaan vasemmalta oikealle, se on 1242, ja kun sitä luetaan oikealta vasemmalle, se on 2421. Kyseessä ei siis ole palindromi.
Toteutamme palindromiohjelman kääntämällä numeroiden numerot päinvastaisiksi ja vertaamalla rekursiivisesti annettua lukua sen käänteiseen esitykseen.
Alla oleva ohjelma toteuttaa ohjelman palindromin tarkistamiseksi.
import java.io.*; import java.util.*; public class Main { // tarkista, sisältääkö num vain yhden numeron public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //palindrome aputoiminto public static int isPalindrome_util (int num, int revNum) throws Exception { //perusehto; palaa jos num=0 if (num == 0) { return revNum; } else { //kutsu.aputoiminto rekursiivisesti revNum = isPalindrome_util(num / 10, revNum); } // Tarkista, onko num:n ja revNum:n ensimmäinen numero sama if (num % 10 == revNum % 10) { // jos kyllä, revNum siirtyy num:n mukana return revNum / 10; } else { // exit throw new Exception(); } } } //menetelmä, jolla tarkistetaan, onko annettu luku palindromi palindromi käyttäen palindromi aputoimintoa public static int isPalindromi(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("Kyllä, annettu luku " + n + " on palindromi."); } catch (Exception e) { System.out.println("Ei, annettu luku " + n + " ei ole palindromi."); } n = 1221; try { isPalindrome(n);System.out.println("Kyllä, annettu luku " + n + " on palindromi."); } catch (Exception e) { System.out.println("Ei, annettu luku " + n + " ei ole palindromi."); } } } } Lähtö
#3) Käänteinen merkkijonorekurssi Java
Kun annetaan merkkijono "Hello", meidän on käännettävä se niin, että tuloksena on merkkijono "olleH".
Tämä tehdään rekursiota käyttäen. Alkaen merkkijonon viimeisestä merkistä tulostetaan rekursiivisesti jokainen merkki, kunnes kaikki merkkijonon merkit on käytetty.
Alla oleva ohjelma käyttää rekursiota kääntäessään annetun merkkijonon.
class String_Reverse { //rekursiivinen menetelmä tietyn merkkijonon kääntämiseen void reverseString(String str) { //perusehto; palaa, jos merkkijono on nolla tai siinä on 1 tai vähemmän merkkejä if ((str==null))} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Annettu merkkijono: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Käänteinen merkkijono: "); obj.reverseString(inputstr); } } } Lähtö
#4) Binäärihaku Java-rekursio
Binäärihakualgoritmi on kuuluisa hakualgoritmi. Tässä algoritmissa etsitään n-alkioisesta lajitellusta joukosta annettu avainalkio. Aluksi jaetaan joukko kahteen osaan etsimällä joukon keskimmäinen alkio.
Sitten riippuen siitä, onko avain puolivälissä, rajoitamme etsintää array:n ensimmäiseen tai toiseen puolikkaaseen. Näin sama prosessi toistetaan, kunnes avainelementtien sijainti on löydetty.
Toteutamme tämän algoritmin rekursiota käyttäen.
import java.util.*; class Binary_Search { // rekursiivinen binäärihaku int binarySearch(int numArray[], int vasen, int oikea, int avain) { if (oikea>= vasen) { //laske matriisin keskikohta int mid = vasen + (oikea - vasen) / 2; // jos avain on keskikohdassa, palauta keskikohta if (numArray[keskikohta] == avain) return mid; // jos avain avain) return binarySearch(numArray, vasen, keskikohta - 1, avain); // // Muuten rekursiivinen haku matriisissa.oikea osajoukko return binarySearch(numArray, mid + 1, right, key); } //joukossa ei ole elementtejä, return -1 return -1; } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //ilmoita ja tulosta joukko int numArray[] = { 4,6,12,16,22}; System.out.println("Annettu joukko : " + Arrays.toString(numArray)); int len = numArray.length; //joukon pituus.int key = 16; // haettava avain int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Elementti " + key + " ei löydy"); else System.out.println("Elementti " + key + " löytyi indeksillä " + result); } } } Lähtö
#5) Etsi vähimmäisarvo Array käyttäen rekursio
Rekursiota käyttämällä voimme myös löytää matriisin pienimmän arvon.
Alla on esitetty Java-ohjelma, jolla etsitään matriisin pienin arvo.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //palauta ensimmäinen elementti, jos vain yksi elementti tai minimi array-elementeistä return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Annettu Array : " + Arrays.toString(numArray))); int n =numArray.length; System.out.print("Joukon pienin elementti: " + getMin(numArray, 0, n) + "\n"); } } } Lähtö
Nämä ovat esimerkkejä rekursiosta. Näiden esimerkkien lisäksi myös monet muut ohjelmistojen ongelmat voidaan toteuttaa rekursiivisilla tekniikoilla.
Rekursiotyypit
Rekursiota on kahdenlaista sen mukaan, milloin rekursiivista metodia kutsutaan.
Ne ovat:
#1) Hännän rekursio
Kun rekursiivisen metodin kutsu on viimeinen lauseke, joka suoritetaan rekursiivisen metodin sisällä, sitä kutsutaan nimellä "Tail Recursion".
Häntärekursiossa rekursiivinen kutsulauseke suoritetaan yleensä yhdessä metodin paluulauseen kanssa.
Seuraavassa on esitetty pyrstörekursion yleinen syntaksi:
methodName ( T parametrit...){ { if (base_condition == true) { return result; } return methodName (T parametrit ...) // tail recursion } #2) Pään rekursio
Päärekursio on mikä tahansa rekursiivinen lähestymistapa, joka ei ole häntärekursio. Jopa yleinen rekursio on siis etukäteisrekursiota.
Päärekursion syntaksi on seuraava:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekursio Vs Iteraatio Javassa
| Rekursio | Iteraatio |
|---|---|
| Rekursio on prosessi, jossa metodi kutsuu itseään toistuvasti, kunnes jokin perusehto täyttyy. | Iterointi on prosessi, jossa koodin osa suoritetaan toistuvasti rajallisen määrän kertoja tai kunnes jokin ehto täyttyy. |
| Onko sovellus toimintoja varten. | Sovelletaan silmukoihin. |
| Toimii hyvin pienemmälle koodikoolle. | Toimii hyvin suuremmalle koodikoolle. |
| Käyttää enemmän muistia, koska jokainen rekursiivinen kutsu työnnetään pinoon. | Muistia käytetään verrattain vähän. |
| Vaikea korjata ja ylläpitää | Helpompi vianmääritys ja ylläpito |
| Tuloksena on pinon ylivuoto, jos perusehtoa ei ole määritetty tai sitä ei ole saavutettu. | Voi suorittaa loputtomasti, mutta lopettaa suorituksen lopulta muistivirheiden yhteydessä. |
| Aika on hyvin monimutkainen. | Ajanmenekki on suhteellisen vähäistä. |
Usein kysytyt kysymykset
Kysymys #1) Miten rekursio toimii Javassa?
Vastaa: Rekursiossa rekursiivinen funktio kutsuu itseään toistuvasti, kunnes perusehto täyttyy. Kutsutun funktion muisti työnnetään pinoon kutsuvan funktion muistin yläosaan. Jokaista funktiokutsua varten tehdään erillinen kopio paikallisista muuttujista.
Q #2) Miksi rekursiota käytetään?
Vastaa: Rekursiota käytetään sellaisten ongelmien ratkaisemiseen, jotka voidaan jakaa pienempiin ongelmiin ja koko ongelma voidaan ilmaista pienemmän ongelman avulla.
Rekursiota käytetään myös ongelmissa, jotka ovat liian monimutkaisia ratkaistaviksi iteratiivisella lähestymistavalla. Käytä rekursiota niiden ongelmien lisäksi, joissa ajan monimutkaisuus ei ole ongelma.
Q #3) Mitä hyötyä rekursiosta on?
Vastaa:
Rekursion etuja ovat muun muassa:
- Rekursio vähentää turhia funktiokutsuja.
- Rekursion avulla voimme ratkaista ongelmia helposti verrattuna iteratiiviseen lähestymistapaan.
Kysymys #4) Kumpi on parempi - rekursio vai toistaminen?
Vastaa: Rekursio tekee toistuvia kutsuja, kunnes perusfunktio on saavutettu. Näin ollen muistia kuluu ylimääräistä muistia, koska jokaisen funktiokutsun muistia työnnetään pinoon.
Toisaalta iterointi ei aiheuta suuria muistin kuluja. Rekursion suorittaminen on hitaampaa kuin iteratiivinen lähestymistapa. Rekursio pienentää koodin kokoa, kun taas iteratiivinen lähestymistapa tekee koodista suuren.
Q #5) Mitkä ovat rekursion edut verrattuna toistoon?
Vastaa:
- Rekursio tekee koodista selkeämpää ja lyhyempää.
- Rekursio on parempi kuin iteratiivinen lähestymistapa esimerkiksi Hanoin tornin ja puiden läpikäymisen kaltaisissa ongelmissa.
- Koska jokainen funktiokutsu lisää muistia pinoon, rekursio käyttää enemmän muistia.
- Rekursion suorituskyky on hitaampi kuin iteratiivisen lähestymistavan.
Päätelmä
Rekursio on erittäin tärkeä käsite ohjelmistoissa ohjelmointikielestä riippumatta. Rekursiota käytetään useimmiten tietorakenteisiin liittyvien ongelmien, kuten Hanoin tornien, puiden ja linkitettyjen listojen jne. ratkaisemiseen. Vaikka rekursio vie enemmän muistia, se tekee koodista yksinkertaisempaa ja selkeämpää.
Olemme käsitelleet rekursiota tässä opetusohjelmassa ja toteuttaneet lukuisia ohjelmointiesimerkkejä käsitteen ymmärtämiseksi paremmin.