rekursiv in Iterativ ohne Stack (nicht endrekursiv)

Ist es möglich eine Funktion nicht nicht endrekursiv ist, also z.B.

f(n) = return (1 + f(n-1) + 2)

ohne Stack in eine Iteration umzuwandeln?

while(true)
?

Jester

Ich nehme an, dass Du einen Wert wie f(0)=x fest gegeben hast?

Dann kannst du f(n) = 1 + f(n-1) + 2 = f(n-1) + 3 auflösen.
Mein Tipp in diesem Fall wäre f(n) = 3*n + x, das kannst Du jetz zum Beispiel per Induktion beweisen. Es gibt auch mathematische Methoden, mit denen man solche Rekurrenzen teilweise direkt auflösen kann.

Uhm, ich glaub das Beispiel war doof.

Um genau zu sein geht es um folgende Aufgabe:
Was würde:

def D(n): return n and (2*n-1)*D(n-1) or 1
def N(n): return n and (4*n*n-8*n+3)*N(n-2)+7*D(n-2) or 1
b=1000000000000; print (N(b*4)*b)/D(b*4)

Ausgeben, wenn das Script durchlaufen würde. Das ist eine Aufgabe von Hacker.org und da will ich keine fertige Lösung hier haben.Da es in der Form zwangsläufig zum Stackoverflow kommen würde wollte ich das auf iterativ umstellen. Und für Funktion D ist das recht einfach:

def D(n):
	if n == 0:
		return 1
	result = (2*n - 1)
	n -= 1
	while n > 0:
		result *= (2*n - 1)
		n -= 1
	return result

Ist ja da nicht schwerer als z.B. die Fibonacci-Folge.
Aber für Funktion N (die ja auch D aufruft) komm ich einfach nicht drauf. Ist es da möglich das umzustellen? Oder ist da der Ansatz falsch und ich muss da mathematisch was rumbasteln? Die aufgabe ist in der Kategorie "coding", deswegen denke ich, dass ich in etwa auf dem richtigen Weg bin.

Jester

Wenn ich das richtig sehe, ist D(n) einfach Produkt über i=1..n (2i-1). Also das Produkt der ersten n ungeraden Zahlen. Wenn ich das als Bruch auffasse und noch mit den ersten n geraden Zahlen erweitere bekomme ich

(2n)!/ Produkt der ersten n geraden Zahlen

dann kann ich unten n 2en ausklammern und bekomme sowas wie (2n)!/(n!*2^n).
Vielleicht hilft Dir das weiter?

hustbaer

Wenn die "and" und "or" als bitweise Operationen zu verstehen sind, dann kann D(n) doch nie grösser werden als n+1 ... nicht?
Ich meine es sollte doch immer gelten a and b <= a und a or 1 <= a + 1 .

hustbaer: Das sind logische Operatoren. Die sind short circuit und geben den letzten ausgewerteten wert zurück. return n and f(n) or 1 gibt also f(n) zurück wenn n wahr ist, ansonsten 1,

Jester: Ja, ich glaub das hilft mir weiter, danke.