rekursive vs. iterative Lösung für Berechnung der Fakultät

[Private Void]

Welche der beiden folgenden Lösungen findet erachtet zur Berechnung der Fakultät für besser - oder kann man gar keine qualitative Unterscheidung bezüglich Laufzeit- bzw. Speicherplatzkomplexität oder sonst irgendwas trefen?

Oder anders gefragt: Welche Vorgehensweise würdet ihr bevorzugen?

public class FakultaetRekursiv {
        public static void main(String[] args) {
                System.out.println(fakultaet(15));
	}
	
        public static double fakultaet(double a){
                if(a==0){
                        return 1;
                }else if(a==1){
                        return a;
                }else{
                        return a*fakultaet(a-1);
                }
        }
}

public class FakultaetIterativ {
	public static void main(String[] args) {
		double a=1;
		
		for (int i = 2; i <= 15; i++) {
			a=a*i;
		}
		System.out.println(a);
	}
}

 

[xerberuz]

Das ist schwer zu sagen. Eigentlich ist eine iterative Lösung schneller. Allerdings trifft das nicht immer zu. Der Compiler kann einfache Rekursionen wegoptimieren. Scala z.B. unterstützt Endrekursion was die rekursiven aufrufe auch optimiert.

Es gibt auch Fälle in denen die rekursive Lösung einfach um einiges eleganter ist. Deshalb kann man wohl keine allgemeingültige Aussage treffen.

 

[bygones]

Das ist schwer zu sagen. Eigentlich ist eine iterative Lösung schneller. Allerdings trifft das nicht immer zu. Der Compiler kann einfache Rekursionen wegoptimieren. Scala z.B. unterstützt Endrekursion was die rekursiven aufrufe auch optimiert.

du kannst auch in Java Endrekursive Funktionen programmieren...


abgesehen davon stimmt deine rekursive loesung nicht ganz... ruf mal [c]fakultaet(1)[/c] auf

 

[xerberuz]

du kannst auch in Java Endrekursive Funktionen programmieren...

Programmieren kann man sie. Aber ob der compiler das optimiert ist eine ganz andere Frage. In vielen Funktionalen Sprachen ist es "vorgeschrieben", dass diese optimierung vorgenommen werden muss. In Java nicht.

Es ist auch keine Optimierung die in der JVM vorgenommen wird, sondern vom Compiler.

 

[Private Void]

abgesehen davon stimmt deine rekursive loesung nicht ganz... ruf mal [c]fakultaet(1)[/c] auf

Hab's geändert. Kannst du nun damit leben ?

 

[zwergmulch]

Ich kann damit nicht leben:
Fak. ist nur für int's definiert. (Du hast Double)
Außerdem würde ich lieber BigInteger nehmen. Außerdem solltest du

if (a == 0 ||a == 1) return 1;

schreiben. Nur so am Rande.
Und schließlich - ruf mal fak(-1) auf.

Sonst siehts eigentlich gut aus.

 

[TrickySys]

Hey!
Hehe, "zwergmulch" hat da wohl recht, aber schließlich ist es jedem dasseine wie er/sie seinen Algorithmus gestaltet. Somit habe ich bereits auch deine Frage angeschnitten. Die Effizienz ist schlecht zu beurteilen, meistens kommt es darauf an worum es überhaupt geht... . Wenn es um die Eleganz geht, stehen meiner Meinung nach die rekursiven Algorithmen weit über den iterativen, ist halt geschmacksache.
Währenddessen ist dies mein erster Beitrag, deshalb wünsch ich allen eine wundervolle gemeinsame Zeit .

 

[JohannisderKaeufer]

Ich kann damit nicht leben:
Fak. ist nur für int's definiert. (Du hast Double)
Außerdem würde ich lieber BigInteger nehmen. Außerdem solltest du

if (a == 0 ||a == 1) return 1;

schreiben. Nur so am Rande.
Und schließlich - ruf mal fak(-1) auf.

Sonst siehts eigentlich gut aus.

wenn dann so:

if(a==0) return 1;

der Rekursive aufruf tuts dann auch für 1!, die überprüfung auf a==1 ist cocolores.

