Gyakorlati alapok II.
Rekurzió
Faktoriális
Az előző, bevezető fejezetben ismertettük a rekurzió működési elvét és fajtáit, illetve az Ami az X-faktorban soha nem lesz: faktoriális című fejezetben magát a faktoriális-számítást, ezért Uroboros-kígyósan fogalmazva csússzunk is bele rögtön további példákba!
Ismétlésképpen: a rekurzió szemléltetésére leggyakrabban a faktoriális számítást veszik elő, így mi sem teszünk másképpen. A faktoriális számítás matematikailag nézve a következő:
5! = 120, ahol 5! = 1 x 2 x 3 x 4 x 5.
Legegyszerűbb a számítást for ciklussal elvégeznünk:
public class Main {
public static void main(String[] args) {
int eredmeny = 1;
int bemenetiAdat = 5;
for(int i = 1; i <= bemenetiAdat; i++){
eredmeny *= i;
}
System.out.println(eredmeny);
}
}
Végeredmény:
120
Nézzük meg külön függvényes megoldásban, amely során a számítást egy külön, faktorialis nevű függvénybe tesszük:
public class Main {
static int faktorialis(int bemenetiAdat){
int eredmeny = 1;
for(int i = 1; i <= bemenetiAdat; i++){
eredmeny *= i;
}
return eredmeny;
}
public static void main(String[] args) {
System.out.println(faktorialis(5));
}
}
Végeredmény:
120
Most nézzük meg a külön függvényes megoldást rekurzióval. Észrevehetjük, hogy faktorialis nevű függvényben mindig önmagát hívjuk meg, még pedig bemenetiAdat-szorosan (return bemenetiAdat * faktorialis(bemenetiAdat-1);).
public class Main {
static int faktorialis (int bemenetiAdat){
if (bemenetiAdat < 1){
return 1;
}
return bemenetiAdat *
faktorialis(bemenetiAdat-1);
}
public static void main(String[] args) {
System.out.println(faktorialis(5));
}
}
Végeredmény:
120
A valós függvényhívások a rekurzió miatt a következők:
faktorialis(5)
faktorialis(4)
faktorialis(3)
faktorialis(2)
faktorialis(1)
faktorialis(0)
return 1
return 2 * 1 = 2
return 3 * 2
= 6
return 4 * 6 = 24
return 5 * 24 = 120
A rekurzió tehát nagyon praktikus, ezért igen elterjedt, bár első pillantásra nehezen érthető megoldás. A fentiekből jól látható, hogy rekurzió és ciklus (iteráció) legtöbbször gond nélkül egymásba alakíthatók. Bizonyos adatszerkezeteknél, ilyen például a faszerkezet (tree structure), a rekurzív keresés, illetve bejárás programozás-technikailag előnyösebb eljárás. Ilyen szerkezet hierarchikus elrendezésű és mindannyian találkoztunk már vele, ha például Windows-könyvtárszerkezetben kattintgattunk:
Pénzes László