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…“) |
|||
| 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 | ||
| Zeile 28: | Zeile 35: | ||
// 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; | ||
| Zeile 33: | Zeile 42: | ||
</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). | |||
Version vom 15. Februar 2021, 15:02 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).