Rekursion - Wofür und womit?

Ich soll in Informatik ein Referat über Rekursion halten und finde nichts über die Anwendungsgebiete. Es geht nur um mathematische Probleme wie das Potenzieren, Fibonacci oder Fakultäten, aber benutzt man die Rekursion wirklich nur da oder auch woanders? Und zweitens: Mit welchen Programmen bzw Anwendungen kann ich Rekursionen ausführen? Danke schon Mal für eine schnelle Antwort!

Answer 1

[Sasatux]

Hallo,

Fibonacci ist an sich keine "richtige" Rekursion, sondern eine Endlosschleife, da es keine Abbruchbedingung gibt. Natürlich ist das was anderes, wenn du einen maximalen Index vorgibst. Es wäre Haarspalterei, wenn man sagen würde, dass richtige rekursive Funktionen in sich die Abbruchbedingung beinhalten.

Als simples(wenn auch mehr als "Proof of Concept") Beispiel kann man einen optimierten Bubble-Sort rekursiv erstellen.

Auf mathematische Probleme ist es sicherlich nicht beschränkt. Beispielsweise kannst du Lexer mit rekursiven Aufrufen erstellen.

Je nach Anwendungsfall ist es möglich, dass das gleiche Ergebnis durch Iterationen erreicht werden kann. Doch auch das ist nicht pauschal zu sagen, da es von vielen Dingen abhängig ist.

In Javascript z.B. kann eine falsche Umsetzung sehr schnell zum Ende der Ausführung führen, da die Kette der Aufrufe auf dem Stack abgelegt werden in der Annahme, dass der nächste Aufruf ein Ergebnis zurück liefert. Wenn dann noch lokale Variablen angelegt werden, dann ist der Speicher sehr schnell voll. Das ist aber von Sprache zu Sprache unterschiedlich und es gibt häufig auch unterschiedliche Arten dies zu steuern.

Rekursion kann ein nützliches Werkzeug sein, aber wenn du nicht verstehst, wie ein Programm im Hintergrund arbeitet oder Besonderheiten der verwendeten Sprache kennst, dann wird es zu Fehlern kommen.

Es mag Programme für so etwas geben(Such mal nach Mandelbrot, Terrain Generator), doch normalerweise ist dies für die Programmierung relevant. Im Falle von der Generierung von z.B. Gebirgen hast du ein sehr konkretes und oft verwendetes Anwendungsgebiet. Prüfsummen(MD5) können rekursiv berechnet werden. Verschlüsselungen. Wobei die Rekursion da nicht die Methode sondern lediglich eine mögliche Art repräsentiert. Sehr oft ist eine Optimierung sinnvoll.

Als sehr (unsinniges) Beispiel kannst du dir einen Algorithmus zum Dividieren von Zahlen überlegen. Also, so wie man es damals in der Schule "zu Fuß" gelernt hat. Das ist - wie ich finde - ein sehr anschauliches Beispiel.

Habe grade mal gesucht und ein Beispiel in einem OpenBook dafür gefunden:

http://openbook.galileocomputing.de/c_von_a_bis_z/009_c_funktionen_020.htm#mj8167bc0895284c09be3f098a49eb1f01

Comments

[Galdur]

Fibonacci ist an sich keine "richtige" Rekursion, sondern eine Endlosschleife, da es keine Abbruchbedingung gibt.

Die Fibonacci-Folge ist eine rekursive Berechnung "wie aus dem Bilderbuch". Sie definiert sich nämlich im mathematischen Sinne schon rekursiv:

Fib(x) = Fib(x-1) + Fib(x-2), wobei Fib(0) = Fib(1) = 1.

Und das alleine reicht aus. Sobald sich eine Funktion in ihrer Definition selbst aufruft, spricht man von Rekursion. Somit ist die Fibonacci-Funktion absolut eine "richtige" Rekursion ;)

Answer 2

[Ennte]

Hallo,

schau dir für Anwendungen doch mal die Türme von Hanoi an. Ansonsten gibt es gerade beim Programmieren etliche Anwendungen von Rekursion. Aber auch in anderen Gebieten die mit Mathematik zu tun haben ist Rekursion ein oft gesehenes Phänomen, allerdings ist sie Manuell gerne mit sehr viel Arbeit verbunden, die man meist lieber dem Rechner überlässt. Ein Beispiel aus der Physik wären zum Beispiel die Clebsch-Gordan-Koeffizienten, mit denen ich mich gerade rumschlagen darf ;)

mfg,
Ennte

Answer 3

[MoMaMa]

Verkettete Listen sind ein super Beispiel dafür.

Es geht eigentlich mit jeder Programmiersprache die Funktionen unterstützt, du beispielsweise genau jetzt, hier, auf Gutefrage.net auf F12 (oder in Firefox Strg+Shift+K) drücken, zum Tab "Konsole" gehen und da folgendes einfügen:

function fibo(n) {
    if (n > 2) return fibo(n-1) + fibo(n-2);
    else return 1;
}
fibo(6);

Und bekommst als Antwort die 6. Fibonacci-Zahl ;)

Auch nett: https://www.google.de/search?q=rekursion bei "Meinten Sie" ;)

Comments

[MoMaMa]

Oder sowas hier: http://www-math.upb.de/~mathkit/Inhalte/Folgen/data/manifest25/schachbrett_reiskoerner.html

Eignet sich ganz gut als Beispiel, auch wenn man das einfacher mit 2², 2³, ... berechnen kann...

[Ennte]

bei mir öffnen sich weder auf F12 noch auf Strg+Shift+K irgendwelche Konsolen (oder Fenster bei denen Konsole eine Option ist) :(

[MoMaMa]

@Ennte

Welchen Browser hast du? Internet Explorer & Chrome können das, Firefox mit S+S+K, wenn du Opera hast Strg+Shift+I

[Ennte]

@MoMaMa

Opera, vielen Dank! Das muss die nächsten Tage mal genauer unter die Lupe genommen werden... welche Sprache läuft denn in der Konsole?

[MoMaMa]

@Ennte

Javascript. Da kommen auch alle Fehler auf allen Webseiten an wenn sich wer verprogrammiert hat oder was gelöscht hat was man noch braucht (das sind hier ein paar Dateien auf gf.net) ;)

[Ennte]

@MoMaMa

alles klar, vielen Dank :)

Answer 4

[Machtnix53]

Eine bedeutende Rolle spielen Rekursionen beim Parsen bzw Interpretieren von Rechenausdrücken oder Programmanweisungen mit Klammern. Wenn eine öffnende Klammer kommt, wird der String bis zur schließenden Klammer von derselben Funktion ausgewertet, die auch für den gesamten Ausdruck verwendet wird. Das Ergebnis des Klammerausdrucks wird dann in dem übergepordneten Ausdruck statt dem Klammerausdruck eingesetzt.

Löst man solche Aufgaben im Kopf, setzt man dieselbe rekursive Strategie ein.