[Scheme] Iterative Version einer Funktion erstellen

[Stex]

Hallo,

ich sitze im Moment an einer Aufgabe, an der ich nicht wirklich weiterkomme:

Die Funktion f:N -> N sei definiert durch:
f = n für n <= 2
f = f(n - 1) + 2f(n - 2) + 3f(n - 3) für n > 2

Aufgabe: Schreiben Sie eine Prozedur (f_iter n), die f in einem iterativen Prozess berechnet.

Eine andere Teilaufgabe war, das ganze rekursiv zu berechnen, was kein großes Problem war.
Was ich hier nicht verstehe ist, wie ich die "Unteraufrufe" (f(n - 3)) mit ein und derselben Prozedur abarbeiten könnte, da ich ja auf jeden Fall wieder auf die "oberste Berechnungsebene" zurück muss, um zum Endergebnis zu kommen.
Ich hatte darüber nachgedacht, noch zusätzliche Parameter mitzugeben, die dann die Unteraufrufe hochzählen, aber je nachdem, wie hoch n letztendlich ist, kann ich das ja nicht dynamisch machen (vor allem, da ich noch nicht alle Bestandteile von Scheme nutzen darf, bspw. keine veränderbaren Variablen).

Hat jemand einen Denkanstoß für mich?

 

[theHacker]

Iterativ bedeutet in Schema, dass der Speicherbedarf konstant is. Für einen "normalen Programmierer" sieht die Lösung aber immer noch rekursiv aus

Du gibst einfach n Zusatzparameter mit, wie schon von dir angesprochen, damit findest du raus, in welcher Rekursionstiefe (bei rekursiver Lösung) du dich befindest.

Mein Vorgehen: Mach dir ne Wertetabelle, was du im Fall von z.B. n = 5 zu tun hast.

n|f|f(n-1)|2f(n-2)|3f(n-3)
1|1|-|-|-
2|1|1|-|-
3|1|1|2|-
4|3|3|2|3
5|8|6|12|9

Kp, ob ich richtig gerechnet hab. Und dann das Schema finden.

P.S. Ich hasse Scheme <- nur fürs Protokoll