Hallo,
ist (in Java) Rekursion immer etwas ineffizienter als das iterative Äquivalent?
Ich wollte ein wenig das “Funktionale Denken” üben und auf Schleifen weitgehend verzichten.
Zum Beispiel bei der Überprüfung ob eine Zahl prim ist
Iterativ:
public static boolean isPrime_iter(long number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (long i = 3; (i * i) <= number; i += 2)
if (number % i == 0) return false;
return true;
}
Rekursiv:
public static boolean isPrime_rec(long number, long... args) {
long i = (args != null && args.length >= 1) ? args[0] : 3;
return (number < 2) ? false
: (number == 2) ? true
: (number % 2 == 0) ? false
: ((i * i) > number) ? true
: (number % i == 0) ? false
: isPrime_rec(number, i + 2);
}
Ich habe dann mal gemessen, wie lange die beiden Methoden brauchen, um alle Zahlen zwischen 1 und 1.000.000 zu überprüfen:
public class PrimeTest {
public static void main(String[] args) {
final int testNumber = 1_000_000;
long start1 = System.currentTimeMillis();
int counter1 = 0;
for (int i = 1; i <= testNumber; ++i) {
if (isPrime_iter(i)) {
++counter1;
}
}
long diff1 = System.currentTimeMillis() - start1;
long start2 = System.currentTimeMillis();
int counter2 = 0;
for (int i = 1; i <= testNumber; ++i) {
if (isPrime_rec(i)) {
++counter2;
}
}
long diff2 = System.currentTimeMillis() - start2;
if (counter1 == counter2) {
System.out.println("Iterativ: " + diff1 + "ms");
System.out.println("Rekursiv: " + diff2 + "ms");
System.out.println("Differenz I-R: " + (diff2 - diff1) + "ms");
}
}
}
Heraus kam, dass die rekursive Methode 144ms langsamer ist. Ich dachte vielleicht läge es daran, dass ich mit Varargs versucht hatte, default arguments zu simulieren, also habe ich eine zweite rekursive Version geschrieben:
public static boolean isPrime_rec2(long number, long i) {
return (number < 2) ? false
: (number == 2) ? true
: (number % 2 == 0) ? false
: ((i * i) > number) ? true
: (number % i == 0) ? false
: isPrime_rec(number, i + 2);
}
Sie war beim Durchlauf 17ms schneller als die erste rekursive Vesion aber immer noch 127ms langsamer als die iterative Variante.
Woran liegt das? Sind meine rekursiven Methoden einfach nur schlecht implementiert, oder sind Methodenaufrufe grundsätzlich langsam?