Rekursiver Aufruf - Was geht da eigentlich vor sich?

[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).