Java - Rekuzija


U Javi je metoda koja sama sebe poziva, poznata kao rekurzivna metoda. Ovaj proces je poznat kao rekurzija. Primjer fizičkog svijeta bio bi postavljanje dva paralelna ogledala okrenuta jedno prema drugom. Bilo koji objekt između njih reflektovao bi se rekurzivno.



Kako rekurzija radi?


Rad Java rekurzije



U gornjem primjeru pozvali smo metod recurse() unutar glavne metode (poziv normalne metode) i, unutar recurse() metode, ponovo pozivamo istu rekurznu metodu. Ovo je rekurzivni poziv. Da bismo zaustavili rekurzivni poziv, moramo osigurati neke uslove unutar metode. U suprotnom, metoda će se pozivati beskonačno.

Zbog toga koristimo naredbu if...else (ili sličan pristup) za završavanje rekurzivnog poziva unutar metode.


Primjer: Faktorijal broja koji koristi rekurziju

class Factorial {

    static int factorial( int n ) {
        if (n != 0)  // uslov raskida
            return n * factorial(n-1); // rekurzivni poziv
        else
            return 1;
    }

    public static void main(String[] args) {
        int number = 4, result;
        result = factorial(number);
        System.out.println(number + " factorial = " + result);
    }
}

U gornjem primjeru imamo metodu koja se zove factorial(). Metoda factorial() se poziva iz metode main() s varijablom broja koja se prosljeđuje kao argument. Ovdje, primijetite izjavu:

return n * factorial(n-1);

Metoda factorial() sama sebe poziva. U početku je vrijednost n unutar metode factorial(). Tokom sljedećeg rekurzivnog poziva, 3 se prenosi na metodu factorial(). Ovaj proces se nastavlja sve dok n nije jednako 0. Kada je n jednako 0, naredba if vraća false, zbog toga se vraća 1. Konačno, akumulirani rezultat se prenosi na metodu main().



Rad faktorskog (factoriel) programa

Slika ispod će vam dati bolju ideju o tome kako se faktorski program izvršava pomoću rekurzije.


Faktorski program koji koristi rekurziju



Prednosti i nedostaci rekurzije

Kada se izvrši rekurzivni poziv onda se dodjeljuju nova mjesta za pohranu varijabli. Kako se svaki rekurzivni poziv vraća, parametri stare varijable i se uklanjaju iz steka. Zbog toga rekurzija obično koristi više memorije i uglavnom je spora. S druge strane, rekurzivno rješenje je mnogo jednostavnije i treba manje vremena za pisanje, uklanjanje grešaka i održavanje.