Rekursion ordentlich aufschreiben

[ocsme]

Guten Tag zusammen,

ich hab mal wieder ein Problem mit der Rekursion wie ich auf die Werte komme klappt so la la 🙂 doch ich weiß nicht wie man das Effektiv aufschreiben kann 😉
Wir sollen das in Tabellenform so aufschreiben:

Rekursive Aufrufe von c(...)
c( , )
c( , )
...

Rückgabewerte von c(...)

Hier mal eine Aufgabe:

public static int calc(int n) {
        if (n<2)
            return n;
        return (calc(n-1) + calc(n-2));
       
        }
       
        public static void main(String[] args) {
            int n = 4;
            System.out.println(calc(n));
           
        }

Ich zeichne es mir immer so auf: bei n=4
calc(3)+calc(2)
calc(3) = calc(2)+calc(1) calc(2)=calc(1)+calc(0)

Damit ist: calc(2) = calc(1)=1 und calc(0)=0 =1
calc(3)=1+1
also ist calc(4)=(1+1)<- das kommt von calc(3) +1 <- calc(2)

Wie schreibe ich das ganze aber schön auf? Bei n=10 komme ich z. B. überhaupt nicht mehr klar 😀

LG

 

[httpdigest]

Also, eine Baumstruktur der rekursiven Aufrufe wirst du bei dem von dir verwendeten Code ja immer haben. Wenn du das jetzt nicht aus Baum sondern sequenziell aufschreiben willst, müsstest du dir nur eine Traversierungsreihenfolge des Baumes auswählen (pre-order, in-order, post-order) und den Baum gemäß dieser Reihenfolge ablaufen bzw. die jeweiligen Aufrufe der Baumknoten sequenziell aufschreiben.
Du kannst bei deinem Code noch zusätzlich ausnutzen, dass die beiden rekursiven Aufrufe sich ihrerseits viele Unteraufrufe mit denselben Parameterkonstellationen teilen werden. Z.B. wiederholt sich ja im linken Teilbaum durch das calc(n-1)...calc(n-1) der rechte Teilbaum calc(n-2) alle zwei Rekursionstiefen. Du musst also nicht _alle_ rekursiven Aufrufe durchspielen.

 

[ocsme]

Vielen Dank für die Ausführliche Antwort.
Habe ja auch gemerkt also ich die ersten paar Werte eingesetzt habe das die n-1 und n-2 sich Überschneiden. Wenn man das etwas Ordentlich aufschreibt und den Block quer nimmt klappt es ganz gut.

Auf die Traversierungsarten bin ich überhaupt nicht gekommen das ist ja mal eine Witzige Idee mal schauen ob ich es hin bekomme wenn nicht klappt es ja nun auch erst mal so 😉 Bin ja schon Froh wenn die Werte raus kommen die mir auch der Computer ausgibt 😉

Danke nochmals =)