Stürzen alle Rekursive Methoden irgendwann ab?

M

Mikrowelle

Bekanntes Mitglied
Code:
    int loop(int x){
        try {
                return loop(x+1); 
                
        } catch (StackOverflowError e) {
            System.out.println(x);
        }
        
   return 1;
    }

Bei mir ist nach 9000 aufrufen ende. Wenn jetzt aber eine Sinnvole Methode wäre die erst nach 10k loops zu ende wäre. Dann hätte ich doch ein Problem oder ?

Wenn ja kann man das rekursiv lassen und das Problem irgendwie lösen ?
 
tfa

tfa

Top Contributor
Die Rekursion braucht immer ein Abbruchkriterium, sonst läuft irgendwann der Stack über. Wann das nicht möglich ist oder du zu viele Aufrufe brauchst, darfst du keine Rekursion verwenden.
 
S

SlaterB

Gast
man kann auch bisschen mit Platz für Stack schaffen,
Java stack overflow error - how to increase the stack size in Eclipse? - Stack Overflow
wobei ich mich zu erinnern glaube dass das entweder nur für den main-Thread gilt oder für den gerade nicht, weitere Einstellungen evtl. nötig

aber sinnvoll sind solche Tiefen nicht wirklich

schließlich kann man auch noch jede Rekursion in eine Iteration umwandeln, z.B. die Daten einer Runde in einer Liste zwischenspeichern,
bei verschiedenen, evtl. unbekannten Methoden durcheinander wird das natürlich nicht so schön, evtl. braucht es dann auch ganze Runnable-Objekte, Methoden mit Code die an bestimmten Punkten Pause machen usw.,
das wird aber nur schlimmer je länger ich rede, bestimmt kein Ziel zu deiner Frage
 
Zuletzt bearbeitet von einem Moderator:
tfa

tfa

Top Contributor
Vernünftige funktionale Programmiersprachen können sogar (End-)Rekursion automatisch in Iteration umwandeln. Das Beispiel würde dann wirklich zu einer Endlosschleife werden und keinen StackOverflowError mehr werfen. Aber in Java muss man das von Hand machen - sofern möglich.
 
Landei

Landei

Top Contributor
Es gibt Techniken, das in Sprachen ohne TCO zu vermeiden, siehe z.B. Trampolining

Allerdings wäre es in Java (ohne Closures) ziemlich wüst, so was von Hand zu programmieren. In Scala kann man das z.B. verwenden, um zwei indirekt (tail call-) rekursive Funktionen, die sich gegenseitig aufrufen, ohne Stackoverflow zu implementieren.
 
Zuletzt bearbeitet:
T

trääät

Gast
grundsätzlich sollten rekursionen immer sinnvolle terminierungen haben ... in diesem fall z.b. wenn x==0 oder sowas ... aber da ja bei dir nach gut 9k schluss ist würde x==0 auch bei x=12k als initialwert immer noch crashen ...

man muss eine rekursion so aufbauen das diese normal ohne stackoverflow terminieren kann .. ansonsten ist es ein fehler des programmierers
 
Landei

Landei

Top Contributor
man muss eine rekursion so aufbauen das diese normal ohne stackoverflow terminieren kann .. ansonsten ist es ein fehler des programmierers

Jain. Wenn man das Problem mit der JVM (einige JVMs können TCO, leider nicht die von Oracle) oder dem Compiler (wie es Scala macht) lösen kann, ist es ziemlich dumm, das dem Programmierer aufzubürden, insbesondere wenn sich mit Rekursion einige Probleme deutlich eleganter lösen lassen (vor allem, wenn innerhalb der Methode mehrere rekursive Aufrufe erfolgen, wie bei diversen Algorithmen auf Bäumen) als iterativ.

Aber natürlich sollte man als Programmierer diese Beschränkung beachten, wenn es sie nun leider FSMs gibt.

