A2 Rekursion

Autor: Harald Pierhöfer

Gewisse Probleme lassen sich vereinfachen, wenn man sie in kleinere Stücke zerlegt und diese einzeln löst. Ruft sich eine Funktion selbst (mehrfach) auf, so entsteht ein weit (verzweigter) Abarbeitungsbaum, der einerseits sehr mächtig, andererseits aber auch zeit- und speicherintensiv wird. Die Beschreibung dieses Baums ist aber einfach und erlaubt einen kurzen Algorithmus.

Von gross zu klein (top-down).

• Ich kann das Grundmuster einer rekursiven Funktion (Methode, Prozedur) angeben.
• Ich kann einen rekursiven Algorithmus skizzieren und in einer ausgewählten Programmiersprache umsetzen.
• Ich kann den zeitlichen Aufwand und den Bedarf an Arbeitsspeicher einer Rekursion qualitativ beschreiben.
• Ich kenne den Begriff des Stacks und kann beschreiben, wie er in der rekursiven Programmierung auf- und abgebaut wird.

• Quicksort, Mergesort
• Fraktale (Hilbertkurve, Peanokurve, Kochsche Schneeflocke,…)
• Türme von Hanoi

Weitere Beispiele: Siehe p3: Closures: Methoden, Prozeduren und Funktionen — Philipp Gressly Freimann 2009/03/09 12:04

• Voraussetzung: P3 Subroutinen (Functions, …) — Philipp Gressly Freimann 2009/03/16 14:01
• 

• Andrea Alder, Marco Bettinaglio, Werner Hartmann, Patrick Leoni, Markus Meier, Florian Schlotke. Leitprogramm Rekursives Programmieren. http://www.swisseduc.ch/informatik/programmiersprachen/rekursion/
• Rekursion

• Eleganz/Speichergrenzen vs. pragmatische Unschönheit — Paul Miotti 2008/06/24
• map-reduce von Google. Ein mögliches aktuelles Thema zum Einstieg ins Thema der Paralellität — Paul Miotti 2008/10/26
• Eine Fertigkeit wäre wohl auch das Abbrechen der Rekursion. Für Mittelschüler wohl nicht so schwierig; Applikationsenwickler-Lehrlinge können das in der Regel nicht. Doch wahrscheinlich ist das auch eine implizite Fähigkeit, denn jeder (auch ich) laufen beim ersten Mal in diese Falle: fibonacci(n) :== fibonacci(n-1) + fibonacci(n-2) … und schon ist er da, der Stack overflow — Philipp Gressly Freimann 2009/01/18 23:13