See põhjalik õpetus rekursiooni kohta Javas selgitab, mis on rekursioon koos näidete, tüüpide ja seotud mõistetega. Samuti hõlmab see rekursiooni vs. Iteratsioon:
Varasematest Java-õpetustest oleme näinud iteratiivset lähenemist, kus me deklareerime tsükli ja seejärel läbime andmestruktuuri iteratiivselt, võttes ühe elemendi korraga.
Oleme näinud ka tingimuslikku voolu, kus me jälle hoiame ühte tsükli muutujat ja kordame koodi, kuni tsükli muutuja vastab tingimusele. Kui tegemist on funktsioonikõnedega, siis uurisime iteratiivset lähenemist ka funktsioonikõnedele.
Selles õpetuses arutame teistsugust lähenemist programmeerimisele, st rekursiivset lähenemist.
Mis on rekursioon Java's?
Rekursioon on protsess, mille käigus funktsioon või meetod kutsub ennast uuesti ja uuesti. Seda funktsiooni, mida kutsutakse uuesti ja uuesti kas otseselt või kaudselt, nimetatakse "rekursiivseks funktsiooniks".
Näeme erinevaid näiteid rekursiooni mõistmiseks. Nüüd vaatame rekursiooni süntaksit.
Rekursiooni süntaks
Igal meetodil, mis rakendab rekursiooni, on kaks põhilist osa:
- Meetodikõne, mis võib kutsuda iseennast, st rekursiivne.
- Eeltingimus, mis peatab rekursiooni.
Pange tähele, et eeltingimus on vajalik iga rekursiivse meetodi jaoks, sest kui me ei katkesta rekursiooni, siis jätkub see lõpmatult ja põhjustab virna ülevoolu.
Rekursiooni üldine süntaks on järgmine:
methodName (T parameters...) { if (precondition == true) //eeltingimus või põhitingimus { return result; } return methodName (T parameters...); //rekursivne üleskutse } Pange tähele, et eeltingimust nimetatakse ka baastingimuseks. Baastingimusest räägime lähemalt järgmises jaotises.
Rekursiooni mõistmine Java's
Selles jaotises püüame mõista rekursiooni protsessi ja näha, kuidas see toimub. Saame teada põhitingimusest, virna ülevoolust ja näeme, kuidas konkreetset probleemi saab rekursiooni abil lahendada ja muid taolisi üksikasju.
Rekursiooni põhitingimus
Rekursiivse programmi kirjutamisel peaksime kõigepealt andma lahenduse baasjuhtumi jaoks. Seejärel väljendame suuremat probleemi väiksemate probleemide kaudu.
Nagu näide, võime võtta klassikalise ülesande arvude faktoriaalarvu arvutamiseks. Antud arvu n korral peame leidma n-i faktoriaalarvu, mida tähistatakse n!
Rakendame nüüd programmi, et arvutada n faktoriaali (n!), kasutades rekursiooni.
public class Main{ static int fact(int n) { if (n == 1) // põhitingimus return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Väljund
Selles programmis näeme, et tingimus (n<=1) on baastingimus ja kui see tingimus saavutatakse, siis funktsioon tagastab 1. Funktsiooni else osa on rekursiivne üleskutse. Kuid iga kord, kui rekursiivset meetodit kutsutakse, väheneb n 1 võrra.
Seega võime järeldada, et lõpuks saab n väärtus 1 või väiksem kui 1 ja sel hetkel tagastab meetod väärtuse 1. See baastingimus saavutatakse ja funktsioon lõpetatakse. Pange tähele, et n väärtus võib olla mis tahes, kui see vastab baastingimusele.
Probleemi lahendamine rekursiooni abil
Rekursiooni kasutamise põhiidee on väljendada suuremat probleemi väiksemate probleemidena. Samuti peame lisama ühe või mitu baastingimust, et saaksime rekursioonist välja tulla.
Seda demonstreerisime juba ülaltoodud faktoriaali näites. Selles programmis väljendasime n faktoriaali (n!) väiksemate väärtustega ja meil oli baastingimus (n <=1), nii et kui n jõuab 1, saame rekursiivsest meetodist loobuda.
Stack Overflow viga rekursioonis
Me teame, et kui kutsutakse ükskõik millist meetodit või funktsiooni, salvestatakse funktsiooni olek korstnasse ja see võetakse tagasi, kui funktsioon naaseb. Korstnat kasutatakse ka rekursiivse meetodi puhul.
Kuid rekursiooni puhul võib tekkida probleem, kui me ei määratle baastingimust või kui baastingimus jääb kuidagi saavutamata või täitmata. Kui selline olukord tekib, siis võib tekkida virna ülevool.
Vaatleme alljärgnevat näidet faktoriaalse märkimise kohta.
Siin on esitatud vale baastingimus, n==100.
public class Main { static int fact(int n) { if (n == 100) // põhitingimus, mis põhjustab virna ülevoolu return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Nii et kui n> 100 meetod tagastab 1, kuid rekursioon ei peatu. n väärtus väheneb lõpmatult, kuna ei ole mingit muud tingimust, et seda peatada. See jätkub kuni virna ülevoolamiseni.
Teine juhtum on siis, kui väärtus n <100. Ka sel juhul ei täida meetod kunagi baastingimust ja tulemuseks on virna ülevool.
Rekursiooni näited Java's
Selles jaotises rakendame järgmised näited, kasutades rekursiooni.
#1) Fibonacci seeria kasutamine rekursiooni abil
Fibonacci jada on antud järgmiselt,
1,1,2,3,5,8,13,21,34,55,…
Ülaltoodud jada näitab, et praegune element on kahe eelmise elemendi summa. Samuti on Fibonacci jada esimene element 1.
Seega üldiselt, kui n on praegune arv, siis on see antud (n-1) ja (n-2) summaga. Kuna praegune element on väljendatud eelmiste elementide kaudu, saame seda probleemi väljendada rekursiooni abil.
Fibonacci seeria rakendamise programm on esitatud allpool:
public class Main { //meetod fibonacci-seeria arvutamiseks 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; //trükkida fibonacci-seeria esimesed 10 arvu System.out.println ("Fibonacci-seeria: esimesed 10 arvu:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Väljund
#2) Kontrollida, kas arv on palindroom, kasutades rekursiooni
Palindroom on jada, mis on võrdne, kui seda lugeda vasakult paremale või paremalt vasakule.
Antud numbri 121 puhul näeme, et kui lugeda seda vasakult paremale ja paremalt vasakule, on see võrdne. Seega on number 121 palindroom.
Võtame teise numbri, 1242. Kui me loeme seda vasakult paremale, siis on see 1242 ja kui lugeda paremalt vasakule, siis 2421. Seega ei ole see palindroom.
Rakendame palindroomi programmi, pöörates numbrite numbreid ümber ja võrdleme rekursiivselt antud arvu selle ümberpööratud esitusega.
Allpool olev programm rakendab programmi palindroomi kontrollimiseks.
import java.io.*; import java.util.*; public class Main { // kontrollime, kas num sisaldab ainult ühte numbrit 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 { // baastingimus; return if num=0 if (num == 0) { return revNum; } else { //callutiliitfunktsioon rekursiivselt revNum = isPalindrome_util(num / 10, revNum); } // Kontrollida, kas num ja revNum esimene number on võrdne if (num % 10 == revNum % 10) { // kui jah, siis revNum liigub koos num'iga return revNum / 10; } else { // exit throw new Exception(); } } // meetod, et kontrollida, kas antud arv on palindroom, kasutades palindroomi utiliitfunktsiooni 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("Jah, antud arv " + n + " on palindroom."); } catch (Exception e) { System.out.println("Ei, antud arv " + n + " ei ole palindroom."); } n = 1221; try { isPalindrome(n);System.out.println("Jah, antud arv " + n + " on palindroom."); } catch (Exception e) { System.out.println("Ei, antud arv " + n + " ei ole palindroom."); } } } } Väljund
#3) Tagasipööratud stringi rekursioon Java
Andes stringi "Hello", peame selle ümberpöörama, nii et tulemuseks oleks string "olleH".
Seda tehakse rekursiooni abil. Alustades stringi viimasest tähemärgist, trükime rekursiivselt iga tähemärki, kuni kõik stringis olevad tähemärgid on ammendunud.
Alljärgnev programm kasutab rekursiooni antud stringi ümberpööramiseks.
class String_Reverse { //rekursiivne meetod antud stringi tagasipööramiseks void reverseString(String str) { //põhitingimus; tagastatakse, kui string on null või sisaldab 1 või vähem tähemärki if ((str==null)} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Antud string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } } Väljund
#4) Binaarne otsing Java rekursioon
Binaarne otsingualgoritm on tuntud otsingu algoritm. Selles algoritmis otsime antud n elemendist koosneva sorteeritud massiivi antud võtmeelementi. Alguses jagame massiivi kaheks pooleks, leides massiivi keskmise elemendi.
Seejärel sõltuvalt sellest, kas võtme keskel piirame oma otsingut massiivi esimeses või teises pooles. Nii korratakse sama protsessi, kuni võtmeelementide asukoht on leitud.
Rakendame selle algoritmi siin rekursiooni abil.
import java.util.*; class Binary_Search { // rekursiivne binaarne otsing int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { // arvutame massiivi keskkoha int mid = left + (right - left) / 2; // kui võti on keskkohas, tagastame keskkoha if (numArray[mid] == key) return mid; // kui võti key) return binarySearch(numArray, left, mid - 1, key); // muidu otsime rekursiivselt massiivisparempoolne alamassiivi return binarySearch(numArray, mid + 1, right, key); } //massiivi elemendid puuduvad, tagastame -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //deklareerime ja trükime massiivi int numArray[] = { 4,6,12,16,22}; System.out.println("Antud massiivi : " + Arrays.toString(numArray)); int len = numArray.length; //massiivi pikkusint key = 16; //otsitav võti 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); } } } Väljund
#5) Leia minimaalne väärtus massiivi kasutades rekursiooni
Kasutades rekursiooni saame leida ka minimaalse väärtuse massiivi.
Allpool on esitatud Java-programm massiivi minimaalse väärtuse leidmiseks.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //tagasi esimene element, kui ainult üks element või minimaalne massiivi elementidest 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("Antud massiivi : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Minimaalne element massiivi: " + getMin(numArray, 0, n) + "\n"); } } } Väljund
Need on mõned näited rekursiooni kohta. Peale nende näidete saab rekursiivsete tehnikate abil rakendada ka paljusid teisi tarkvaraprobleeme.
Rekursioonitüübid
Rekursioon on kahte tüüpi, sõltuvalt sellest, millal rekursiivset meetodit kutsutakse.
Need on järgmised:
#1) Tagasipöördumine
Kui rekursiivse meetodi üleskutse on viimane rekursiivse meetodi sees täidetav käsk, nimetatakse seda "Tail Recursion".
Saba rekursiooni korral täidetakse rekursiivne kutsung tavaliselt koos meetodi tagastusavaldusega.
Järgnevalt on esitatud sabarekursiooni üldine süntaks:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail recursion } #2) Pea rekursioon
Pearekursioon on igasugune rekursiivne lähenemine, mis ei ole sabarekursioon. Nii et isegi üldine rekursioon on ees rekursioon.
Pea rekursiooni süntaks on järgmine:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekursioon vs. Iteratsioon Java's
| Rekursioon | Iteratsioon |
|---|---|
| Rekursioon on protsess, mille käigus meetod kutsub ennast korduvalt, kuni mingi põhitingimus on täidetud. | Iteratsioon on protsess, mille käigus kooditükki täidetakse korduvalt piiratud arv kordi või kuni mingi tingimuse täitmiseni. |
| Kas rakendus on funktsioonide jaoks. | Kohaldatakse silmuste puhul. |
| Töötab hästi väiksema koodimahu puhul. | Töötab hästi suurema koodimahu puhul. |
| Kasutab rohkem mälu, kuna iga rekursiivne kõne lükatakse virna. | Kasutatakse suhteliselt vähem mälu. |
| Raske tõrjuda ja hooldada | Lihtsam tõrjuda ja hooldada |
| Tulemuseks on virna ülevool, kui baastingimust ei ole määratud või seda ei ole saavutatud. | Võib teostada lõpmatult, kuid lõpetab lõpuks täitmise mis tahes mäluvigade korral. |
| Ajakomplekssus on väga suur. | Ajakomplekssus on suhteliselt madalamal tasemel. |
Korduma kippuvad küsimused
K #1) Kuidas töötab rekursioon Javas?
Vastus: Rekursioonis kutsub rekursiivne funktsioon ennast korduvalt, kuni baastingimus on täidetud. Kutsutud funktsiooni mälu lükatakse korstnasse kutsuva funktsiooni mälu tippu. Iga funktsioonikõne puhul tehakse eraldi koopia lokaalsetest muutujatest.
Q #2) Miks kasutatakse rekursiooni?
Vastus: Rekursiooni kasutatakse nende probleemide lahendamiseks, mida saab jaotada väiksemateks ja kogu probleemi saab väljendada väiksema probleemi kaudu.
Rekursiooni kasutatakse ka nende probleemide puhul, mis on liiga keerulised, et neid saaks lahendada iteratiivse meetodi abil. Lisaks probleemidele, mille puhul ajakomplekssus ei ole probleemiks, kasutage rekursiooni.
Q #3) Millised on rekursiooni eelised?
Vastus:
Rekursiooni eelised on järgmised:
- Rekursioon vähendab funktsioonide üleliigset kutsumist.
- Rekursioon võimaldab meil probleeme hõlpsasti lahendada, võrreldes iteratiivse lähenemisega.
K #4) Kumb on parem - rekursioon või iteratsioon?
Vastus: Rekursioon teeb korduvaid kutsungeid, kuni baasfunktsioonini jõutakse. Seega tekib mälukulu, kuna iga funktsioonikõne jaoks lükatakse mälu virna.
Iteratsioonil seevastu ei ole palju mälu koormust. Rekursiooni täitmine on aeglasem kui iteratiivne lähenemine. Rekursioon vähendab koodi suurust, samas kui iteratiivne lähenemine muudab koodi suureks.
Q #5) Millised on rekursiooni eelised Iteratsiooni ees?
Vastus:
- Rekursioon muudab koodi selgemaks ja lühemaks.
- Rekursioon on parem kui iteratiivne lähenemine selliste probleemide puhul nagu Hanoi torn, puu läbimine jne.
- Kuna iga funktsioonikõne puhul lükatakse mälu virna, kasutab rekursioon rohkem mälu.
- Rekursiooni jõudlus on aeglasem kui iteratiivse lähenemise puhul.
Kokkuvõte
Rekursioon on tarkvaras väga oluline mõiste, olenemata programmeerimiskeelest. Rekursiooni kasutatakse enamasti andmestruktuuride probleemide lahendamisel, nagu Hanoi tornid, puu läbimine, seotud loendid jne. Kuigi see võtab rohkem mälu, muudab rekursioon koodi lihtsamaks ja selgemaks.
Selles õpetuses oleme uurinud kõike rekursioonist. Samuti oleme rakendanud mitmeid programmeerimisnäiteid, et mõistet paremini mõista.