Rekursion

[fleckdalm]

Ich glaube ich verstehe jetzt zumindest so ungefähr wie rekursion funktioniert aber was ich nicht verstehe ist der sinn der rekursion, wann verwendet man so etwas? und kann man das in den meisten fällen mit schleifen nicht viel einfacher lösen?
mfg Fleckdalm

 

[nrg]

Ich finde man kommt iterativ schon sehr gut aus. Manche Rekursionen sind aufgrund von Stack Overflows eh nicht brauchbar. Das einzige woran ich mich jetzt spontan erinnern kann, das ich rekursiv gelöst habe, war das Auslesen aller Dateien von einer Root ausgehend. Das wäre aber glaube genauso iterativ machbar, wenn auch vllt etwas hässlicher...

 

[XHelp]

Du benutzt es einfach dann, wenn es sich besser anbietet. Und nein, mit Schleifen kannst du es nicht immer einfacher lösen. Solche intuitiv-rekursiven Sachen wie Baumsuche lassen sich durch Rekursionen besser beschreiben.

Generell müssten die Rekursionen gleichmächtig mit While-Schleifen sein (in Java: generell mit Schleifen). Aber die Umformung kann manchmal etwas komisch aussehen.

 

[Marco13]

Sowas wie die Türme von Hanoi iterativ ist schon ekliger als der rekursive Dreizeiler. Allgemein eben, wenn man auf Strukturen wie Bäumen arbeitet, oder bei bestimmten mathematischen Funktionen, die schon so gegeben sind, dass man sie rekursiv "einfach hinschreiben" kann, aber für iterative Form erst... denken müßte ....

 

[muckelzwerg]

Rekursionen sind ziemlich interessant, wenn Du Dich mehr mit Mathe, Logik und formalen Sprachen beschäftigst.
Und das wiederum ist nicht soo weit weg, wie man manchmal (gerne) glaubt.
Stell Dir vor, Du würdest ein Progamm entwickeln, das mathematische Terme löst. Also z.B. ein Taschenrechner, der nicht nur ein paar Knöpfe hat, um mit der Maus draufzupatschen, sondern auch eine aufwändigere Texteingabe ermöglicht.
Da bietet sich ein rekursiv absteigender Parser an, der den Rechenbaum erzeugt.

Oder vielleicht ein Lösungsprogramm für ein Spiel? Auch da kann rekursive Abarbeitung sehr angenehm sein. Zum Beispiel lässt sich der Minimax-Algorithmus leicht rekursiv implementieren. Und damit kann man immerhin mal einen "Schachcomputer" entwickeln. (wenn auch nicht unbedingt den nächsten Weltmeister ^^)
Hier hat doch gerade jemand wieder einen Sudoku-Solver geschrieben. Nimm doch mal den Begriff "Rekursion" und schau da mal rein.
(hab den Code noch nicht gelesen)

 

[shiroto]

Stichwort: Funktionale Programmiersprachen. In Java wirst du (je nachdem was du machen willst) wahrscheinlich wirklich nicht allzu viel rekursionen brauchen. Aber solltest du mal in ProLog oder LisP arbeiten wirst du um rekursion kaum rum kommen. Rekursion ist auch DAS thema bei KI programmierung. Also sie hat schon ihre daseinsberechtigung ^^

 

[kirax]

Jede Rekursion lässt sich in eine Iteration umformen. Das lässt sich beweisen und es gibt sogar Programme die das bewerkstelligen können (auch umgekehrt, z.B. als obfuscator).
Ich hatte früher auch meine Probleme mit Rekursion, weil ich es nicht verstanden habe (getreu dem Motto "um Rekursion zu verstehen, muss man erst Rekursion verstehen"), aber wenn man einmal dahinter gekommen ist, ist es ein super Werkzeug.
Da lassen sich dann viele Probleme rekursiv "intuitiv" lösen. Beispiele wurden ja schon zur Genüge genannt.

 

[rekursion?]

