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?




U gornjem primjeru pozvali smo metod recursiveMethod() unutar glavne metode (poziv normalne metode) i unutar recursiveMethod() 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

Pogledajmo nekoliko primjera kako biste razumjeli upotrebu faktoriela u Javi.


Primjer 1: Fibonačijeva serija (Fibonacci Series):

public class RecursionExample {  
    static int n1=0,n2=1,n3=0;      
     static void printFibo(int count){      
        if(count>0){      
             n3 = n1 + n2;      
             n1 = n2;      
             n2 = n3;      
             System.out.print(" "+n3);     
             printFibo(count-1);      
         }      
     }        
  
public static void main(String[] args) {  
    int count=15;      
      System.out.print(n1+" "+n2);// Ispisuje 0 i 1      
      printFibo(count-2);// n-2 zato što je broj 2 već ispisan
}  
}  

Primjer 2: Pomoću rekurzije dodajemo sve brojeve do 10.

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Primjer 3: Pomoću rekurzije dodajemo sve brojeve između 5 i 10.

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}