10

Einführung in den Algorithmenentwurf (Fach) / Rekursion (Lektion)

Diese Lektion wurde von Eike_OS erstellt.

Lektion lernen

zurück  |  weiter 1 / 1

• Rekursion Eine Funktion die sich selbst aufruftEigenschaften:    Rückwärts gerichtet    Großes Problem wird auf kleineres Problem zurückgeführt
• Rückkopplung Mechanismus bei dem das Ausgangssignal in direkter/indirekter Weise auf den Eingang zurückgeführt wirdEigenschaften:    Vorwärts gerichtet    Nächster Zustand beruht auf vorherigem Zustand
• Primitive Rekursion Jede primitive Rekursion lässt sich durch eine Iteration implementierenBenötigt werden:    Rekursionsanfang/anker    Rekursionsschritt
• Endrekursion Rekursion, bei der nur ein rekursiver Aufruf am Ende erfolgt
• Tragfähiges mentales Modell der Rekursion Ordner exisitert, in dem jede Funktion als Kopiervorlage zur Verfügung stehtLokale Variablen & Parameter werden auf dem jeweiligen Blatt notiertFunktion wird abgearbeitet und aktuelle Stelle markiertBeim aufrufen einer neuen Funktion wird eine Kopie gemacht und auf's alte Blatt gelegtIst die Funktion abgearbeitet wirft man das aktuelle Blatt wegund arbeitet auf dem drunter liegenden Blatt weiterKonsequenz:    Eine Rekursion entspricht dem Aufbau eines Stacks
• Aktiver Datenfluss Datenfluss auf dem "Hinweg"
• passiver Datenfluss Datenfluss auf dem "Rückweg"    bereitet Probleme beim entwickeln von mentalen Modellen    findet nicht in Endrekursionen statt
• Strukturelle Rekursion Beruht auf der inneren Struktur von Datentypen
• Rekursiver Datentyp Datentyp der Werte seines eigenen Datentyps enthältVorteil: Nutzung des passiven Datenflusses auf dem Rückweg
• Backtracking Grundidee: Systematisches Durchsuchen des Raums nach allen LösungenLösungsraum:    alle möglichen Lösungen lassen sich als Blätter/Knoten in einem Baum anordnen    Knoten enthalten mögliche (Teil)Lösungen    Kinder sind meist ungültig    Suche entspricht einer Baumtraverse auf diesem Baum

zurück  |  weiter 1 / 1