Sowas wie die Türme von Hanoi iterativ ist schon ekliger als der rekursive Dreizeiler. Allgemein eben, wenn man auf Strukturen wie Bäumen arbeitet, oder bei bestimmten mathematischen Funktionen, die schon so gegeben sind, dass man sie rekursiv "einfach hinschreiben" kann, aber für iterative Form erst... denken müßte ....

Bei Türme von Hanoi gibt es iterativen Code, der quasi wie der aufgelöste Rekursionscode ist, aber auch andere iterative Algorithmen, die nicht aus den rekursiven entlehnt sind.

Bei Rekursion gibt es immer ein/e/n Problem/Lösung/aktuellen Stand usw. das/die/der bei jedem Rekursionsschritt als Parameter mitgegeben und verändert wird, einen/mehrere rekusive(n) Aufruf(e) und eine Abbruchbedingung, die mit einem der Parameter zusammenhängt. Man muss sich nur überlegen, wie das Problem ist, wenn man es um einen Schritt weiter löst. Dadurch erhält man kürzeren übersichtlicheren Coder, der "eleganter" sein soll als ein iterativer Code...

 

[Andi_CH]

Manche Lösungen sind rekursiv einfach einfacher zu verstehen.

Da kannst du direkt vergleichen Türme von Hanoi iterativ und Türme von Hanoi rekursiv

Vor allem bei der Rekursion musst du beim Main mit lesen beginnen - das sieht dann so richtig banal aus ;-) während ich die iterative LKösung nicht einmal selbst gefunden hätte (ich meine das jetzt nicht programmier- sondern problemtechnisch)

 

[Java123???]

Eine relativ einfache Aufgabe wäre, dass du ein Programm schreibst, welches die Fakultät einer Zahl berechnet. Löse diese Aufgabe doch mal iterativ und dann rekursiv. Danach wirst du merken, dass rekursiv manchmal sehr viel besser sein kann.

Mfg

 

[SlaterB]

Fakultät ist zur Übung super, aber den Sinn kann man dort kaum erkennen,
das ist in einer Schleife gerade weg viel besser programmiert,

richtig schick wird Rekursion erst, wenn es viele Verzweigungen gibt, ganz direkt etwa an eine Baumstruktur von Daten gedacht,

wenn man sowas hier zeichnen will,
dann hat man ohne Rekursion beim Nachbau derselben Unmengen an Zwischenzuständen irgendwo abzulegen und in eine Verarbeitungsreihenfolge zu drücken, oder muss mit komplizierter Mathematik die nötigen Linien auf völlig andere Weise finden,
mit Rekursion ist das ganz sauber lokal einfach organisiert, von einem Punkt und einer Richtung aus zwei Linien malen, (fast) nicht mehr zu tun

rekursive Sortieralgorithmen sind gewiss auch ein anschauliches Beispiel

 

[Java123???]

Damit du auch noch ein Beispiel von einer sinnvollen Rekursion bekommst:

public void suche(File f) {
     if(f.isDirectory) {
          suche(f);
     } else {
          //durchsuche Datei
     }
}

 

[Andi_CH]

Damit du auch noch ein Beispiel von einer sinnvollen Rekursion bekommst:

public void suche(File f) {
     if(f.isDirectory) {
          suche(f);
     } else {
          //durchsuche Datei
     }
}

Das ist aber ein sehr schlechtes Beispiel, denn diese Iteration bricht nie ab!

Der iterative Aufruf darf NIE mit demselben Wert durchgeführt werden, mit dem die Funktion aufgerufen wurde!

 

[Java123???]

sry, na klar. Ka wo heut meine Gedanken sind.

Verbessert:

public String suche(File[] f) {
    for (File file : f) {
        if(file.isDirectory()) {
            suche(file.listFiles());
        }else{
            if(file.getName().equals(zuSuchendeDatei)) {
                return file.getAbsolutePath();
            }
        }
    }
    return null;
}

 

[xehpuk]

Der iterative Aufruf darf NIE mit demselben Wert durchgeführt werden, mit dem die Funktion aufgerufen wurde!

