Rekursion ist kürzer
Von: matroid
Datum: Di. 14. August 2001 21:25:02
Thema: Mathematik
\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Um Rekursion zu verstehen, muß man zunächst Rekursion verstehen.

Einen "Leitfaden Rekursives Programmieren" gibt es bei EducETH.

Eine kurze Beschreibung des Wesens der Rekursion, anhand eines ernsten und eines nicht so ernsten Beispiels unter "mehr..." Wie trinkt ein Mathematiker eine Flasche Bier?

Algorithmus "Bier trinken"

  1. Fall: Das Bier ist im Keller.
    Der Mathematiker geht in den Keller, nimmt eine Flasche Bier, trägt sie in die Wohnung, öffnet die Flasche mit einem Flaschenöffner, nimmt ein Glas aus dem Schrank, gießt Bier aus der geöffneten Flasche in das Glas und trinkt das Bier aus dem Glas.
  2. Fall: Das Bier ist im Kühlschrank.
    Der Mathematiker trägt das Bier in den Keller, dann weiter mit Fall 1.
Wie man sieht, ergibt Rekursion die kürzere Beschreibung. Darauf kommt es an! Eine Wiederholung der Details aus Fall 1 auch im Fall 2 machte die Beschreibung nur unübersichtlicher. Der Algorithmus "Bier trinken" ist so wie oben optimal formuliert. Außerdem wird sich jede Verbesserung oder Ergänzung der Beschreibung des Falles 1 auch sogleich positiv auf Fall 2 auswirken. Auch das ist gewollt.

Mathematiker denken häufig rekursiv. Die Vollständige Induktion ist die rekursive Beweismethode der Mathematik. Dabei wird ja ständig der Fall n+1 wird auf den Fall n zurückgeführt.

In der gesamten Diskreten Mathematik spielen rekursive Algorithmen bei der Lösung von Optimierungsproblemen eine wesentliche Rolle.

Ein einfaches Beispiel aus der Kombinatorik soll den Unterschied (den Nutzen!) zeigen.
[Wenn das nach dem überzeugenen Bier-Beispiel noch erforderlich sein sollte. ;)]

k-Kombinationen von n Elementen

Die Anzahl der Möglichkeiten, k Kugeln aus n Kugeln ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge zu ziehen, ist n über k.

Diese Anzahlformel ist bekannt. Eine elementare Darstellung dazu gibt es bei Urnenmodelle.

Wie kann man nun aber alle Möglichkeiten aufschreiben? Bzw. wie sieht ein Algorithmus aus, der systematisch alle Möglichkeiten erzeugt?

Der naive Ansatz:

sub kombi() 
i = -1

for a = 1 To 6
for b = a + 1 To 7
for c = b + 1 To 8
for d = c + 1 To 9
for e = d + 1 To 10
For f = e + 1 To 11
i = i + 1
kombination = Str(a) + Str(b) + Str(c) + Str(d) + Str(e) + Str(f)
// i-te Kombination ausgeben
Next f
Next e
Next d
Next c
Next b
Next a
End Sub
Nachteil dieses Schleifenverfahrens: man muß das Programm ändern, wenn sich die Anzahl der Kugeln (n) oder die Länge der Kombination (k) ändert.
Außerdem ist die Anzahl der Rechenoperationen nicht leicht zu bestimmen.

Das folgende rekursive Verfahren ist universell für alle n und k verwendbar.
Die Idee dabei ist: Eine Kombination von k aus n Elementen kann zurückgeführt werden auf zwei Fälle:

  1. Fall: Die Kombination enthält das n-te Element.
  2. Fall: Die Kombination enthält das n-te Element nicht.

Algorithmus zur Aufzählung alle Kombinationen von k aus n Elementen [A(n,k)]

  1. Starte mit nichts.
  2. Wenn k=0, dann Ende.
  3. Zur Erzeugung aller k-Kombinationen von n, die n enthalten, merke n und rufe diesen Algorithmus erneut zur Bestimmung der k-1 elementigen Kombinationen aus n-1 Elementen auf [also A(n-1,k-1)].
    Jede k-1-Kombinationen von n-1 wird um das gemerkte n ergänzt und ergibt eine k-Kombination von n Elementen.
  4. Wenn k noch kleiner als n ist, dann rufe zur Erzeugung aller k-Kombinationen von n, die n nicht enthalten, diesen Algorithmus zur Bestimmung aller k-Kombinationen von n-1 Elementen erneut auf [also A(n-1,k)].
    Jede k-Kombination von n-1 Elementen ist eine k Kombination von n Elementen, die n nicht enthält.
Dieser Algorithmus hier formuliert in PHP:
   $kombination = $array(); 

function kombi($n,$kk)
{
global $kombination;

// Vervollständige Kombinationen ohne $n
if($n>$kk)
kombi($n-1,$kk);

// Bilde Kombinationen mit $n
if($n>=$kk--)
{
// Merke $n
$kombination[$kk] = $n;

if($kk>0)
kombi($n-1,$kk);
else
print_kombi();
}
}
Unter n_ueber_k kann man es ausprobieren.
 


Dieser Artikel kommt von Matroids Matheplanet
https://matheplanet.de

Die Url für diesen Artikel ist:
https://matheplanet.de/default3.html?article=103