Johdatus Java-ohjelman rekursiiviseen toimintaan
Rekursiivinen toiminto on se, joka kutsuu itseään yhden tai useamman kerran. Rekursiivista toimintoa käytetään tilanteissa, joissa sama toimenpide täytyy suorittaa uudestaan ja uudestaan, kunnes tulos on saavutettu. Se suorittaa useita iteraatioita ja ongelmalausunto muuttuu yksinkertaisemmaksi jokaisen iteraation kanssa.
Aina perusraja on määritettävä kirjoitettaessa rekursiivista toimintoa. Muutoin seurauksena on pino ylivuodon virhe. Pino on muistialue, joka on varattu menetelmäkutsujen ylläpitämiseen. Virhe johtuu siitä, että toiminto alkaa jatkuvasti suorittaa toimintoa, koska se ei löydä rajoittavaa ehtoa ja tyhjentää siten varatun muistin lopulta. Joten estääksemme pinojen ylivuodon, määrittelemme tietyt perusedellytykset lauseiden (jos… muu) avulla (tai minkä tahansa muun ehdollisen lausekkeen) avulla, mikä saa rekursiotoiminnon lopettamaan heti, kun vaadittu laskenta on valmis.
Rekursiotyypit Java-ohjelmissa
Java-ohjelmassa on 2 tyyppisiä rekursioita. He ovat:
1. Suora rekursio
Syntaksi:
Tässä funktio1 kutsuu itseään jatkuvasti, joten se on rekursiivinen funktio.
public static void main(String() args)(
//few lines of code
function();
//few lines of code
)
function() (
//few lines of code
function();
//few lines of code
)
esimerkki
Luvun tekijä on esimerkki suorasta rekursiosta. Rekursion perusperiaatteena on ratkaista monimutkainen ongelma jakamalla pienempiin. Esimerkiksi, jos kyseessä on luvun tekijä, lasketaan ”i”: n tekijä, jos tiedämme sen ”i-1”.
Koodi:
public class Factorial (
static int fact(int i)(
if (i == 1)
return 1;
else
return(i * fact(i-1));
)
public static void main(String() args) (
System.out.println("The factorial of given number 6 is: "+fact(6));
)
)
lähtö:
2. Epäsuora / keskinäinen rekursio
Toimintoa 1, joka kutsuu toista funktiota2, jota puolestaan kutsutaan toimintoksi 1 joko suoraan tai epäsuorasti, kutsutaan epäsuoraksi rekursiiviseksi funktioksi.
Syntaksi:
Mieti 2 funktiota nimeltään function1 () ja function2 (). Täällä funktio1 kutsuu toimintoa2 ja toimintoa2 kutsuu toimintoa1.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
esimerkki
Epäsuoran rekursion osoittamiseksi otamme seuraavan ohjelman, jolla selvitetään, onko annettu luku parillinen vai pariton annetusta syötöstä.
Koodi:
import java.util.Scanner;
public class IndirectRecursion (
public static boolean oddNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return false;
) else (
return evenNum(i-1);
)
)
public static boolean evenNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return true;
) else (
return oddNum(i-1);
)
)
public static void main(String() args) (
Scanner inputNum = new Scanner(System.in);
System.out.print("Give a number: ");
int n = inputNum.nextInt();
if (evenNum(n)) System.out.println(n + " is even");
else System.out.println(n + " is odd");
inputNum.close();
)
)
lähtö:
Esimerkkejä Java-rekursioista
Tässä on muutama esimerkki ongelmien ratkaisemiseksi rekursiomenetelmällä.
Esimerkki 1 - Fibonacci-sekvenssi
Joukon "n" numeroiden sanotaan olevan Fibonacci-sekvenssissä, jos numero3 = numero1 + numero2, eli jokainen luku on sen kahden edellisen numeron summa. Siksi sekvenssi alkaa aina kahdesta ensimmäisestä numerosta, kuten 0 ja 1. Kolmas luku on 0 ja 1 summa, joka johtaa 1: een, neljäs luku on 1 ja 1 lisäys, mikä johtaa 2: een, jakso jatkuu.
Tutustu seuraavaan Java-koodiin luodaksesi Fibonacci-sekvenssin:
public class FibonacciSeries(
static int num1=0, num2=1, num3=0;
static void fibonacci(int n)(
if(n>0)(
num3 = num1 + num2;
num1 = num2;
num2 = num3;
System.out.print(" "+num3);
fibonacci(n-1);
)
)
public static void main(String args())(
int n=10;
System.out.print(num1+" "+num2);//printing constant first two digits 0 and 1
fibonacci(n-2);//Since first two numbers are already done
)
)
lähtö:
Tässä kaksi ensimmäistä numeroa alustetaan arvoiksi 0 ja 1 ja tulostetaan. Muuttujia “num1”, “num2” ja “num3” käytetään tarvittavan sekvenssin luomiseen. Muuttuja “num3” saadaan lisäämällä “num1” ja “num2”, ja numeroita siirretään yksi sijainti vasemmalle sekoittamalla koodin osoittamalla tavalla. Toimintoa "Fibonacci" kutsutaan tässä rekursiivisesti ja jokaisessa iteraatiossa arvon "n" arvo pienenee yhdellä. Siksi rekursio poistuu heti, kun "n" saavuttaa arvon 0.
Esimerkki 2 - Hanoin torni
Tämä on klassinen matemaattinen tehtävä, jolla on 3 napaa ja “n” lukumäärä erikokoisia levyjä. Palapeli menee seuraavasti:
Alussa ensimmäisessä navassa on kiekot järjestetty siten, että suurin levy kaikista on navan alaosassa ja pienin navan yläosassa. Tavoitteena on siirtää nämä levyt ensimmäisestä navasta kolmanteen napaan pitämällä levyt samassa asennossa kuin ensimmäinen. Seuraavassa on muutamia ehtoja, jotka tulee pitää mielessä siirtäessäsi näitä levyjä:
1. Kerrallaan vain yksi levy on siirrettävä.
2. Prosessissa suuremman levyn sijoittaminen pienemmän päälle ei ole sallittua.
3. Toista (keskimmäistä) napaa voidaan käyttää välittäjänä siirtäessäsi levyjä ensimmäisestä toiseen napaan.
Seuraava on Java-koodi, jota voidaan käyttää palapelin ratkaisemiseen:
Koodi:
public class TowerOfHanoi (
public static void main(String() args) (
int count = 3;
tower(count, 'A', 'B', 'C');
)
public static void tower(int first, char disk1, char temp, char disk2) (
if (first == 1) (
System.out.println("Disk 1 from " + disk1 + " to " + disk2);
) else (
tower(first - 1, disk1, disk2, temp);
System.out.println("Disk " + first + " from " + disk1 + " to " + disk2);
tower(first - 1, temp, disk1, disk2);
)
)
)
lähtö:
Tässä muuttuja “count” edustaa käytettävien levyjen lukumäärää. Toiminto “torni” on rekursiivinen toiminto, jota käytetään levyjen siirtämiseen sauvasta 1 tankoon 3. Yksinkertainen ratkaisu tähän ongelmaan voidaan tarjota harkitsemalla ensin 2 levyä.
- Ensinnäkin, aloitamme siirtämällä kiekkoa 1 sauvosta 1 tankoon 2.
- Seuraavaksi siirrämme disc2 tankoon 3.
- Lopuksi viimeistelemme siirtämällä disc1 tankoon 3 valmistamalla tarvittava ratkaisu.
Tätä samaa periaatetta sovelletaan n-lukumäärään levyjä siirtämällä (n-1) kiekkoa sauvasta 1 2 ja noudattamalla samanlaisia vaiheita kuin yllä.
Rekursion edut Java-ohjelmassa
- Koodia on helppo kirjoittaa ja ylläpitää.
- Paras tapa löytää tuloksia, joissa vaaditaan suuri määrä iteraatioita.
Rekursion haitat Java-ohjelmassa
- Rekursiiviset toiminnot käyttävät enemmän muistia. Tämä johtuu siitä, että joka kerta kutsutaan rekursiivista funktiota; muistin varaus tehdään äskettäin pinon muuttujille. Ja vastaava muistivaraus vapautetaan heti, kun muuttujan arvot palautetaan.
- Tämä muistin allokointiprosessi vie enemmän aikaa, joten suoritus on yleensä hidasta.
johtopäätös
Rekursiiviset toiminnot ovat suhteellisen yksinkertaisia koodata, mutta ne eivät myöskään ole yhtä tehokkaita verrattuna muihin olemassa oleviin menetelmiin. Siksi niitä käytetään pääasiassa tapauksissa, joissa kehitykselle annetaan vähemmän aikaa ja myös jos ongelmassa voidaan havaita merkittävä kuvio.
Suositellut artikkelit
Tämä on opas Rekursioon Java-ohjelmassa. Tässä keskustellaan Java-ohjelman rekursiotyypeistä yhdessä sen erilaisten esimerkien kanssa sekä edut että haitat. Voit myös katsoa seuraavia artikkeleita saadaksesi lisätietoja-
- JScrollPane Java
- Matematiikan toiminnot Java-ohjelmassa
- Matematiikan toiminnot Java-ohjelmassa
- Rakentaja Java
- Rekursiivinen toiminto Pythonissa
- Factorial Program in JavaScript