Endrekursiv vs Rekursiv

[Mart]

Also ich versteh den Unterschied nicht warum man etwas endrekursiv machen sollte wie zb

    public static int fak(int n , int akk) {
        return n != 0 ? fak(n-1, akk*n) : akk;
    }

im gegensatz zu

public static int fak(int n) {
return n != 0 ? n*fak(n-1) : 1;
}

ich versteh schon wie es funktioniert aber hab keinen plan warum man dieses oder jenes hernehmen sollte
bzw was die begründung wäre sich für eines zu entscheiden

 

[httpdigest]

Endrekursionen kann man _immer_ in eine äquivalente iterative Schleifen-Form ohne zusätzlichen dynamischen Speicher transformieren (zusätzlich gibt es auch Laufzeitumgebungen und Compiler, die das automatisch tun - die JVM gehört _nicht_ dazu (weswegen man auch bei eigentlich tail-recursive Methoden immer noch eine StackoverflowException bekommen kann)!). Das ist bei allgemein-rekursiven Funktionen nicht möglich. Dort braucht man im allgemeinen Fall zumindest immer einen Stack als dynamische Datenstruktur (was bei der Rekursion ja der Callstack war).

 

[Mart]

der callstack kann doch auch immer noch in einen overflow enden

 

[httpdigest]

der callstack kann doch auch immer noch in einen overflow enden

Bei rekursiven Aufrufen, die eben nicht durch eine automatische Compilertransformation in eine iterative Variante umgeformt wurde (wie es z.B. auch die JVM nicht tut), ja. Genau das habe ich ja auch gesagt.

Endrekursionen kann man _immer_ in eine äquivalente iterative Schleifen-Form ohne zusätzlichen dynamischen Speicher transformieren [...]. Das ist bei allgemein-rekursiven Funktionen nicht möglich.

Vielleicht störte dich ja auch die zweifache Klammerverschachtelung in meinem Satz, die ich gerade bemerkte.

 

[Flown]

Kurze Berichtigung:
- JVM (HotSpot) hat (noch) keine JIT-Optimierung für tail-recursive Funktionen
- Java Compiler hat keine Endrekursion Optimierung
- Scala, Kotlin und andere JVM Sprachen haben sehr wohl tail-recursion Optimierungen