Mathematik: Rekursive Funktionen
Released by matroid on Do. 29. November 2001 20:53:05 [Statistics]
Written by matroid - 10032 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}\) Eine rekursive Definition einer Funktion besteht aus einer Vorschrift, wie für jedes Element des Wertebereichs der Wert f(x) über früher definierte Funktionen und Werte von f für kleinere Argumente errechnet werden kann.
Rekursion
[Die Vorgehensweise bei der Rekursion kann man sich wie das Durchlaufen eines Baumes von einem Punkt in der Krone zur Wurzel vorstellen. Für jeden Punkt im Baum ist nur bekannt, wie man von dort näher zur Wurzel kommt. An keinem Punkt ist bereits der ganze Weg bekannt.]

Beispiel einer rekursiven Definition - Die Fibonacci-Folge

f: IN -> IN definiert durch
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) [für n>1]

Wie berechnet man damit den nächsten Wert?
Es ist f(2) = f(2-1) + f(2-2) = f(1) + f(0) = 2.

Für diese Funktion ist es offensichtlich, daß sie wohldefiniert ist. Man nennt eine rekursiv definierte Funktion wohldefiniert wenn die Berechnung für jeden Wert des Wertebereichs nach endlich vielen Schritten stoppt und das Ergebnis keine Widersprüche aufweist.
Eine Grundanforderung an rekursive Defintionen besteht darin, daß die Berechnung für jeden Wert des Wertebereichs nur "vorher" berechnete Werte erfordert oder auf vorher berechenbare Werte zurückgeführt werden kann.
Einige weitere einfache Beispiele.

Beispiel: nicht wohldefiniert

f(n) = f(n+1) [n>=0]
Es kann damit kein einziger Wert ausgerechnet werden, weil die Berechnung nicht auf "vorher" berechnete Werte zurückzuführen ist. Das liegt nicht daran, daß auf der rechten Seite der höhere n-Wert steht. Eine Gleichung kann man immer in beiden Richtungen lesen. Aber selbst wenn man die Rekursionsvorschrift umdreht, nämlich f(n+1) = f(n), hilft das nicht weiter. Man weiß dann nur, daß f(1) = f(0) ist - aber was ist f(0)? Das ist kein vorher berechenbarer Wert. Dieser Rekursionsvorschrift fehlt schlicht die Anfangsbedingung.

Beispiel: wohldefinierte Funktion

f(0) = 1
f(n) = f(n+1)-1 [n ungerade, n>0]
f(n) = f(n-2) [n geradem n>0]

Mit dieser Vorschrift rechnet man aus:
f(2) = f(0) = 1
f(1) = f(2) - 1 = 1 - 1 = 0.
f(4) = f(2) = f(0) = 1
f(3) = f(4) - 1 = 1 - 1 = 0
f(6) = f(4) = f(2) = f(0) = 1
f(5) = f(6) - 1 = 1 - 1 = 0

Dieses Beispiel verdeutlicht, wie man das 'vorher berechnet oder berechenbar' verstehen muß. Es genügt für die Wohldefiniertheit, daß es eine geeignete Reihenfolge für die Berechnung gibt, die man findet, indem man einfach der Rekursionsvorschrift folgt. Im Beispiel hindert uns nichts daran, f(2) vor f(1) auszurechnen, und wir haben damit alles, was man braucht, um die Berechnung weiterer Folgenwerte fortzusetzen.

In diesem Sinne ist f(2) ein "vorher" berechneter Funktionswert. Die Berechnung endet immer nach endlich vielen Schritten.
Und es entstehen keine Widersprüche. Selbst wenn wir die Rekursionsvorschrift für ungerade n anders auflösen, nämlich f(n+1) = f(n) + 1 [n ungerade]. Danach ist f(4) = f(3) + 1 und die errechneten Werte für f(3) und f(4) erfüllen auch das.

Anscheinend wohldefiniert ist die Hofstadter-Folge Deren Rekursionsvorschrift lautet:

Q(1) = Q(2) = 1
Q(n) = Q( n - Q(n-1) ) + Q( n - Q(n-2) )
Ich schreibe 'anscheinend', weil bisher keine Grenze für die Berechenbarkeit weiterer Werte gefunden wurde. Aber kann man das formal beweisen? Vielleicht hat es ja schon jemand geschafft, aber da ich das nicht weiß, will ich nicht zu viel behaupten.

Beispiel: Widerspruch bei nicht wohldefinierter Rekursionsvorschrift

f(1) = 0
f(n) = 1 + f(n/2) [für gerade n]
f(n) = f(3n-1) [für ungerade n]

Wir erhalten:
f(1) = 0
f(2) = 1 + f(1) = 1
f(3) = f(8) = 1 + f(4) = 1 + 1 + f(2) = 3
f(4) = 1 + f(2) = 2
f(5) = f(14) = 1 + f(7) = 1 + f(20) = 1 + ( 1 + f(10) ) = 3 + f(5)

Gesehen? Da steht: f(5) = 3 + f(5)!
Wenn f(5) definiert wäre, dann wäre das ein Widerspruch. Also kann f(5) gar nicht definiert sein. Und damit ist die rekursive Funktion nicht wohldefiniert.

Kurioses Beispiel: die sogenannte 91-er Funktion

M(n) = n - 10 [für n>100]
M(n) = M(M(n+11)) [für n<=100]

[Das M als Funktionssymbol steht für McCarthy]

Die Definition verwendet geschachtelte rekursive Funktionsanwendungen [Ok, die Hofstadter-Folge auch].