Also das hätte ich gern bewiesen. :bae:

 

[Andi_CH]

Also das hätte ich gern bewiesen. :bae:

Willst du mich provozieren oder was ???:L
Ich reagiere nur noch zum Schutz der Anfänger die sich hier tummeln!

Der häufigste Fehler sind wohl Rekursionen die nie abbrechen.
(NEIN ein Stackoverflow gilt NICHT als Rekursionsabbruch)

In dem Fall oben wird f überprüft ob es ein Directory ist.

Wenn ja wird mit f ein rekursiver Aufruf durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

Es wir ein rekursiver Aufruf mit f durchgeführt.

Worauf f überprüft wird ob es ein Directory ist.
(Ja, ist es, das wissen wir ja schon)

............................................................................

 

[SlaterB]

ohne zu provozieren ein Gegenbeispiel, wobei noch zu interpretieren ist, ob der Wert gleich bleibt,
aber wenn man noch separat verwalteten Zustand miteinbezieht, können auch exakt dieselben Parameter-Werte ok sein,
wobei auch das vielleicht schon eine Verletzung der virtuellen Regel ist

public class Test
{
    public static void main(String[] args)
    {
        List<Integer> l = new ArrayList<Integer>();
        l.add(3);
        l.add(2);
        l.add(1);
        System.out.println(sum(l));
    }

    static int sum(List<Integer> l)
    {
        return l.isEmpty() ? 0 : l.remove(0) + sum(l);
    }
}

 

[Java123???]

Es war die Rede vom

Wert

, bei dir ist der Wert nicht mehr gleich, weil du die Liste veränderst bevor du sie wieder als Parameter nutzt.

 

[xehpuk]

Wir sind eben in der objektorientierten Welt, wo es Zustände gibt, die sich nebenher ändern können. Hier also zusätzlich ein Beispiel, in dem sich der "Wert" des Parameters (in diesem Fall nicht mal einer vorhanden) nicht ändert:

public class Recursion {
	private static int count;
	
	public static void main(String[] args) {
		count = 10;
		countDown();
	}
	
	private static void countDown() {
		if (count-- <= 0)
			return;
		System.out.println(count);
		countDown();
	}
}

 

[SlaterB]

wenn man es von der Systemzeit oder dem Zufall anhängig macht, dann gibt es sowas wie 'unveränderten Wert' generell nicht,
nun aber genug genervt

 

[Andi_CH]

ohne zu provozieren ein Gegenbeispiel, wobei noch zu interpretieren ist, ob der Wert gleich bleibt,
aber wenn man noch separat verwalteten Zustand miteinbezieht, können auch exakt dieselben Parameter-Werte ok sein,
wobei auch das vielleicht schon eine Verletzung der virtuellen Regel ist

public class Test
{
    public static void main(String[] args)
    {
        List<Integer> l = new ArrayList<Integer>();
        l.add(3);
        l.add(2);
        l.add(1);
        System.out.println(sum(l));
    }

    static int sum(List<Integer> l)
    {
        return l.isEmpty() ? 0 : l.remove(0) + sum(l);
    }
}

Wobei die :? Notation natürlich wieder eine gar nicht so feine Provoktaion ist...
(Es gibt nur eine einzige Stelle an der diese gut ist - in C++ Konstruktoren beim Initialisieren von Konstanten.)

	static int sum(List<Integer> l) {
		System.out.println(l.toString());
		if (l.isEmpty()) {
			return 0;
		} else {
			// da wir dzuerst l um ein element Verkürzt und dann sum aufgerufen
			// Ich würde mich aber NIE darauf verlassen, dass das auch in der Reihenfolge
			// ausgeführt wird bzw audh in Zukunft nie vertauscht wird
			// (Zu viele schlechte Erfahrungen!)
			return l.remove(0) + sum(l);
		}
	}

Ein sysout am Anfang der Methode ergibt folgenden poutput

[3, 2, 1]
[2, 1]
[1]

