Rekursiver Aufruf - Was geht da eigentlich vor sich?

[3_of_8]

Also inherited selbst meinte irgendwas von n log n, aber wenn ich mir das so ansehe, sieht es nach was anderem aus.

Er hat - je nachdem, ob n gerade oder ungerade ist - 2 oder 3 Rekursionsbäume bei jedem Funktionsaufruf und die Rekursionstiefe ist in etwa ld n. Daraus ergibt sich als untere Grenze O(2^(ld n))=O(n) und als obere Grenze O(3^(ld n))=O(3^((log3 n)/(log3 2))=O(n), also O(n)... wenn ich mich jetzt nicht verrechnet habe...

[Khabarakh]

Du darfst die Memoisation nicht vergessen, denn die Aufrufe in der gleichen Rekursionstiefe überlappen sich stark. Wenn ich das richtig sehe, kommen mit jeder Rekursionstiefe höchstens zwei dazu, also insgesamt 2i+1 bei der Tiefe i. Summiert von 1 bis log n also O(log² n).

[sirius]

Nochmal zur Eingangsfrage:
Ich habe hier eine powerpoint-Prä gemacht, welche die Rekursion mal verdeutlichen soll:
http://www.delphipraxis.net/internal...196&highlight=