Nebenbei gibt es einen weiteren Weg, den Stackoverflow zu verhindern: Man kann die aktuelle Tiefe mitzählen, und wenn es zu tief wird, selbst eine Exception - allerdings mit Argumenten und Zwischenresultaten - werfen. Eine umgebende Methode fängt diese Exception, und startet die Rekursion mit den Werten aus der Exception neu. Ich denke, ich brauche nicht viel über Aufwand und Lesbarkeit dieser Technik zu referieren, aber es ist zumindest eine Möglichkeit.
 
Zuletzt bearbeitet:
Landei

Landei

Top Contributor
Hier ein Beispiel für diese Methode:

Java:
public class RecursionException extends RuntimeException {

    public Object arg;

    public RecursionException(Object arg) {
        this.arg = arg;
    }

    public Object getArgs() {
        return arg;
    }
}

public abstract class Recursion<T> {

    private final int maxStackDepth;
    private int stackDepth = 0;

    public Recursion(int maxStackDepth) {
        this.maxStackDepth = maxStackDepth;
    }

    public abstract T run(Object arg) throws RecursionException;

    public void increaseDepth(Object arg) {
        stackDepth++;
        if (stackDepth == maxStackDepth) {
            stackDepth = 0;
            throw new RecursionException(arg);
        }
    }

    public T call(Object arg) {
        Object currentArg = arg;
        while (true) {
            try {
                return run(currentArg);
            } catch (RecursionException ex) {
                System.out.println("catched!"); //nur zu Testzwecken
                currentArg = ex.getArgs();
            }
        }
    }
}

public class RecursionTest {

    public static void main(String... args) {
        System.out.println(addUp(1000,0));
        //System.out.println(addUp(100000,0));  --> StackoverflowException

        //der analoge Aufruf:
        Recursion<Long> rec = new Recursion<Long>(1000) {

            @Override
            public Long run(Object arg) throws RecursionException {
                increaseDepth(arg);
                long[] data = (long[]) arg;
                if (data[0] == 0) return data[1];
                return run(new long[]{data[0]-1,data[0]+data[1]});
            }
        };
        System.out.println(rec.call(new long[]{100000, 0}));
    }

    private static long addUp(int i, long sum) {
        if (i == 0) return sum;
        return addUp(i-1, sum + i);
    }
}

Wirklich nicht hübsch, läuft aber...

Übrigens muss man aufpassen, dass man nicht mit gewrappten Primitiven arbeitet, sonst bekommen die (also deren Cache) eine StackoverflowException - da sollte Oracle auch mal nachbessern...
 
Zuletzt bearbeitet:
T

tröööt

Gast
mir ist klar was du meinst ... aber es gibt nun mal gewisse "empfohlene grundsätze" (ich rede jetzt eher weniger von den conventions) an die man sich halten sollte ...
ob man jetzt wirklich "exception-missbrauch" verantstaltet um den code an sich "nach außen hin" exception-/error-frei zu halten ... naja ... geteilter meinung ... aber wenn man in rekursive methode überhaupt keine abbruchbedingung reinschreibt sondern dafür den error-catch missbraucht hat man defintiv als programmierer versagt ...
wenn man allerdings eine abbruchbedingung verwendet und diese aber auf grund von fehlern nicht erreicht werden kann muss man halt nachbessern ...

ich bin z.b. auch der auffassung das "normale" java-programme komplett in einer "normalen" VM laufbar sein sollte OHNE das man z.b. an heap und/oder stack größen rumschraubt ...
 
S

SlaterB

Gast
> aber wenn man in rekursive methode überhaupt keine abbruchbedingung reinschreibt sondern dafür den error-catch missbraucht hat man defintiv als programmierer versagt

beziehst du dich allein auf das erste Posting? das war doch nun wirklich ein Testprogramm, um überhaupt die Stack-Tiefe festzustellen,
(wobei gefährlich ist ob das System.out.println() mit nochmal paar Stack-Tiefen überhaupt ginge,
lieber anders testen, etwa ein Instanzattribut erhöhen, und später nach Zusammenfall des gesamten Stacks ausgeben)