Wobei bewiesen ist dass du die Rekursion NICHT mit gleichen Werten aufrufst.

Es muss bewiesen werden, dass der Parameter der rekursiv aufgerufenen Funktion irgend wann das Abbruchkriterium erreicht - die Liste oben wird bei jedem Aufruf verkürzt bzw. beim folgenden Beispiel der Wert immer um 1 verkleinert

public class Fakultaet {

	public static int fakultaet(int i) {
		if (i==1) {
			return 1;
		} else {
			return i * fakultaet(i-1);
		}
	}

	public static void main(String[] args) {
		int wert = 7;
		System.out.println("Fakultät von " + wert + " ist "+ fakultaet(wert));
	}
}

und um weiteren Provokationen aus dem Weg zu gehen - vergesst es, ich lese hier nichts mehr!

 

[Sonecc]

Warum der ein oder andere sich provoziert fühlt ist fraglich...

Im Endeffekt ist es so, dass eine Rekursion so definiert sein muss, dass sie in endlich vielen Schritten endet. Dass dies nicht eintreten kann, wenn sich die Abbruchbedingung nie verändert (wie bei der ersten Version des TOs) ist denke ich offensichtlich. Daher bin ich der Meinung dass die Aussage von Andi auch nicht als verkehrt angesehen werden kann, sondern eigentlich bestätigt werden müsste (was sie unfreiwillig auch mehrfach wurde)

 

[fleckdalm]

Danke euch allen für die vielen erklärungen und Beispiele! Den großteil davon habe ich sogar verstanden;-)
mfg Fleckdalm

 

[muckelzwerg]

Für solche Abbruchkriterien gibt es formale Beweismethoden. (Papier und Stift)
Bei Vergleichen mit Konstanten (i == 1) sind die auch gar nicht so schwer. Im Wesentlichen macht man da eine versteckte, vollständige Induktion.
Man beweist zum einen, dass der Vorgang "verringere den Wert" irgendwann losgelaufen ist" und zum anderen, dass er dann auch "stetig weiter verringert" wird.
Klassisches Bild sind fallende Dominosteine. Fällt ein Stein, muss auch sein Nachfolger fallen.
Und genau DAS ist eine Rekursion. "Stein X ist gefallen, also muss Stein X-1 auch gefallen sein."
Interessanterweise gibt es formale Beweismethoden auch für z.B. iterative Schleifen. Und diese Beweismethoden machen genau das gleiche. Eine kleine Induktion, die im Kern wieder eine Rekursion enthält.
Sooo unwichtig können die Dinger nicht sein.
(Ein bisschen was zu Logik und formalen Sprachen lesen, dann sieht man das sowieso ganz anders. Rekursionen sind nicht bloß kleine Funktionen, die sich selbst aufrufen. Da steckt schon etwas mehr dahinter. ^^)



SlaterB, Du hast da ein Fraktal gezeigt, das vermutlich mit einem L-System erzeugt wurde. Vom mathematischen Aufbau her hat das ganz klar eine "rekursive Form".
Um so etwas darzustellen geht man aber für gewöhnlich iterativ und vorwärtsgerichtet vor.
Hast Du sowas mal rekursiv gemacht, oder gesehen? Würde mich sehr interessieren.

 

[kirax]

Wir sind eben in der objektorientierten Welt, wo es Zustände gibt, die sich nebenher ändern können. Hier also zusätzlich ein Beispiel, in dem sich der "Wert" des Parameters (in diesem Fall nicht mal einer vorhanden) nicht ändert:

public class Recursion {
	private static int count;
	
	public static void main(String[] args) {
		count = 10;
		countDown();
	}
	
	private static void countDown() {
		if (count-- <= 0)
			return;
		System.out.println(count);
		countDown();
	}
}

Streng genommen ändert sich da der Wert einer globalen Variable. Das Programm ist äquivalent zu einem, das count als Parameter verwendet, damit fiele es wieder unter die Kategorie "bricht ab mit geändertem Parameter"...

