Brauchen Sie Verständnis dieser Rekursion

Question

Ich weiß nicht warum, aber ich kann diese Rekursion für den Tod von mir nicht verfolgen und es wirklich mich sauer. Ich würde mich freuen, wenn jemand helfen könnte zu erklären, wie man das durchmacht.

public class MindNumber 
{ 

    public static int numb(int i) 
    { 
    int result; 


    if (i < 1) 
    { 
     result = -1; 

    } 
    else if (i < 10) 
    { 
     result = numb(i - 1) + numb(i - 2); 

    } 
    else if (i % 2 == 0) 
    { 
     result = numb(i/2); 
    } 
    else 
    { 
     result = numb(i/2) + numb(i % 2); 

    } 

    return result; 
    } 
} 

public class MindNumberDriver 
{ 
    public static void main(String[] args) 
    { 
    int i; 

    i = MindNumber.numb(12); 

    System.out.println(i); 

    } 
} 

Der Ausgang ist -21. Verstehe nicht, wie es ehrlich dazu kommt.

Answer 1

Sie durch den Prozess zu helfen:

i zu starten = 12, so treten wir in die dritte Bedingung, die taub (6)

taub (6) kehrt zurück taub (5) + taub (4

)

betäubt (5) zurückgibt taub (4) + taub (3)

tauben (4) gibt taub (3) + taub (2)

taub (3) liefert taub (2) + taub (1)

taub (2) gibt taub (1) + taub (0) = taub (1) + (-1)

taub (1) betäubt (0) + taub (-1) = (Returns - 1) + (-1) = (-2)

Jetzt können wir anfangen, den Call-Stack wieder hochzulaufen.

taub (2) gibt taub (1) + taub (0) = (-2) + (-1) = (-3)

taub (3) liefert taub (2) + taub (1) = (-3) + (-2) = (-5)

... ect

Answer 2

Dies ist die negative Fibonacci-Folge für Zahlen im Bereich von 1 bis 9:

-1, -1, -2, -3, -5, -8, -13, -21, -34, ... 
f(6) = 21 

Die kritischen Schritte hier sind die ersten beiden Bedingungssätze, i < 1 und i < 10. Die beiden anderen übersetzen einfach :

If **i** is even, recur using half that value; 
otherwise, recur using half the value rounded up. 

Die Ausführung ist hier

i = 12; wiederholen mit 12/2, oder 6.
i = 6; return -f (6)

Wenn Sie die Ausführung verfolgen möchten, verwenden Sie eine sehr alte, Low-Tech-Debugging-Technik: Drucken Sie Anweisungen, um den Ausführungs- und Datenfluss zu verfolgen. Wenn Sie eine Routine eingeben, drucken Sie ihre Argumente. Drucken Sie kurz vor dem Verlassen den Wert, den Sie zurückgeben möchten. Beschriften Sie jeden Druck, damit Sie der Aktion folgen können.