Bevezetés a Java rekurzív funkciójába
A rekurzív funkció az, amely egyszer vagy többször felhívja magát. A rekurzív funkciót azokban a helyzetekben használják, amikor ugyanazt a műveletet kell újra és újra elvégezni, amíg az eredmény el nem érkezik. Több iterációt hajt végre, és a problémamegjegyzés minden egyes iterációval egyszerűbbé válik.
A rekurzív funkció írásakor mindig meg kell adni az alapkorlátot, egyébként Stack Overflow hibát eredményez. A verem egy memóriaterület, amely a módszerhívások fenntartására van fenntartva. A hiba azért van, mert a funkció folyamatosan kezd futni, mivel nem fogja megtalálni a korlátozó feltételt, és így végül kimeríti a lefoglalt memóriát. Tehát a verem túlcsordulásának elkerülése érdekében bizonyos alapfeltételeket definiálunk „ha másként” utasítások (vagy bármilyen más feltételes kijelentés) segítségével, amely miatt a rekurziós funkció leáll, mihelyt a szükséges számítás befejeződik.
A rekurzió típusai Java-ban
Kétféle rekurzió létezik a Java-ban. Ők:
1. Közvetlen rekurzió
Szintaxis:
Itt az1 funkció folyamatosan hívja magát, tehát egy rekurzív funkció.
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
)
Példa
A szám tényezője a közvetlen rekurzió példája. A rekurzió alapelve egy komplex probléma megoldása kisebb részekre osztással. Például egy szám faktorszáma esetén kiszámoljuk az „i” tényezőt, ha tudjuk, hogy annak „i-1” tényezője.
Kód:
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));
)
)
Kimenet:
2. Közvetett / kölcsönös rekurzió
Egy1 funkciót, amely egy másik2 funkciót hív, amelyet viszont közvetlenül vagy közvetve az 1. funkció hív, közvetett rekurzív funkciónak nevezzük.
Szintaxis:
Vegyünk két funkciót, melynek neve az function1 () és a function2 (). Itt az function1 hívja a function2 és a function2 hívja az function1-et.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
Példa
Az indirekt rekurzió bemutatására a következő programot vesszük alapul, amelyből kiderül, hogy egy adott szám páros vagy páratlan-e a megadott bemenethez képest.
Kód:
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();
)
)
Kimenet:
Példák a Java rekurzióra
Itt található még néhány példa a problémák megoldására a rekurziós módszerrel.
1. példa - Fibonacci szekvencia
Az „n” szám halmazát Fibonacci sorozatban kell elhelyezni, ha szám 3 = szám 1 + szám 2, azaz minden szám az előző két szám összegét jelenti. Ennélfogva a sorozat mindig az első két számjegygel kezdődik, mint például 0 és 1. A harmadik szám 0 és 1 összege, ami 1-et eredményez, a negyedik szám 1 és 1 összeadását eredményezi, ami 2-t eredményez, és a sorozat folytatódik.
Nézze meg a következő kódot a Java-ban, hogy Fibonacci-szekvenciát hozzon létre:
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
)
)
Kimenet:
Itt az első két szám 0-ra és 1-re inicializálódik és kinyomtatásra kerül. A „num1”, „num2” és „num3” változókat kell használni a kívánt sorozat előállításához. A „num3” változót a „num1” és „num2” hozzáadásával kapjuk meg, és a számokat az egyik helyzettel balra toljuk el, a kód szerint ábrázolva. A „Fibonacci” függvényt rekurzívan hívjuk ide, és minden iterációnál az „n” értékét 1-rel csökkentjük. Ezért a rekurzió akkor lép ki, amikor az „n” eléri a 0 értéket.
2. példa - Hanoi tornya
Ez egy klasszikus matematikai probléma, amelynek 3 pólusa és “n” száma különböző méretű lemezeket tartalmaz. A puzzle a következőképpen alakul:
Az elején az első pólus úgy van elrendezve, hogy a tárcsák oly módon vannak elrendezve, hogy mindegyik legnagyobb tárcsa az alján, a legkisebb pedig a pólus tetején legyen. A cél az, hogy ezeket a lemezeket az első pólusról a harmadik pólusra mozgatják, miközben a lemezeket az első helyzettel azonos helyzetben tartják. Az alábbiakban felsorolunk néhány feltételt, amelyet szem előtt kell tartanunk, miközben ezeket a lemezeket eltoljuk:
1. Egy időben csak egy lemezt kell mozgatni.
2. A folyamat során nem szabad nagyobb lemezt helyezni egy kisebbre.
3. A második (középső) pólus mediálható, miközben a lemezeket áthelyezik az elsőről a második pólusra.
Az alábbiakban látható a Java kód, amely felhasználható a puzzle megoldására:
Kód:
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);
)
)
)
Kimenet:
Itt a „count” változó jelöli a használni kívánt lemezek számát. A „torony” funkció a rekurzív funkció, amellyel a lemezeket az 1. rúdról a 3. rúdra mozgathatják. Erre a problémára egyszerű megoldást kínálhat, ha először 2 lemezt vesz figyelembe.
- Először azzal kezdjük, hogy az 1. tárcsát a 2. rúdra mozgatjuk.
- Ezután a disc2-t mozgatjuk a 3. rúdra.
- Végül befejezzük a Disc1 mozgatásával a 3. rúdra, a kívánt megoldás befejezéséhez.
Ugyanezt az elvet kell alkalmazni az „n” számú tárcsára is, ha a tárcsát (n-1) az 1-es rúdról 2-re mozgatják, és a fenti lépésekkel járnak.
A rekurzió előnyei a Java-ban
- A kód könnyen írható és karbantartható.
- A legjobb módszer az eredmények megtalálására, ahol nagyszámú iterációra van szükség.
A rekurzió hátrányai a Java-ban
- A rekurzív funkciók több memóriát igényelnek. Ennek oka az, hogy minden alkalommal rekurzív függvényt hívnak; a memória allokációja újonnan történik a verem változóinál. És a megfelelő memóriakiosztás felszabadul, mihelyt a változó értékeket visszatérítik.
- Ez a memóriaelosztási folyamat több időt vesz igénybe, ezért a végrehajtás általában lassú.
Következtetés
A rekurzív funkciók viszonylag egyszerűbben kódolhatók, de a többi létező módszerhez képest nem is annyira hatékonyak. Ezért főként azokban az esetekben alkalmazzák, amikor kevesebb a fejlesztési idő és a probléma jelentős mintája megfigyelhető.
Ajánlott cikkek
Ez egy útmutató a Java rekurzióhoz. Itt tárgyaljuk a Java rekurzió típusait, annak különféle példáit, valamint előnyeit és hátrányait. A következő cikkeket is megnézheti további információkért -
- JScrollPane Java-ban
- Matematikai funkciók a Java-ban
- Matematikai funkciók a Java-ban
- Kivitelező Java-ban
- Rekurzív funkció a Pythonban
- Faktorialis program a JavaScript-ben