Beweisen, dass es eine rekursive Funktion, die ohne Parameteränderung terminiert, kann man mit dem Modell von endlichen deterministischen Zustandsautomaten:

Ein Startzustand S mit einer gegebenen Menge Parameter. Mehr Zustände braucht man nicht, da sich nach Def. kein Parameter ändert, also bleibe ich immer im Zustand S, egal welche der (meinetwegen unendlich vielen) Kanten ich von diesem Zustand abwandere. Die Kanten sind allesamt Schlingen, da ich wie gesagt keinen weiteren Zustand habe. Ich bleibe also immer in S und da sich kein Parameter ändert, wandere ich immer wieder über eine Schlinge zurück in S. Einzige Ausnahme: Es gibt keine passende Schlinge. Dann, aber auch nur dann, terminiert die Funktion, aber auch nur direkt nach dem Start. Wer da jetzt von Rekursion sprechen will - naja

Sicher geht das noch formeller, aber dazu hab ich grad keine Lust

"Teile und Herrsche" <- ein Grundsatz für Rekursion. Das Fakultätsbeispiel erfüllt diesen Grundsatz nicht, von daher ist die Frage, ob Rekursion an der Stelle angebracht ist. Unser Prof hat mal zwei Gruppen von Rekursionen unterschieden, die eine "Teile und Herrsche", die andere das Fakultätsbeispiel. Leider hab ich deren Namen vergessen

Noch ein Beispiel: Sortieralgorithmen. Mergesort arbeitet mit wenigen Codezeilen in (echt) O(nlogn) und ist dazu noch relativ leicht verständlich (im Gegensatz z.B. zu Quicksort )

Man muss sich nur überlegen, wie das Problem ist, wenn man es um einen Schritt weiter löst.

Ich sag nur Induktion Deswegen ist Rekursion ja so toll ^^

 

[SlaterB]

SlaterB, Du hast da ein Fraktal gezeigt, das vermutlich mit einem L-System erzeugt wurde. Vom mathematischen Aufbau her hat das ganz klar eine "rekursive Form".
Um so etwas darzustellen geht man aber für gewöhnlich iterativ und vorwärtsgerichtet vor.
Hast Du sowas mal rekursiv gemacht, oder gesehen? Würde mich sehr interessieren.

ich hätte gedacht rekursiv, meine das früher mal so umgesetzt zu haben,
wie es aber 'für gewöhnlich' gemacht wird will ich nicht beschwören

die Frage nach einem aktuellen Beispiel nehme ich als kleine Herausforderung gerne auf:

public class TestGUI  extends JFrame {
    public TestGUI()  {
        JPanel p = new JPanel() {
                protected void paintComponent(Graphics g) {
                    super.paintComponent(g);
                    rec(g, 200, 300, Math.PI, 120);
                }

                private void rec(Graphics g, double x, double y, double direct, int length) {
                    if (length < 1) return;
                    double newX = x + Math.sin(direct) * length;
                    double newY = y + Math.cos(direct) * length;
                    g.drawLine((int)x, (int)y, (int)newX, (int)newY);

                    int newL = length * 3 / 5;
                    rec(g, newX, newY, direct - Math.PI / 4, newL);
                    rec(g, newX, newY, direct + Math.PI / 4, newL);
                }

            };
        add(p);

        setSize(450, 350);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setVisible(true);
    }

    public static void main(String[] args)  {
        new TestGUI();
    }
}

 

[muckelzwerg]

Ja, genau sowas meinte ich. "Eigentlich" macht man das eher nicht.
Wenn Du mit einer Länge von 120 startest, und die jedesmal um 0.6 (=3/5) verringerst, dann machst Du 9 Schritte, bis die Länge unter 1 fällt.
120 * 0.6^9 ~ 1.2
120 * 0.6^10 ~ 0.7
In jedem Schritt erzeugst Du zwei neue Funktionsaufraufe. Das sind dann schon 2^9=512 laufende Funktionen.
Und für solche Fraktale ist das eigentlich noch "winzig".
"Eigentlich" erzeugt man da eine Modulkette, meist aus einfachen Zeichen. Und diese Module werden dann als Stackoperationen interpretiert. (>> Turtlegrafik)
Zum Hinzeichnen weils gut aussieht, ist das aber was ganz anderes.

 

