Theoretische Frage: Rekursion / Iteration

Jan

Ich hab da mal eine eher theoretische Frage zu einer Informatik-Aufgabe.
Es sind mehrere Aufgaben, die eigentlich immer 2mal gelöst werden sollen, einmal mittels normaler Rekursion und dann noch einmal mit Hilfe einer rekursiven Iteration.
Die normale Rekursion war für mich bei allen Aufgaben kein Problem, bei der Iteration hakt es nur bei einer Aufgabe. Das Grundprinzip ist mir also klar.
Nun konkret zu meinem Problem:

Bisher waren alle Aufgaben so, dass man für die Iteration die gleiche Prozedur in sich selbst noch EINMAL aufruft und das Zwischenergebnis durchreicht.
Nun ist bei einer Aufgabe aber eine Funktion gegeben, die sich selbst DREImal aufruft. Wie zum Henker mach ich sowas?
Geht das überhaupt irgendwie? Mir ist das nicht ganz klar, wie das funktionieren könnte. Oder muss ich evtl. die Funktion erstmal irgendwie umbasteln?

Zur Info: die Funktion sieht so aus:

n für n <= 2
g(n) =
        g(n-1) + 2*g(n-2) + 3*g(n-3)  sonst

Normal Rekursiv ist das ja kein Problem. Ist natürlich extrem Ressourcen fressend, aber einfach zu programmieren.
Die Iterative Variante davon gelingt mir aber leider nicht so intuitiv.

volkard

Jan schrieb:

Nun ist bei einer Aufgabe aber eine Funktion gegeben, die sich selbst DREImal aufruft. Wie zum Henker mach ich sowas?

speicher die letzten drei werte in den variablen b,c,d und berechne a draus. dann shifte d=c;c=b;b=a;

Jan

volkard schrieb:

speicher die letzten drei werte in den variablen b,c,d und berechne a draus. dann shifte d=c;c=b;b=a;

Hmm, das hört sich jetzt ja prinzipiell nicht schlecht an. Ich muss wohl aber dazu sagen, dass wir mit SCHEME programmieren und ich keine globalen Variablen nutzen kann, sondern in den Funktionsaufrufen alle Variablen übergeben werden müssen.
Und da genau liegt mein Problem. Ich habe ein Zwischenergebnis, brauche aber 3 weitere Prozedurdurchläufe für das nächste Zwischenergebnis. D.h. das wären dann ja schon 3 Zwischenergebnisse, die ich irgendwie nicht mehr zusammenführen kann.
Oder gibt es eine Möglichkeit, die Funktion "von unten nach oben" durchlaufen zu lassen? Das sehe ich irgendwie nicht so. Also bleibt ja nur noch, sie von oben nach unten Schrittweise durchlaufen zu lassen. Allerdings hab ich ja bei jedem neuen Schritt 2 neue Variablen!? Wie könnte ich die Anzahl der benötigten Variablen konstant halten?

volkard

Jan schrieb:

Und da genau liegt mein Problem. Ich habe ein Zwischenergebnis, brauche aber 3 weitere Prozedurdurchläufe für das nächste Zwischenergebnis. D.h. das wären dann ja schon 3 Zwischenergebnisse, die ich irgendwie nicht mehr zusammenführen kann.

das macht man, indem man die variablen übergibt. ist irgendwie ein konzept, das knoten im hirn macht. ich schreib di5r mal ganz ungetestet hin, nach was sich das meiner meinung nach anfühlt:

int helper(int current,int end,int a,int b,int c){
   if(current==end)
      return a;
   else
      return helper(current+1,end,a+b+c,a,b);
}
int g(int n){
   return helper(1,n,2,2,2)
}

Jan

Hmm, ich werd das mal versuchen zu analysieren. Ich kann so absolut nicht überblicken, ob mir das weiterhilft, aber spätestens, wenn ich den Code mal in Scheme übertragen habe, weiß ich vielleicht mehr.