Und komm mir ja nicht auf die Idee zu antworten, das das die Rekursionstiefe verkürzen würde!

Denn sonst....


kannst du auch gleich auf a == 2, a == 3, a == 4.....
überprüfen. Das verkürzt die Rekursionstiefe ebenfalls.

und -1 ist doch auch ok. -1 ist ja nicht definiert und die exception fliegt. Es dauert vielleicht nur ein wenig, aber sie fliegt.

 

[zwergmulch]

Ein StackOverflowError ist ok? Naja, ich würde eine RuntimeException vorziehen,
anstatt eine mehr oder eher weniger klare Fehlermeldung zu erhalten.
@

if (a == 0) return 1;

Naja, er hat geschrieben:

if (a==1) return a;

was ein unnützer zusätzlicher Speicherzugriff ist.
Außerdem wird bei fak(0) ja das selbe zurückgegeben.
Und die Rekursionstiefe verkürzt es wirklich nicht.
Ist letztendlich auch egal - darum auch das "" am Ende.

 

[Private Void]

Um endgültig der Frage auf den Grund zu gehen, ob die rekursive oder iterative Variante besser ist (zumindest bezogen auf die Berechnung der Fakultät), hab ich gerade folgenden "Versuchsaufbau" entworfen (Kritik erlaubt).
Es misst die Zeit, die jede Variante jeweils benötigt.

Das Ergebnis: die iterative Variante ist schneller als die rekursive.

import java.math.BigInteger;

public class Fakultaet {
	static BigInteger one=BigInteger.ONE;
	
	public static void main(String[] args) {
		BigInteger a=new BigInteger("75"); // Zahl, die "fakultiert" wird
		
		System.out.println(a+"!");
		System.out.println("-----");
		
		System.out.println("rekursive Variante");
		double time=(double)System.nanoTime(); // Startzeit
		System.out.println("Ergebnis: "+rekursiv(a));
		System.out.println("Zeit: "+((double)System.nanoTime() - time) / 1000000+" ms"); // Zielzeit
		
		System.out.println("-----");
		
		System.out.println("iterative Variante");
		time=(double)System.nanoTime();
		System.out.println("Ergebnis: "+iterativ(a));
		System.out.println("Zeit: "+((double)System.nanoTime() - time) / 1000000+" ms");
	}
	
	private static BigInteger rekursiv(BigInteger a){
		if(a.equals(BigInteger.ZERO)){
			return one;
		}else{
			return rekursiv(a.subtract(one)).multiply(a);
		}
	}
	
	private static BigInteger iterativ(BigInteger a){
		BigInteger n = one;
		
		do{
			n=n.multiply(a);
			a=a.subtract(one);
		}while(!a.equals(one));
		
		return n;
	}
}

 

[Ebenius]

Das Ergebnis: die iterative Variante ist schneller als die rekursive.

Bei mir nicht. Mal so mal so. Micro-benchmarks eben.

Ebenius

 

[Private Void]

Bei mir nicht. Mal so mal so. Micro-benchmarks eben.

Bei mir ist das bei 15 Versuchen einmal vorgekommen, dass die rekursive Variante schneller war - also hab ich diesen Schluss daraus gezogen.
Ich wollte schon fragen, ob dieses "Phänomen" einen Namen hat, dass bei jedem Versuch mit der selben Zahl andere Zeiten rauskommen, aber du hast mir die Bezeichnung ja hiermit geliefert .

 

[Landei]

Wenn ich mal eine einfache iterative Implementierung in den Raum werfen dürfte:

    public static long fak(int n) {
        if (n == 0) return 1;
        long r = (n + 1) / 2;
        long mm = r*r;
        int ii = 1;
        int k = 1;
        while (ii < mm) {
            r *= mm - ii;
            k += 2;
            ii += k;
        }
        return n % 2 == 0 ? n * r : r;
    }

Sie braucht nur etwa halb soviel Multiplikationen wie die "naive iterative" Lösung.

Ansonsten sei dem ernsthaft Interessierten die Seite von Herrn Luschny ans Herz gelegt (die Lösung hier dürfte dort dem "Squared Difference"-Algorithmus entsprechend).