Mathematik: Rekursion ist kürzer
Released by matroid on Di. 14. August 2001 21:25:02 [Statistics]
Written by matroid - 5029 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\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.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Web-Review :: Rekursion :: Programmierung :: Informatik :
Rekursion ist kürzer [von matroid]  
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 ...
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5029
 
Aufrufstatistik des Artikels
Insgesamt 769 externe Seitenaufrufe zwischen 2012.01 und 2021.11 [Anzeigen]
DomainAnzahlProz
https://google.com263.4%3.4 %
http://google.de60879.1%79.1 %
https://google.de10213.3%13.3 %
https://google.ru101.3%1.3 %
http://google.it91.2%1.2 %
https://www.startpage.com40.5%0.5 %
http://google.com10.1%0.1 %
http://search.sweetim.com10.1%0.1 %
http://www.die-startseite.net20.3%0.3 %
http://www.search.ask.com10.1%0.1 %
http://www.claro-search.com10.1%0.1 %
http://suche.t-online.de30.4%0.4 %
http://google.nl10.1%0.1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 758 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (143x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (94x)https://google.de/
201901-06 (45x)http://google.de/search?q=algorithmus kombinationen
201204-10 (45x)http://google.de/url?sa=t&rct=j&q=rekursive kombination
201201-01 (42x)http://google.de/url?sa=t&rct=j&q=ziehen von k elementen aus n rekursiv
201212-12 (31x)http://google.de/url?sa=t&rct=j&q=kombinationen algorithmus
2012-2015 (29x)http://google.de/url?sa=t&rct=j&q=kombinationen ohne wiederholung algorithmus
201205-05 (27x)http://google.de/url?sa=t&rct=j&q=matheplanet matroid rekursion n k
201202-02 (27x)http://google.de/url?sa=t&rct=j&q=ziehen ohne zurücklegen ohne reihenfolge...
2020-2021 (25x)https://google.com/
201308-12 (23x)http://google.de/url?sa=t&rct=j&q=algorithmus kombinationen ohne wiederholung
201203-03 (20x)http://google.de/url?sa=t&rct=j&q=sinus rekursiv integral
201208-08 (19x)http://google.de/url?sa=t&rct=j&q=ziehen ohne zurücklegen alle kombination...
201206-06 (18x)http://google.de/url?sa=t&rct=j&q=kombinationen rekursiv berechnen
201301-01 (17x)http://google.de/url?sa=t&rct=j&q=kombinationen ohne wiederholung in schleife
201211-11 (17x)http://google.de/url?sa=t&rct=j&q=rekursives denken mathematik
201207-07 (16x)http://google.de/url?sa=t&rct=j&q=urne "ziehen ohne zurã¼cklegen"...
201303-03 (16x)http://google.de/url?sa=t&rct=j&q=kombinationen rekursiv
201302-02 (16x)http://google.de/url?sa=t&rct=j&q=rekursion alle möglichkeiten
201307-07 (14x)http://google.de/url?sa=t&rct=j&q=rekursion kombiniere python
201305-05 (14x)http://google.de/url?sa=t&rct=j&q=variation rekursiv
201304-04 (11x)http://google.de/url?sa=t&rct=j&q=variation berechnen rekursiv
202012-12 (10x)https://google.ru/
201405-05 (9x)http://google.it/url?sa=t&rct=j&q=
202010-10 (8x)https://google.de
201306-06 (8x)http://google.de/url?sa=t&rct=j&q=stichprobenvarianz rekursionsformel
201411-11 (5x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBwQFjAA
201402-02 (5x)http://google.de/url?sa=t&rct=j&q=rekursion anzahl der möglichkeiten
2020-2021 (4x)https://www.startpage.com/

[Top of page]

"Mathematik: Rekursion ist kürzer" | 1 Comment
The authors of the comments are responsible for the content.

Re: Rekursion ist kürzer
von: FriedrichLaher am: Mo. 26. November 2001 11:25:09
\(\begingroup\)Nun ja, fuer das Durststillen, kann der Mathematiker im Fall 2 ja einen Physiker bitten, ihm bei einem Gedankenexperiment zu Helfen, das den Fall auf Fall 1 zurueckfuehrt, ohne physisch zu agieren.

Im ernst wird es wohl noetigenfalls Werkzeuge geben die einen recursiv formulierten Algorithmus zu serialisieren versuchen - in Schleifenform oder wenn moeglich auch "entrollt" (wie 1te KombiVariante) und die guenstigste Loesung suchen.

Insbesondere wenn viele grosse Parameter immer wieder mitgeschleppt werden muessen, kann das schnell zu viel Speicher kosten, und das Hinundher kostet vielleicht auch mehr Zeit als eine Iteration.
Und bevor es ans Codieren geht, sollten immer erst die mathematischen Moeglichkeiten ausgeschoepft werden wenn das Programm mehr als 1mal laufen soll.
Es ist Unsinn, wenn Programmieranfaenger
immer
wieder z.B. 1+2+...+n
als
Schleife oder gar recursiv programmieren sollen!
Wenn
auch die Zwischensummen benoetigt werden
ist
natuerlich eine Schleife noetig wenn n variabel
sein soll,
nicht
noetig ist aber fuer 1+2k+3k+...nk
zu
Potenzieren - es ist ja fuer ganze k > 0 eine Arithmetische Reihe (k+1)ter Ordnung!
U.s.w. .... \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]