Rekursiv zu iterativ

Wurstinator

Eine mathematische Funktion.

speziell für die Fibonacci- und ähnliche Folgen: geschlossene Formel von de Moivre-Binet

Wurstinator

Was heißt "ähnliche Folgen"?

Ein Beispiel, an dem ich gerade hänge:
E(t) = 0,3 * 0,7^t-1 * G₀ + 0,6 * E(t-1)
E(0) = E₀

G₀ und E₀ sind Konstanten.

Wäre diese Funktion somit eine ähnliche Folge wie die Fibonacci-Zahlen?

nö. Ähnlich wäre z.B. die "k-generalized Fibonacci" f(n)=f(n-1)+f(n-2)+...+f(n-k).

einen allgemeinen rekursiven Funktionsaufruf f(x0) kann man ungefähr so in ein iteratives Programm umwandeln:

f(x):
    if(Abbruchbedingung(x)): 
        return g(x)
    else f(h(x))

=>

x := x0
while(not Abbruchbedingung(x)):
    x := h(x)
output g(x)

knivil

Wurstinator schrieb:

Hallo,
gibt es einen allgemeingültigen Weg, wie meine eine rekursive Funktion, wie z.B. die Fibonacci-Zahlen ( Fib(n) = Fib(n-1) + Fib(n-2) ) in eine iterative Funktion mit gleichem Ergebnis umwandeln kann?

Ja, scharf hingucken!

Nur mal ueberschlagen: E(t) = A*k^(t-1) + B*E(t-1) mit A und B als Konstanten ergibt bei mir E(t) = A*S_n{1,t}(B^n*k(t-n)) + B^(t)E₀. S_n{1,t}(..) Bedeutet dabei soviel wie Summe von 1 bis t mit Laufindex n. Kann sein, dass einige Indizes noch etwas angepasst werden muessen, ich habs nur mal ueberschlagen.

Bashar

Wurstinator schrieb:

Eine mathematische Funktion.

Dann fragst du nach einer expliziten Darstellung der Folge. Iterativ ist da das falsche Wort.

Das nur zur Erklärung, warum ich ohne weiteres Nachfragen von einem Programm ausgegangen bin.

Wurstinator

Bashar schrieb:

Dann fragst du nach einer expliziten Darstellung der Folge. Iterativ ist da das falsche Wort.

Achso? Na, dann habe ich es mir wohl mal irgendwann falsch gemerkt.
Somit hilft mir auch !rr!rr_.s Antwort nicht viel weiter, tut mir Leid für das Missverständnis.

@ knivil: Auf die Idee, die Funktion teilweise auszurechnen, bin ich nicht gekommen, danke schonmal dafür.
Gibt es noch einen anderen Weg oder sind andere Möglichkeiten immer nur auf sehr spezialisierte Funktionen anwendbar?

Jester

Einen Ansatz der immer funktioniert ist mir nicht bekannt. Es gibt aber eine ganze Menge Techniken mit denen man es versuchen kann: Differenzenmethode, erzeugende Funktionen und Darstellung als Matrix
-Multiplikation und dann diagonalisieren fallen mir da auf Anhieb ein.

Bitte ein Bit

Einen Ansatz der immer funktioniert ist mir nicht bekannt.

Ich weis nicht, aber ich glaube es gibt nicht immer einen Ansatz der funktioniert. Ackermann Funktion lässt sich hier als ein Beispiel nennen.

Wurstinator

@ Jester: Hättest du auch Links, die diese Techniken erklären?
Ich hab nur Aufgaben dazu gefunden, aber nirgends die Kentnisse dafür.