Ist Rekursion in Java immer ineffizienter als Iteration?


#1

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?


#2

Also bei Rekursion wird das Stapeln der jeweiligen Rücksprungadresse und ein Sprung benötigt, während bei der Iteration nur eine Endbedingung für das Verlassen der Schleife und ein Branch benötigt wird. Von daher kann die Iteration schon etwas schneller sein. Aber ich würde deinem “Benchmark” mal ein Warmup gönnen oder die Vergleiche öfters nacheinander ausführen, um sicherzustellen, dass der JIT auch das Meiste optimiert hat, wodurch sich Laufzeiten auch gerne mal verringern.


#3

Jo, ist immer langsamer als iterativ. Methodenaufrufe fressen nun mal Zeit! Und das habn auch schon die macher von Java gesagt.

Und es sind, leider muss ich das sagen, nicht nur Rücksprungadressen die benötigt werden.

:sleeping:


#4

Wenn man ganz korrekt sein möchte dann sollte man

number == 2 
number < 2
number % 2 == 0

in einzelne Funktionen umwandeln und sich die Aufrufhäufigkeit anzuschauen. Entweder mit einem Profiler oder einfach mit einem counter hochzählen.

static int isEquals2FunctionCallCounter = 0;
public static boolean isEquals2(long number) {
    isEquals2FunctionCallCounter++;
    return number == 2;
}

Da wird man dann sehen, dass zwischen deiner iterativen und der rekursiven Variante deutliche Unterschiede zu sehen sind.

Zudem wird bei der Rekursion viel mehr Speicher verwendet. Während bei der Iteration lediglich ein Verweis auf die Funktion an sich und zwei long, number und i verwaltet werden müssen. Sind es bei der Iteration für jeden Iterationsschritt jeweils ein Verweis auf die Funktion, sowie zwei longs, number und i, was sich erheblich aufsummieren kann und auch Aufwand für Java bedeutet, obwohl das dennoch sehr effizient geschieht.

Interessanter als ein Vergleich
von 1 zu 1_000_000, ist ein Vergleich
von 2_000_000_000 bis 2_001_000_000 und dann noch
von 2_000_000_000_000 bis 2_000_001_000_000.


#5

Ergänzend zu dem was @ionutbaiu und @Spacerat geschrieben haben, Java kann leider keine Tail Recursion Optimiertung, wie andere Sprachen.Hier kannst du nachlesen was das im Detail bedeutet. Grob gesagt heißt das, dass der Compiler rekursive Methoden zu einer Schleife umwandeln kann, wenn das letzte Statement einer Methode der rekursive Aufruf selbst ist. Ich hab leider nicht auf die Schnelle rausfinden können, ob das in java irgendwann geplant ist.


#6

Naja, Endrekursion erweitert die Möglichkeiten zwar etwas, aber optimiert nicht unbedingt die Laufzeit.

Beliebig hohe Rekursionstiefe, allerdings muss die Laufzeit nicht unbedingt besser werden.


#7

Wenn die Endrekursion Optimierung die Laufzeit nicht verbessert, wofür wird diese dann gemacht / gedacht? - Und welche Möglichkeiten werden erweitert?

Dem Posting hier zu Folge gibt es keine klare Aussage: In verschiedenen Sprachen kann sich dies verschieden auswirken. Vermutlich ist das sogar so, dass in den Fällen, die hier betrachtet werden, aufgrund der Limitierung des Speichers egal ist, ob man rekursiv oder iterativ implementiert. Die Laufzeiten werden sich nicht sonderlich unterscheiden. Hast du auch selber festgestellt: 127 ms. Lass es eine Sekunde sein, immer noch egal.


#9

Das ist auf jeden Fall eine gute Idee - zum Üben und zum Verständnis.

Fast immer, zumindest ein wenig. Aber Performance ist ja hier nicht das wichtige, sondern die konzeptionelle Herangehensweise.

Schaust du einmal in ganz “praktischen” Code in einer funktionalen Sprache wie Haskell - in der es gar keine klassische Iteration mit Schleifenvariable geben kann *) - wirst du fast keine direkte Rekursion finden. Stattdessen werden Funktionen wie fold aufgerufen, die die Rekursion (zumindest konzeptionell) für dich übernehmen. Rekursion zu verstehen ist schön und gut, aber genauso wichtig ist, das Rad nicht immer wieder neu zu erfinden, sondern auf vorhandene, abstrakte Konstrukte wie map, fold, zip u.s.w. zurückzugreifen, die jeder funktionale Programmierer kennt und leichter lesen kann als explizite Rekursionen, die in der praktischen Anwendung durchaus haarig aussehen kann. Nebeneffekt dieser Vorgehensweise ist, dass der Haskell-Compiler diese Funktionen besonders optimieren kann **).

In JVM-Sprachen ist diese Optimierung einfach: Verwende “unter der Haube” Iteration. Genau das tun “funktionale” Bibliotheken wie vavr oder functionaljava, genau das tun die Standardbibliotheken in Scala. Sicher ist das nicht die reine Lehre, aber im Endeffekt macht es keinen Unterschied, denn eine solche Methode wird sich von außen gesehen nicht von einer mit Rekursion geschriebenen unterscheiden - außer dass sie ein klein wenig schneller ist, und keine StackOverflowException wirft. Diese “intern gemogelten” Methoden bilden dann die Grundbausteine für sauber geschriebenen funktionalen Code.

*) weil es dort keine veränderlichen Variablen gibt (allerdings Wege, sie zu “simulieren”)

**) manchmal sogar Ketten von Funktionsaufrufen, z.B: basierend auf Fusion Laws oder ähnlichem.


#10

Zumindest in manchen JVMs, z.B. IBMs J9, gibt es bereits Tail-recursion-elimination :wink:
Vielleicht findet es ja irgendwann auch Einzug in die Hotspot-JVM