# Effizientere Rekursion



## David2456 (15. Dez 2015)

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?


```
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 (15. Dez 2015)

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)


----------



## klauskarambulut (15. Dez 2015)

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.


```
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.


```
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


----------



## Joose (15. Dez 2015)

JStein52 hat gesagt.:


> Ich halte das was da unter dem link steht für einen Schmarrn.



Weil? Eine Begründung wäre hilfreich um die Aussage zu verstehen


----------



## JStein52 (15. Dez 2015)

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.


----------



## Joose (15. Dez 2015)

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 (15. Dez 2015)

Joose hat gesagt.:


> seiner Erklärung nach wäre eine verschränkte Rekursion eine indirekte und nicht wie im Blog dargestellt eine direkte


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 ...


----------



## Joose (15. Dez 2015)

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.


----------



## JStein52 (15. Dez 2015)

Was sagst du nun dem TE auf seine Frage ??


----------



## David2456 (15. Dez 2015)

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 (15. Dez 2015)

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.


----------



## David2456 (15. Dez 2015)

Nein bevor ich überhaupt etwas eingeben konnte kam der Fehler sprich nach dem   java RecursivePower


----------



## JStein52 (15. Dez 2015)

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


----------



## David2456 (15. Dez 2015)

```
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


----------



## JStein52 (15. Dez 2015)

Ok. Und gibst du deinem Programm beim Aufruf denn nun die beiden Parameter die es erwartet mit ?
(args[0]  und args[1])


----------



## klauskarambulut (15. Dez 2015)

```
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 (15. Dez 2015)

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.


----------



## klauskarambulut (16. Dez 2015)

machs doch besser!



Spoiler





```
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; } }
```


----------



## David2456 (16. Dez 2015)

Vielen Dank klauskarambulut. Funktioniert


----------

