Geschrieben von Vanni0601 am 09.07.2016 um 20:13:
Rekursionsfunktion verstehen
Hallo Zusammen,
Ich bin zur Zeit am Lernen für meine Algorithmen-Klausur in 2 Wochen.
Das Thema Rekursion habe ich immer fleißig vor mir hergeschoben, doch nun muss ich da langsam mal ran.
Und zwar ist mir diese Rekursionssache vollkommen unklar. Wenn mir eine Rekursionsgleichung gegeben ist, weiß ich nicht wirklich wie ich diese interpretieren soll und was diese genau aussagt.
Ein weiteres Problem stellt sich mir, wenn ein bestimmtes Problem geschildert wie ich daraus eine Rekursionsfunktion erstellen soll.
Zum Beispiel habe ich folgende Aufgabe vor mir liegen:
Betrachten Sie die Baumstruktur: innere Knoten haben eine von zwei möglichen Farben: Pink und lila. Ein pinker Knoten hat genau 2 lila Kinder. Ein lila Knoten hat genau 2 Pinke Kinder. Blätter haben keine Farbe. Die Wurzel ist lila.
Geben Sie eine rekursionsgleichung für die Anzahl der Knoten in Abhängigkeit von der Tiefe n des Baumes an.
Finden Sie eine geschlossene Form der Rekursionsgleichung und beweisen Sie deren Korrektheit.
So, wie der Baum aussieht habe ich mir bereits aufgezeichnet und was prinzipiell mit der Anzahl der Knoten in jedem weiteren Level des Baumes passiert ist mir auch klar. Aber wie zum Teufel stelle ich darauf aufbauend eine Rekursionsgleichung auf?
Ich bin echt verzweifelt, wahrscheinlich brauche ich nur einen kleinen Anschubser, aber ich verstehe momentan die ganze Geschichte mit den Rekursionen nicht.
Ich bin dankbar für jede noch so kleine Hilfe.
Grüße Vanny