da hätte man natürlich noch 100.000 als ewig hohe Test-Grenze einbauen können, wäre es dann schöner?
sollte doch nun wirklich genau bis zur Exception laufen, als Test..,
welchen anderen fachlichen Sinn sollte das überhaupt haben, damit kann man doch kein sinnvolles Programm bauen, nichtmal auf falschen Wege
 
Landei

Landei

Top Contributor
aber wenn man in rekursive methode überhaupt keine abbruchbedingung reinschreibt sondern dafür den error-catch missbraucht hat man defintiv als programmierer versagt ...

Schau mal genau hin, ich haba auch eine normale Abbruchbedingung (nämlich [c]if (data[0] == 0) return data[1];[/c]), die Exception wird nur ausgelöst, wenn der Stack zu groß wird, danach geht's weiter.
 
B

Bernd Hohmann

Top Contributor
Wie tfa schrieb, kann man Rekursion oft in Iteration auflösen.

Das eigentliche Problem bei der Rekursion ist, dass der gesamte Variablen"müll" (sofern nicht mit einem Compilertrick wegoptimiert) der Methode auf den Stack geschmissen wird. Grössere Methoden mit vielen Variablen sind daher die eigentlichen Dickmacher auf dem Stack.

Viele Algorithmen brauchen nur eine einzige Variable auf dem Stack und daher kann man zb. QuickSort in eine Art Iteration auflösen, in dem man den Pivot-Pointer einfach in ein Array steckt und einen Arrayzeiger mitführt.

Mit sowas kann man wahre Speichermonster in handzahme Flöhe verwandeln.

