Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
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:27] – [Fallunterscheidung ist unbedingt notwendig] sbel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Rekursive Schachtelsuche ====== | ====== 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... | ||
+ | |||
+ | {{ : | ||
< | < | ||
funktion suche_schluessel(schachtel): | funktion suche_schluessel(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 " | + | ausgeben " |
</ | </ | ||
+ | |||
+ | Bei der Betrachtung des Pseudocodes fällt auf, dass sich die Funktion '' | ||
+ | |||
+ | <WRAP center round tip 60%> | ||
+ | Wenn eine Funktion sich selbst aufruft spricht man von **Rekursion**. | ||
+ | </ | ||
+ | |||
+ | //Ein Wort Eleganz und Performanz:// | ||
+ | |||
+ | < | ||
+ | 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! | ||
+ | </ | ||
+ | (Leigh Caldwell, http:// | ||
+ | |||
+ | ===== 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 " | ||
+ | |||
+ | Experiment | ||
+ | |||
+ |