Die 91-Funktion ist tatsächlich für alle positiven ganzen Zahlen definiert, und sie liefert immer den Wert 91 - und das gibt der Funktion ihren Namen.

Siehe auch en.wikipedia.org/wiki/McCarthy_91_function#Proof

Trennlinie
[Mathe ist ein Spiel für mindestens eine Person]

\(\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:
: Analysis :: Folgen und Reihen :: Leicht verständlich :: Schüler aufwärts :: Fibonacci-Zahlen :: Mathematik :: Rekursion :
Rekursive Funktionen [von matroid]  
Eine rekursive Definition einer Funktion besteht aus einer Vorschrift, wie für jedes Element des Wertebereichs der Wert f(x) über früher definierte Funktionen und Werte von f für kleinere Argumente errechnet werden kann. [Die Vorgehensweise bei der Rekursion kann man sich wie das Durchlaufen e
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 10032
 
Aufrufstatistik des Artikels
Insgesamt 1512 externe Seitenaufrufe zwischen 2012.01 und 2022.01 [Anzeigen]
DomainAnzahlProz
https://google.com302%2 %
https://www.ecosia.org191.3%1.3 %
https://google.de44129.2%29.2 %
https://www.bing.com362.4%2.4 %
https://duckduckgo.com322.1%2.1 %
https://www.startpage.com30.2%0.2 %
http://google.de87357.7%57.7 %
https://google.lu281.9%1.9 %
https://google.fr130.9%0.9 %
http://google.ch50.3%0.3 %
http://r.duckduckgo.com20.1%0.1 %
http://www.bing.com110.7%0.7 %
http://www.benefind.de20.1%0.1 %
http://google.com20.1%0.1 %
http://www.delta-search.com20.1%0.1 %
http://172.16.0.5:191010.1%0.1 %
http://de.yhs4.search.yahoo.com10.1%0.1 %
https://swisscows.com10.1%0.1 %
https://startpage.com10.1%0.1 %
http://search.conduit.com10.1%0.1 %
http://search.softonic.com20.1%0.1 %
http://de.search.yahoo.com10.1%0.1 %
http://search.iminent.com10.1%0.1 %
http://www.surfcanyon.com10.1%0.1 %
http://images.google.de10.1%0.1 %
http://suche.t-online.de10.1%0.1 %
http://int.search.tb.ask.com10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 38 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.01.01-2022.01.20 (26x)https://google.com/
2022.01.20 08:44https://www.ecosia.org/
2022.01.10-2022.01.20 (4x)https://google.de
2022.01.06-2022.01.19 (2x)https://www.bing.com/
2022.01.10-2022.01.18 (2x)https://duckduckgo.com/
2022.01.09-2022.01.17 (3x)https://google.de/

Häufige Aufrufer in früheren Monaten
Insgesamt 1429 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (385x)https://google.de/
2013-2020 (268x)http://google.de/url?sa=t&rct=j&q=
2012-2015 (158x)http://google.de/url?sa=t&rct=j&q=rekursive funktion mathematik
2012-2013 (90x)http://google.de/url?sa=t&rct=j&q=rekursive funktionen mathe
201211-11 (61x)http://google.de/url?sa=t&rct=j&q=was bedeutet eine funktion ist rekursiv mat...
2020-2021 (49x)https://google.de
2012-2013 (44x)http://google.de/url?sa=t&rct=j&q=rekursive Mathematik
2012-2013 (39x)http://google.de/url?sa=t&rct=j&q=rekursive mathematische funktion
201411-11 (36x)http://google.de/url?sa=t&source=web&cd=4&ved=0CCcQFjAD
2020-2021 (29x)https://www.bing.com/
2020-2021 (28x)https://duckduckgo.com/
202105-05 (28x)https://google.lu
201302-02 (23x)http://google.de/url?sa=t&rct=j&q=rekursiven funktionen mathematisch
201205-05 (22x)http://google.de/url?sa=t&source=web&cd=5&ved=0CGYQFjAE
201306-06 (20x)http://google.de/url?sa=t&source=web&cd=1&ved=0CA4QFjAA
2020-2021 (17x)https://www.ecosia.org/
201210-10 (16x)http://google.de/url?sa=t&rct=j&q=rekursiv definierte funktionen
201208-08 (14x)http://google.de/url?sa=t&rct=j&q=rekursive mathematische funktionen
201402-02 (14x)http://google.de/url?sa=t&rct=j&q=rekursive formel mathe e funktion beispiel
202107-07 (13x)https://google.fr
201405-05 (12x)http://google.de/url?sa=t&source=web&cd=3&ved=0CDIQFjAC
201407-07 (10x)http://google.de/url?sa=t&source=web&cd=3&ved=0CCAQFjAC
201304-04 (10x)http://google.de/url?sa=t&rct=j&q=rekursiv definierte funktion beispiele
201204-04 (8x)http://google.de/url?sa=t&rct=j&q=rekursivität und mathematik
201511-11 (7x)http://google.de/url?sa=t&source=web&cd=8&rct=j&q=rekursion zeigen mathe
2016-2018 (7x)http://google.de/
201703-03 (6x)http://google.de/search?site=webhp&ei=lvTGWLT8DIeTa7mPp8AN&q=rekursiv mathe b...
201308-08 (6x)http://google.de/url?sa=t&rct=j&q=mathematik rekursive funktion
2016-2017 (5x)http://google.ch/url?sa=t&rct=j&q=
202108-08 (4x)https://google.com/

[Top of page]

"Mathematik: Rekursive Funktionen" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 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]