Effizientere Rekursion

D

David2456

Aktives Mitglied
Hallo,
ich kenne mich mit der Effizients von Rekursionsformen nich wirklich aus.
Ich habe eine Beispiel Methode welche welche eine Repetetive Rekursion darstellt. Gibt es eine Rekursionsform welche effizienter ist?

Java: 
public static int powerRecursive(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * powerRecursive(base, exp - 1);
    }

Zum Überblick hier nochmal eine Seite in der alle Formen aufgelistet sind.
http://www.gehaxelt.in/blog/die-verschiedenen-rekursionsarten/
 
JStein52

JStein52

Top Contributor
Ich halte das was da unter dem link steht für einen Schmarrn. Und bei deinem Beispiel kannst du nichts anders machen. (Ok, wenn man es darauf anlegt kann man noch beliebige Dinge einbauen)
 
K

klauskarambulut

Bekanntes Mitglied
Die Rekursionstiefe ist begrenzt. Wenn der Exponent groß genug ist, dann verabschiedet sich das ganze mit einem Stackoverflow.

Es gibt Sprachen, die Tailcall-Optimisation durchführen. D.h. der Compiler baut das intern in eine Schleife um. Für Tailcall-Optimisation ist es allerdings Elementar, dass der Rückgabewert der Funktion nur aus dem Funktionsaufruf selbst bestehen darf.

Java: 
private static int powerRecursive(int acc, int base, int exp) {
  if(exp == 0){
    return acc;
  }
  return powerRecursive(acc * base, base, exp -1);
}

public static int powerRecursive(int base, int exp) {
  return powerRecursive(1, base, exp);
}

Funktioniert zwar in Java, da Java keine Tailcall-Optimisation macht hat man nichts gewonnen. Scala Code hat damit keine Probleme, so daß dort beliebig große Exponenten verwendet werden könnten.

Man kann allerdings die Rekursionstiefe verkleinern indem man das ganze etwas geschickter angeht.

Java: 
publicstaticint powerRecursive(int base, int exp){
  if(exp ==0){
    return1;
  }
  int halfExp = exp / 2;
  int rest = exp % 2;
  int powerOfHalf = powerRecursive(base, halfExp);
  return powerOfHalf * powerOfHalf + (rest * base);
}

Will man nun mit dem Exponenten 1024 etwas berechnen, dann ist
AufrufNr. mit Exponent
1. - 1024
2. - 512
3. - 256
4. - 128
5. - 64
6. - 32
7. - 16
8. - 8
9. - 4
10. 2
11. 1
12. 0

Wohingegen bei der Variante aus dem OP mit 1024 folgenden Call-Stack hat.
AufrufNr. mit Exponent
1. - 1024
2. - 1023
...
1024. - 1
1025. - 0

Also 1024 Aufrufe vs. 12
 
JStein52

JStein52

Top Contributor
z.B. weil überhaupt nichts dazu gesagt wird in welchen Eigenschaften sich diese "Rekursionsklassen" denn nun unterscheiden. Sogar der dortige Autor selber hatte keine schlüssige Erklärung auf die Nachfrage was das nun soll. "Damit man besser darüber diskutieren kann". Tolle Begründung.
Wichtiger als die Tatsache ob ich die rekursive Funktion denn nun links rum oder rechtsrum aufrufe ist das was @klauskarambulut oben gemacht hat: den Algorithmus so verändern dass die Rekursionstiefe nicht zu tief wird.
 
J

Joose

Top Contributor
Da hast du natürlich recht das in dem Blog nur erklärt wird woran man welche Art der Rekursion erkennen kann. Auch hat der Autor einen Fehler gemacht bei seiner Unterscheidung zwischen direkter und indirekter Rekursion (seiner Erklärung nach wäre eine verschränkte Rekursion eine indirekte und nicht wie im Blog dargestellt eine direkte).
Es gibt halt einen wirklich kurzen Einblick in die Unterscheidung von Rekursionen, natürlich sollte man sich andere Quellen auch noch anschauen.
 
JStein52

JStein52

