Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start [12.01.2022 21:08] – angelegt sbel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start [13.01.2022 08:34] – [Fallunterscheidung ist unbedingt notwendig] sbel
@@ Zeile 1: / Zeile 1: @@
 ====== Rekursive Schachtelsuche ======
+Die rekursive Denkweise macht sich zunutze, dass wir für jede Schachtel, wie wir finden, dasselbe tun müssen:
+  * Aufmachen.
+  * Wenn ein Schlüssel drin ist: Freuen!
+  * Wenn eine Schachtel drin ist: Das was wir mit jeder Schachtel machen...
+{{ :faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:rekursiv.drawio.png |}}
 <code>
 funktion suche_schluessel(schachtel):
-	für jeden gegenstand in schachtel:
+  für jeden gegenstand in schachtel:
-			wenn gegenstand.istSchachtel():
+    wenn gegenstand.istSchachtel():
-				 suche_schluessel(gegenstand)
+      suche_schluessel(gegenstand)
-			sonst wenn gegenstand.istSchlüssel:
+    sonst wenn gegenstand.istSchlüssel:
-				ausgeben "Schlüssel gefunden!"
+      ausgeben "Schlüssel gefunden!"
 </code>
+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 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? Erläutere, was das Problem ist - kannst du es lösen?