Rekursion: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
| Zeile 24: | Zeile 24: | ||
<code> | <code> | ||
// rekursive Methode mit Parameter | // rekursive Methode mit Parameter | ||
// n wird bei jedem Aufruf eins runtergezählt! | // n wird bei jedem Aufruf eins runtergezählt! | ||
public int fakultaet(int n) { | public int fakultaet(int n) { | ||
//Abbruchbedingung | '''//Abbruchbedingung''' | ||
if (n <= 1) { | if (n <= 1) { | ||
return 1; | return 1; | ||
} | } | ||
// rekursiver Aufruf fuer n-1 | '''// rekursiver Aufruf fuer n-1''' | ||
int zahl = fakualtaet(n-1); | int zahl = '''fakualtaet(n-1)'''; | ||
// Sachlogik | // Sachlogik | ||
int ergebnis = n * zahl; | int ergebnis = n * zahl; | ||
Version vom 17. Februar 2021, 08:03 Uhr
Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst:
- rekursive Methoden
- rekursive Datenstrukturen
rekursive Methoden
Rekursive Methoden sind Methoden, die sich selber aufrufen, um z.B. eine Berechnug auszuführen.
Wichtig sind dabei folgende Elemente:
- ein Parameter, in dem man je nach Rekursionsstufe einen anderen Wert übergeben kann.
- eine Abbruchbedingung für das Rekursionsende - sonst läuft die Methode ewig weiter.
- ein (oder mehrere) rekursive Aufrufe.
einfaches Beispiel
Die folgende rekursive Methode berechnet n! = 1*2*3*...*n
// rekursive Methode mit Parameter
// n wird bei jedem Aufruf eins runtergezählt!
public int fakultaet(int n) {
//Abbruchbedingung
if (n <= 1) {
return 1;
}
// rekursiver Aufruf fuer n-1
int zahl = fakualtaet(n-1);
// Sachlogik
int ergebnis = n * zahl;
return ergebnis;
}
Wo kommt das noch vor?
rekursive Methoden braucht man bei folgenden Themen:
- Rekursion bei Binärbäumen
Unter anderem werden Inorder- Preorder und Post-Order Traversierungen von Binärbäumen rekursiv programmiert. - Quicksort
rekursive Datenstrukturen
Binärbäume sind als Datenstruktur rekursiv definiert. Denn jeder Binärbaum enthält seinerseits zwei Binärbäume (den rechten und den linken).