Top Contributor
Joose hat gesagt.:
seiner Erklärung nach wäre eine verschränkte Rekursion eine indirekte und nicht wie im Blog dargestellt eine direkte
Zum Vergrößern anklicken....
Genau. Und was hilft mir das nun wenn ich weiss das ist diese oder jene Rekursionsform (ausser zu denken gut dass wir mal darüber geredet haben). Mal ganz im Ernst, hast du dir darüber in der Praxis schon mal Gedanken gemacht ? Und auch die Frage ob der Compiler das nun wegoptimiert oder nicht ist doch eher akademischer Natur. Auf solchen Informationen baue ich doch nicht mein Programm auf. Vielleicht habe ich morgen auf einer anderen Plattform einen anderen Compiler der das nicht tut ...
 
J

Joose

Top Contributor
Nein das habe ich auch nicht behauptet das es für einen "0815 Anwendungsentwickler/Programmierer" wichtig ist welche Art der Rekursion er einsetzt.
Aber es gibt sicher auch Gebiete wo man schon darauf achtet.
 
D

David2456

Aktives Mitglied
Danke klauskarambulut. Ich habe noch eine Frage. Wollte die Methode welche du geschrieben hast Testen, dabei kam aber ein Fehler raus java.lang.ArrayOutOfBoundsException: 0 at RecursivePower.main(RecursivePower.java:4). Funktioniert die Methode bei dir oder hab ich was falsch gemacht (ja ich habe die Leerzeichenfehler korrigiert)?
 
JStein52

JStein52

Top Contributor
Die werte die rauskommen sind irgendwie falsch, aber der Fehler den du da hast ist komisch da ja nirgends mit indices rumgerechnet wird. Den kriege ich nicht.
 
JStein52

JStein52

Top Contributor
Was heisst etwas eingeben ? Dann zeig uns doch mal den Rest deines Codes ? Da ist der Fehler wohl eher dort wo du die Methode aufrufst !! Wie gesagt, die Methode rechnet falsch aber sie liefert ein Ergebnis
 
D

David2456

Aktives Mitglied
Java: 
public class RecursivePower {

    public static void main(String... args) {
        int base = Integer.parseInt(args[0]);
        int exp = Integer.parseInt(args[1]);

        System.out.println(  base + "^" + exp + " = "
                           + powerIterative(base, exp)
                           + " (iteratively calculated).");

        System.out.println(  base + "^" + exp + " = "
                           + powerRecursive(base, exp)
                           + " (recursively calculated).");
    }

    public static int powerIterative(int base, int exp) {
        int pow = 1;
        for (int i = 0; i < exp; i++) {
            pow *= base;
        }
        return pow;
    }

public static int powerRecursive(int base, int exp){

       if(exp ==0){

           return 1;

       }

  int halfExp = exp / 2;
  int rest = exp % 2;
  int powerOfHalf = powerRecursive(base, halfExp);
  return powerOfHalf * powerOfHalf + (rest * base);

  }

}

Das ist der komplette Code
 
K

klauskarambulut

Bekanntes Mitglied
Java: 
public static int powerRecursive(int base, int exp) {
  if(exp ==0) {
    return 1;
  } 
  //braucht noch eine Prüfung auf exp == 1
  if(exp == 1) {
    return base;
  }
  int halfExp = exp /2;
  int rest = exp %2;
  int powerOfHalf = powerRecursive(base, halfExp);
  return powerOfHalf * powerOfHalf +(rest * base);
}
 
JStein52

JStein52

Top Contributor
2^3 ist dann aber 6 !!?? Irgendwas stimmt immer noch nicht. Ich glaube sämtliche ungeraden Exponenten sind falsch ??!!

Edit: Nö, stimmt auch nicht. Ist irgendwie noch ziemlich falsch.
 
K

klauskarambulut

Bekanntes Mitglied
machs doch besser!

Java: 
public static int powerRecursive(int base, int exp) { if(exp ==0) { return 1; } if(exp == 1) { return base; } int halfExp = exp /2; int rest = exp %2; int powerOfHalf = powerRecursive(base, halfExp); if(rest == 1) { return powerOfHalf * powerOfHalf * base; } else { return powerOfHalf * powerOfHalf; } }
 

Aktuelle Jobs

Neue Themen


Oben