Auflösung einer linearen Rekursion

#1
Hallo liebes Forum
! Dies hier ist mein erster Beitrag hier und ich bin gerade sehr sehr verzweifelt. Es geht um die Lösung einer Aufgabe, bei der ich gerade vor einer sprichwörtlichen Wand stehe. Wenn ihr mir dabei irgendwie helfen könntet wäre ich extrem dankbar.

Die Aufgabe lautet wie folgt:
Eine allgemeine lineare Rekursion, d.h. eine Rekursion mit nur einem rekursiven Aufruf, hat die untenstehende Form. Dabei sind Problem und Loesung zwei Typen, die alle notwendigen Informationen enthalten.
Schreiben Sie, unter Verwendung eines Stacks und der unten zur Verfügung gestellten Zeile, eine iterative Funktion, die die gleiche Berechnung durchführt, wie die dargestellte rekursive Funktion.
Geben Sie die Lösung durch jeweils ein Leerzeichen getrennt ein (Lösung unter Angabe der Zahlen/Buchstabenangabe die jeweils vor den Zeilen unten stehen). Verwenden Sie nur Grossbuchstaben und ergänzen Sie geschweifte schliessende und öffnende Klammmern, wo sie nach den üblichen Regeln benötigt werden.

Loesung funktion(Problem X) {
if ( klein(X) ) {
return berechneLoesung(X);
}else{
Problem Xk = macheKlein(X);
Loesung Yk = funktion(Xk);
return kombiniereLoesung(X,Yk);
}
}



Zur Verfügung gestellte Zeilen:
1 Y = berechneLoesung(X);
2A Y = kombiniereLoesung(X,Y);
2B X = kombiniereLoesung(X,Y);
3A S.push(X);
3B S.top(X);
4 X = macheKlein(X);
5 return Y;
6A X = S.top();
6B X = S.pop();
7 while (!S.isempty())
8A while( !klein(X) )
8B while( klein(X) )
9 S = new Stack();
 
Oben