Konvertieren einer rekursiven Funktion, die 2 Rekursion zu Iteration zurückgeben

Question

Ich habe immer Problem beim Konvertieren eines rekursiven Algorithmus, den ich erstellt habe, die 2 rekursiven Aufruf zurückgibt, bis der Basisfall erfüllt ist.

Es ist einfach zu mögen, zurückzuverfolgen, was jeder rekursive Aufruf tut, aber das Konvertieren in Iteration ist ein wenig verwirrend.

Zum Beispiel dieser rekursive Funktion

BEGIN SEQ(n) 
    if (n == 1) 
    return 3; 

    else if (n == 2) 
    return 2; 

    else 
    return SEQ(n - 2) + SEQ(n - 1) 

Dieses ziemlich geradlinig ist, wenn ich auf Gummi-Ente versuche meinen Weg durch die rekursive, die den Folgeprozess

SEQ (6) = SEQ erzeugt (4) + SEQ (5)

SEQ (5) = SEQ (3) + SEQ (4)

SEQ (4) = SEQ (2) + SEQ (3)

SEQ (3) = SEQ (1) + SEQ (2)

SEQ (2) = 2

...

SEQ (3) = 3 + 2 = 5

SEQ (4) = 2 + 5 = 7

SEQ (5) = 5 + 7 = 12

SEQ (6) = 7 + 12 = 19

Ich kann aber scheint nicht eine Iteration Art und Weise, die genau zurückkehren, um herauszufinden, wie die rekursive tut

Answer 1

Ihre Iteration Methode in C# könnte wie folgt aussehen:

public static int SEQ(int n) 
{ 
    if (n == 1) 
    { 
     return 3; 
    } 

    if (n == 2) 
    { 
     return 2; 
    } 
    var first = 3; 
    var second = 2; 

    for (var i = 3; i <= n; i++) 
    { 
     second += first; 
     first = second - first; 
    } 


    return second; 
}