faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung
Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start [12.01.2022 21:16] – [Fallunterscheidung ist unbedingt notwendig] sbelfaecher:informatik:oberstufe:algorithmen:rekursion:rekursionsschachteln:start [24.01.2024 11:37] (aktuell) – [Fallunterscheidung ist unbedingt notwendig] Marco Kuemmel
Zeile 23: Zeile 23:
 Wenn eine Funktion sich selbst aufruft spricht man von **Rekursion**. Wenn eine Funktion sich selbst aufruft spricht man von **Rekursion**.
 </WRAP> </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 ===== ===== 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. 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>
 +4 ..... 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.
  • faecher/informatik/oberstufe/algorithmen/rekursion/rekursionsschachteln/start.1642018561.txt.gz
  • Zuletzt geändert: 12.01.2022 21:16
  • von sbel