Rekursion: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
(Die Seite wurde neu angelegt: „Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst: * rekursive Methoden * rekursive Datenstrukturen =rekursive Methoden= Rekursive…“) |
|||
| (3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
[[Kategorie:Informatik]] | |||
[[Kategorie:Informatik-Q1]] | |||
[[Kategorie:Informatik-Abitur]] | |||
Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst: | Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst: | ||
* rekursive Methoden | * rekursive Methoden | ||
| Zeile 18: | Zeile 21: | ||
==einfaches Beispiel== | ==einfaches Beispiel== | ||
Die folgende rekursive Methode berechnet n! = 1*2*3*...*n | Die folgende rekursive Methode berechnet n! = 1*2*3*...*n | ||
<code> | <code> | ||
// rekursive Methode mit Parameter | |||
// 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 | |||
int ergebnis = n * zahl; | int ergebnis = n * zahl; | ||
return ergebnis; | return ergebnis; | ||
} | } | ||
</code> | </code> | ||
==Wo kommt das vor?== | ==Wo kommt das noch vor?== | ||
rekursive Methoden braucht man bei folgenden Themen: | rekursive Methoden braucht man bei folgenden Themen: | ||
* [ | * [[Binärbaum_(Methoden)#Rekursion|Rekursion bei Binärbäumen]]<br/>Unter anderem werden Inorder- Preorder und Post-Order Traversierungen von Binärbäumen rekursiv programmiert. | ||
* [[Quicksort]] | |||
* [[Graph#Tiefendurchlauf|Tiefendurchlauf bei Graphen]] | |||
=rekursive Datenstrukturen= | |||
[[Binärbaum|Binärbäume]] sind als Datenstruktur rekursiv definiert. | |||
Denn jeder Binärbaum enthält seinerseits zwei Binärbäume (den rechten und den linken). | |||
Aktuelle Version vom 23. Januar 2022, 18:13 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).