Bernd
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
H Alle Geraden zahlen bis 10 ausgeben Java Basics - Anfänger-Themen 11
L Alle Ziele in einem Raster abknallen Java Basics - Anfänger-Themen 17
J Alle Werte eines Strings zusammen addieren Java Basics - Anfänger-Themen 15
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
B Alle Links in einem Text suchen und ersetzen mit einem neuen Link Java Basics - Anfänger-Themen 18
K Array alle Werte aufsummieren und ausgeben Java Basics - Anfänger-Themen 6
Dimax Erste Schritte String replace alle Zeichen Java Basics - Anfänger-Themen 10
L Wie vergrößere ich ein Rechteck in alle Richtungen um eins und bekomme dessen Rand? Java Basics - Anfänger-Themen 2
L Breadth-First Search statt einem Pfad, alle Pfade herausfinden Java Basics - Anfänger-Themen 4
X Erste Schritte String: Alle doppelten Leerzeilen entfernen Java Basics - Anfänger-Themen 21
M Regex-Ausdruck: Alle Zeichen bis auf ein bestimmtes erlauben (p{L}) Java Basics - Anfänger-Themen 5
I Alle Elemente von zwei Listen vergleichen Java Basics - Anfänger-Themen 1
Kirby_Sike Alle möglichen Error Möglichkeiten abfangen Java Basics - Anfänger-Themen 33
M Unterklasse soll nicht alle Methoden erben Java Basics - Anfänger-Themen 3
V Erste Schritte for-Schleife; Ausgabe soll alle 5 Sekunden erfolgen. Java Basics - Anfänger-Themen 4
A Alle true Werte eines boolean Arrays herausfiltern Java Basics - Anfänger-Themen 19
D Alle Möglichkeiten, n-Anzahl aus Elementen aus einem Array zu wählen, ausgeben? Java Basics - Anfänger-Themen 23
M prüfen ob alle array werte gleich sind Java Basics - Anfänger-Themen 27
F Alle Zeichenkombinationen eines Strings iterativ herausfinden Java Basics - Anfänger-Themen 26
L Classpath Alle Dateien im Classpath finden Java Basics - Anfänger-Themen 4
G Überprüfen ob alle Ziffern von 1-9 in einem Integer vorhanden sind Java Basics - Anfänger-Themen 6
J Erste Schritte Alle möglichen ausgaben von 5 Zahlen als Vector Java Basics - Anfänger-Themen 7
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
D Methoden Eigene Methode um alle Ausgaben aufzurufen Java Basics - Anfänger-Themen 17
F Ordner auf alle Unterdatein abfragen Java Basics - Anfänger-Themen 3
A In einem String alle Eigennamen zählen Java Basics - Anfänger-Themen 6
B Klassen Alle Unter-Objekte durchlaufen in der Hauptklasse Java Basics - Anfänger-Themen 10
W ArrayList löscht alle Elemente bis auf eines Java Basics - Anfänger-Themen 2
B Webservice -> alle parameter bekommen von form Java Basics - Anfänger-Themen 2
das_leon Alle Zeilen einer CSV-Datei auslesen Java Basics - Anfänger-Themen 1
C HashMap - alle keys haben values der letzten put-Anweisung Java Basics - Anfänger-Themen 3
F Eclipse alle Projekt weg Java Basics - Anfänger-Themen 6
V Alle Komponenten eines JPanels Java Basics - Anfänger-Themen 14
I gemeinsame Config-Datei für alle Windows-User Java Basics - Anfänger-Themen 5
H JButton - Wechsel der Textfarbe alle 500ms Java Basics - Anfänger-Themen 10
DaCrazyJavaExpert Alle Zahlenkombinationen aus 9 zahlen finden Java Basics - Anfänger-Themen 17
F Alle Objekte einer Klasse nach Eigenschaft durchsuchen Java Basics - Anfänger-Themen 8
M Alle Instanzen einer Klasse ansprechen Java Basics - Anfänger-Themen 4
S Problem: Array alle Einträge gleich Java Basics - Anfänger-Themen 10
Z Enter Taste alle 0,5 Sekunden ausführen Java Basics - Anfänger-Themen 1
U RegEx alle Kommas bei den Zahlen in Punkt umwandeln Java Basics - Anfänger-Themen 3
K alle Vorkommen einer bestimmten Ziffer in einer Zahl zählen Java Basics - Anfänger-Themen 2
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
C Alle Zweierpotenzen bis 2^10 ausgeben lassen Java Basics - Anfänger-Themen 15
B Alle Attribute von Klasse bekommen und ändern Java Basics - Anfänger-Themen 12
M Input/Output Alle Zeilen auslesen und in Variable speichern Java Basics - Anfänger-Themen 5
W Mozilla Thunderbird email an alle Kontakte Java Basics - Anfänger-Themen 3
F Methode alle 15min ausführen Java Basics - Anfänger-Themen 5
D Alle möglichen Kombinationen in einem Array ausgeben Java Basics - Anfänger-Themen 2
I Alle Laufwerke und deres Pfade ausgeben Java Basics - Anfänger-Themen 6
S Classpath: Alle .jars innerhalb eines Ordners einbinden Java Basics - Anfänger-Themen 4
G Alle Objekte und Variablen automatisch ausgeben Java Basics - Anfänger-Themen 7
I Programm, welches eine Textzeile einliest und alle darin enthaltenen Buchstaben umwandelt Java Basics - Anfänger-Themen 3
G Wie bekomme ich alle Ausgaben von runTime.exec() Java Basics - Anfänger-Themen 7
L Best Practice Alle Kombinationen aus Listenelementen, Anzahl Listen unterschiedlich Java Basics - Anfänger-Themen 6
M Compiler-Fehler Alle Methoden eines Interfaces Implementiert dennoch Fehler Java Basics - Anfänger-Themen 3
I Alle Zeitzonen in Liste speichern Java Basics - Anfänger-Themen 4
F alle 100ms Befehle ausführen Java Basics - Anfänger-Themen 26
M Alle Sublisten einer bestimmten Laenge berechnen Java Basics - Anfänger-Themen 2
F Alle DEMOS fast veraltet...? Java Basics - Anfänger-Themen 13
J Alle Leerzeichen aus String entfernen Java Basics - Anfänger-Themen 13
D Methoden Alle Siebenstelligen Primpalidrome von PI Java Basics - Anfänger-Themen 6
K Durch alle Attribute eines Objektes iterieren Java Basics - Anfänger-Themen 6
P Klassen Alle Strings einer ArrayList<eigeneKlasse> anspre Java Basics - Anfänger-Themen 2
W String von hinten alle drei Zeichen abschneiden und in umgekehrter Reihenfolge ausgeben. Java Basics - Anfänger-Themen 9
M Alle möglichen Strings Java Basics - Anfänger-Themen 5
J Alle Wörter der Länge n mit 0 und 1 Java Basics - Anfänger-Themen 17
T Alle Threads .notify() Java Basics - Anfänger-Themen 13
G Methoden Alle Objekte der ArrayList ausgeben funktioniert nicht. Java Basics - Anfänger-Themen 12
N Klassen Class nur einmal ausführen und sie speichert daten für alle anderen classes? Java Basics - Anfänger-Themen 3
M Klassen Auf Alle Array Methoden gleichzeitig zugreifen Java Basics - Anfänger-Themen 8
D Frame schließt gleich alle Frames Java Basics - Anfänger-Themen 5
T Wie mache ich einen Timer der alle 2 sekunden aufgerufen wird? Java Basics - Anfänger-Themen 5
D JFileChooser "alle Dateien" unterbinden Java Basics - Anfänger-Themen 3
S Aus zwei Dateipfaden alle Dateien auslesen Java Basics - Anfänger-Themen 11
B Frage zur Effizienz - alle Array-Felder initialisieren oder jedes Feld auf null prüfen? Java Basics - Anfänger-Themen 4
F Geht in alle Case rein, warum?? Java Basics - Anfänger-Themen 12
R Alle Klassen ermitteln, die Interface implementieren / Reflection Java Basics - Anfänger-Themen 51
M Primzahlen - es werden alle Nicht-Primzahlen ausgegeben Java Basics - Anfänger-Themen 5
L RandomAccessFile liest nicht alle Zeichen Java Basics - Anfänger-Themen 3
S Warten bis alle Threads fertig sind Java Basics - Anfänger-Themen 12
M Class will alle Variablen als static haben Java Basics - Anfänger-Themen 11
E Erste Schritte Eclipse kompiliert alle Projekte im Workspace Java Basics - Anfänger-Themen 10
J Alle Vorkommen eines chars in einem Array durch einen anderen char ersetzen Java Basics - Anfänger-Themen 10
S Alle 60min prüfen ob eine Datei da ist Java Basics - Anfänger-Themen 6
Dit_ Funktion alle 24 Stunden ein mal aufrufen Java Basics - Anfänger-Themen 3
Dit_ Input/Output Alle Exceptions protokollieren Java Basics - Anfänger-Themen 9
S Regex - alle Matches ausgeben? Java Basics - Anfänger-Themen 2
2 Alle Werte die mit n Würfeln mit m Seiten geworfen werden können in ein n Dimensionales Array Java Basics - Anfänger-Themen 15
B Alle Benutzer anzeigen Java Basics - Anfänger-Themen 17
S Suchmaske alle Möglichkeiten effinzent durchgehen Java Basics - Anfänger-Themen 4
R Kurze Linien alle x-Pixel Java Basics - Anfänger-Themen 2
K Alle vorkommen eines Zeichens in StringBuffer Objekt löschen Java Basics - Anfänger-Themen 6
D X Werte in ArrayList von Point Objekte alle gleich ? Java Basics - Anfänger-Themen 11
H Alle Array-Elemente auf einmal überprüfen? Java Basics - Anfänger-Themen 10
R Alle Daten einer HashMap ausgeben Java Basics - Anfänger-Themen 17
S mysql-connector-java-*.jar, MySql ResultSet - Alle ROWs ausgeben? Java Basics - Anfänger-Themen 3
S alle instanzen einer klasse löschen Java Basics - Anfänger-Themen 18
N Variable für alle Klassen Java Basics - Anfänger-Themen 6
J Subklasse soll alle Klassen/Pakete der Superklasse importieren Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Anzeige


Oben