kann mir jeamnd mal an einem einfachen bsp das Prinzip eines rekursionsbaumes zeigen ?ich habe glaube ich denn Sinn verstanden aber ich komme nie auf die einzelnen Blätter des Baumes [18]
ich komme nie auf die einzelnen Blätter des Baumes [18]
die blätter sind da wo die rekursive funktion sich nicht nochmal selbst aufruft.
wenn ich also die
fibonacct-zahlen rekursiv berechnen will rechne ich:
f(4) = f(3) + f(2)
f(3):
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
f(1) = 1 [x] hier
f(0) = 0 [x] und hier sind die blätter (rekursionsabschluss)
f(2) = 1
f(3) = 1 + f(1) (nun muss man nochmal rekursiv absteigen)
f(1) = 1 [x] auch hier ein blatt
f(3) = 1 + 1 = 2 (nun aufsteigen)
f(4) = 2 + f(2) (und hier wieder absteigen)
f(2) = f(1) + f(0)
f(1) = 1 [x] hier
f(0) = 0 [x] und hier sind die blätter (rekursionsabschluss)
f(2) = 1
f(4) = 2 + 1 = 3
fertig.
für alle n > 1 muss ich die zahl rekursiv berechnen, für 0 und 1 ist die zahl fest definiert und ich muss nichts rekursiv berechnen. die blätter sind hier also immer f(0) und f(1).
Im Skript von rarey seite 34 das Bsp eines Rekursions Baumes die dritte ebene von der wurzel aus also da wo wir c(n/1)^2 haben wie komme ich auf die n/16 und warum mal c?
mmm und was ich garnicht vertehe ist wie komme ich dann auf die Kosten abschätzung der untersten ebene?
