Das war zu kompliziert von mir gedacht. Hier dürfte ein Stack reichen.
Nehmen wir mal:
[code=Java]
public int f(int x) {
if (x <= 0) { return 0; }
return x + f(x-1) + f(x/2);
}
[/code]
Das lässt sich schreiben als:
[code=Java]
public int f(int x) {
if (x <= 0) { return 0; }
int sum = x;
sum += f(x-1); // erster rekursiver Aufruf
sum += f(x/2); // zweiter rekursiver Aufruf
return sum;
}
[/code]
Da die Reihenolge der Summanden keine Rolle spielt, kann man hier einfach die Werte auf den Stack legen:
[code=Java]
public int f(int x) {
int sum = 0;
Stack<Integer> stack = new Stack<>();
stack.push(x);
while (!stack.isEmpty()) {
int cx = stack.pop();
sum += cx;
if (cx > 1) {
stack.push(cx/2);
}
if (cx > 0) {
stack.push(cx-1);
}
}
return sum;
}
[/code]
Ansonsten müsste man cx-1 oben und cx/2 unten in den Stack einfügen, dann sollte auch die Reihenfolge passen.