[SlaterB]

aber nicht 512 gleichzeitig laufende Funktionen, beim Stack wird es doch sicher auch 512x Einfügen + Auslesen geben also gleich doppelt so viele Aufrufe?
wobei Swing für derartige Optimierungen wohl nicht geeignet ist, jeder drawString() führt intern bestimmt zig Methodenaufrufe aus, wegen Polymorphie extra aufwendig usw.

wenn schon optimieren, dann vielleicht eine Blüte der unteren 5 Ebenen als Polygon vorberechnen und dieses dann ~32x Zeichnen,
bzw. hier eine Baumhälfte malen und dann spiegeln und ähnliches

 

[Antoras]

In jedem Schritt erzeugst Du zwei neue Funktionsaufraufe. Das sind dann schon 2^9=512 laufende Funktionen.

Die werden nacheinander aufgerufen, es sind hier also nur 9 Rekursionsstufen.

Wenn man viel mit Rekursion arbeiten möchte, sollte man sowieso Tailrekursiv programmieren, wobei man dann noch einen Compiler braucht, der das wegoptimieren kann. Leider kann das weder der Java- noch der JIT-Compiler der JVM. Also sollte man in Java damit eher sparsam umgehen.

 

[muckelzwerg]

Klar, es sind immer nur 9 Funktionen gleichzeitig am existieren.

SlaterB, den Stack verwendest Du, um Turtlegrafik zu zeichnen. Bei Deiner Rekursion hast Du die Generation und das Zeichnen in einem.
Typischerweise werden solche Figuren mit Lindenmayer-Systemen erzeugt. Das sind Termersetzungssysteme, bei denen die Rekursion in den Produktionsregeln steckt.
Trotzdem werden die Ableitungen eigentlich nicht rekursiv erzeugt.
Die Zeichenkette stellt den Zustand zu einer bestimmten Zahl von Ableitungen dar. Es werden sequentiell alle Zeichen (Module) entsprechend der Ersetzungsregeln ausgetauscht, bzw. in einer neuen Zeichenkette zusammengefügt.
Dabei macht man für gewöhnlich nur einen Sprung von einer Generation. Die "eval-Funktion" betrachtet das Zeichen (und evtl. seinen Kontext, also seine benachbarten Zeichen) und erzeugt daraus eine neue Zeichenfolge.
Würde man dort rekursiv arbeiten wollen, dann müsste man nun die eval-Funktion direkt wieder auf die neu entstandene Teilfolge anwenden und ein weiteres mal ersetzen.
Stattdessen ersetzt man aber einmal die komplette Folge sequentiell und bringt sie in die nächste Generation.
Will man noch eine Generation weiter, dann wiederholt man den Vorgang.

 

[Rekursion?]

Jetzt driftet die Diskussion ab in Diskussionen über die Anzahl der Funktionsaufrufe, über die Stackgröße der Funktionsaufrufe, über die interne Umsetzung rekursiver Funktionen, über die Beweisbarkeit der Terminierung rekursiver Funktionen usw.

Jede Methode, die einen Methodenaufruf der gleichen Methode enthält, ist bereit seine rekursive Methode. Dann gibt es auch rekursive Methoden, die sich gegenseitig selbst aufrufen. Das sind ebenfalls rekursiv Methoden.

Wenn Parameter die Abbruchbedingen ausmachen und diese Parameter sich nicht ändern, dann ist die Abbruchbedingung entweder sofort oder nie erfüllt, was zur sofortigen Terminierung oder zu keiner führt. Mit "ändern" ist bei primitiven Typen eine Werteänderung, bei Referenztypen eine Zustandsänderung des Objektes gemeint.