Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start [12.01.2022 21:12] – sbel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start [24.01.2024 11:37] (aktuell) – [Fallunterscheidung ist unbedingt notwendig] Marco Kuemmel
@@ Zeile 19: / Zeile 19: @@
 Bei der Betrachtung des Pseudocodes fällt auf, dass sich die Funktion ''suche_schlüssel'' selbst aufruft -- das ist der Ausdruck im Code des Denkprinzips "das was wir mit jeder Schachtel machen" von oben.
+<WRAP center round tip 60%>
+Wenn eine Funktion sich selbst aufruft spricht man von **Rekursion**.
+</WRAP>
+//Ein Wort zu Eleganz und Performanz:// Die rekursive Formulierung eines Algorithmus ist oft klarer als die iterative - sie bietet aber keine Performancevorteile -- oft sind iterative Formulierungen sogar schneller.
+<blockquote>
+Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!
+</blockquote>
+(Leigh Caldwell, http://stackoverflow.com/a/72694/139117)
+===== Fallunterscheidung ist unbedingt notwendig =====
+Die Funktion ruft sich aber nicht bedingungslos selbst auf, sondern nur dann, wenn eine Schachtel (und kein Schlüssel) gefunden wird. Wenn man diese Fallunterscheidung weglässt, erzeugt man eine "rekursive Endlosschleife": Die Funktion ruft sich bedingungslos immer wieder selbst auf, das Programm kommt zu keinem Ende.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) Experiment: Countdown ===
+Implementiere eine Methode, die einen Countdown ausgibt:
+<code>
+..... 3 ..... 2 ..... 1 ..... 0
+</code>
+**(A)** Zunächst iterativ, z.B. mit einer for-Schleife, in Java: ''public void countdown_iterativ (int start)''. Teste den Code - funktioniert dein Countdown?
+**(B)** Dann rekursiv anhand des folgenden Pseudocodes:
+<code>
+countdown_rekursiv(int i):
+  print(i + " .... ")
+  countdown_rekursiv(i-1)
+</code>
+  * Teste den Code. Was beobachtest du?
+  * Skizziere eine Programmablaufdiagramm für die rekursive Methode.
+  * Erläutere, was das Problem ist.
+<WRAP center round important 80%>
+Jede rekursive Funktion benötigt eine Fallunterscheidung in zwei Fälle:
+  * **Rekursionsfall**: Im Rekursionsfall ruft sich die Funktion selbst auf
+  * **Basisfall**: Im Basisfall ruft sich die Funktion nicht selbst auf, die Rekursion wird mit einem ''return''-Statement beendet.
+</WRAP>
+**(C)** Passe deine rekursive Methode anhand des folgenden Pseudocodes mit einer Fallunterscheidung an:
+<code>
+countdown_rekursiv(int i):
+  wenn i<=0:
+    return
+  sonst:
+    print(i + " .... ")
+    countdown_rekursiv(i-1)
+</code>
+  * Teste deinen Code
+  * Skizziere ein Programmablaufdiagramm für die rekursive Variante mit Fallunterscheidung.