BPS #8: Rekursiv zu Iterativ

Übersicht

BlitzMax, BlitzMax NG

Beginners-Corner

	Xeres Moderator Betreff: BPS #8: Rekursiv zu Iterativ	Fr, Mai 13, 2011 11:44 Antworten mit Zitat
Einleitung, Motivation Oft gibt es für ein Problem eine einfache, rekursive Berechnungsformel. Man kommt meist auf eine rekursive Formel, wenn man versucht, das Problem so lange zu zerlegen, bis nur noch triviale Fälle übrig sind. Z.b. kann man 2^100 nicht mal eben so schnell im Kopf ausrechnen. Man weis aber, dass 2^100 = 22^99 ist. Am Ende hat man das ganze dann soweit runtergebrochen, bis man vllt 2^1 oder 2^0 da stehen hat, und ab da weis man das Ergebnis ja. Also schreibt man z.B. eine Funktion: Code:* [AUSKLAPPEN] [EINKLAPPEN] Function f2hoch:Int(x:Int) If x > 0 Return 2 * f2hoch(x - 1) return 1 End Function Diese rekursive Funktion ist jedoch selten performant, sprich nicht sehr schnell, da der Aufruf einer Funktion immer mit einem Sprung des Prozessors (und damit einhergehender Sicherung der Register etc. verbunden) ist. Zudem füllt sich so der Stack des Prozessors sehr schnell, sodass ab einer gewissen Tiefe eine Ausnahmebehandlung aufgerufen wird, welche das Programm in der Regel zum Absturz bringt. Daher beschäftigen wir uns in dieser Folge mit der Transformation von rekursiven Funktionen in iterative Funktionen. Bei iterativen Funktionen wird der Wert nicht durch Aufruf der gleichen Funktion mit anderen Werten, sondern durch einen Schleifendurchlauf berechnet. Das erspart den Sprung in eine andere Funktion und erhöht somit die Ausführgeschwindigkeit. Für unser obiges Beispiel könnten wir z.B. einfach eine For-Schleife wählen, und den Wert in einer variablen zwischenspeichern: Code: [AUSKLAPPEN] [EINKLAPPEN] Function f2hochIterativ:Int(x:Int) y:Int = 1 For Local i:Int = 0 Until x y:2 Next Return y End Function Noch ein einfaches Beispiel: Code:* [AUSKLAPPEN] [EINKLAPPEN] 'Die beiden Funktionen werden mit Werten von 0 bis 15 gefüttert und das Ergebnis ausgegeben. For Local i:Int = 0 To 15 Print i + " rekursiv: " + bsp_rekursiv(i) + " iterativ: " + bsp_iterativ(i) Next 'Beispielfunktionen Function bsp_rekursiv:Int(n:Int) If n <= 0 Return 0 Return 1 + bsp_rekursiv(n - 1) End Function Function bsp_iterativ:Int(n:Int) Local a:Int For Local i:Int = 1 To n a:+1 Next Return a End Function Beide Funktionen berechnen genau die gleichen Werte! Die iterative Funktion tut dies jedoch viel optimierter als die rekursiv programmierte. Aufgabenstellung: Schreibe die folgenden rekursiv programmierten Funktionen in iterative um: Funktion 1 (leicht) Code: [AUSKLAPPEN] [EINKLAPPEN] Function func1_rekursiv:Int(n:Int) If n = 0 Return n Return n + func1_rekursiv(n - 1) End Function Funktion 2 (schwer) Code: [AUSKLAPPEN] [EINKLAPPEN] Function fib_rekursiv:Int(x:Int) If x = 0 Return 0 If x = 1 Return 1 Return fib_rekursiv(x - 1) + fib_rekursiv(x - 2) End Function Tipps: Lass dir die Ergebnisse der Funktionen mittels For-Schleife für unterschiedliche Werte anzeigen. So kannst du dein Ergebnis auch einfach überprüfen. Für iterative Programmierung arbeitet man meistens mit For-Schleifen. Überlege dir, was passiert, wenn der Funktion eine 2 übergeben wird. Verfolge den Weg der Zahl durch die Funktion. Für die zweite Funktion: Es handelt sich um die Fibbonacci-Reihe. Zeit: Ihr habt zwei Wochen Zeit um eure Programme zu schreiben. Bitte postet Eure fertigen Codes erst in zwei Wochen, wenn der Auswertungsthread erstellt wird, dort hinein. Fragen könnt ihr hier natürlich jederzeit stellen. RELATED TOPIC: Auswertungsthread RELATED TOPIC: Die Beginner's Practice Series (BPS)
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Betreff: BPS #8: Rekursiv zu Iterativ

Fr, Mai 13, 2011 11:44
Antworten mit Zitat

Einleitung, Motivation
Oft gibt es für ein Problem eine einfache, rekursive Berechnungsformel. Man kommt meist auf eine rekursive Formel, wenn man versucht, das Problem so lange zu zerlegen, bis nur noch triviale Fälle übrig sind. Z.b. kann man 2^100 nicht mal eben so schnell im Kopf ausrechnen. Man weis aber, dass 2^100 = 2*2^99 ist. Am Ende hat man das ganze dann soweit runtergebrochen, bis man vllt 2^1 oder 2^0 da stehen hat, und ab da weis man das Ergebnis ja. Also schreibt man z.B. eine Funktion:

Code: [AUSKLAPPEN]

Function f2hoch:Int(x:Int)
If x > 0 Return 2 * f2hoch(x - 1)
return 1
End Function

Diese rekursive Funktion ist jedoch selten performant, sprich nicht sehr schnell, da der Aufruf einer Funktion immer mit einem Sprung des Prozessors (und damit einhergehender Sicherung der Register etc. verbunden) ist. Zudem füllt sich so der Stack des Prozessors sehr schnell, sodass ab einer gewissen Tiefe eine Ausnahmebehandlung aufgerufen wird, welche das Programm in der Regel zum Absturz bringt.

Daher beschäftigen wir uns in dieser Folge mit der Transformation von rekursiven Funktionen in iterative Funktionen. Bei iterativen Funktionen wird der Wert nicht durch Aufruf der gleichen Funktion mit anderen Werten, sondern durch einen Schleifendurchlauf berechnet. Das erspart den Sprung in eine andere Funktion und erhöht somit die Ausführgeschwindigkeit.

Für unser obiges Beispiel könnten wir z.B. einfach eine For-Schleife wählen, und den Wert in einer variablen zwischenspeichern:

Code: [AUSKLAPPEN]

Function f2hochIterativ:Int(x:Int)
y:Int = 1
For Local i:Int = 0 Until x
y:*2
Next
Return y
End Function

Noch ein einfaches Beispiel:
Code: [AUSKLAPPEN]

'Die beiden Funktionen werden mit Werten von 0 bis 15 gefüttert und das Ergebnis ausgegeben.
For Local i:Int = 0 To 15
Print i + " rekursiv: " + bsp_rekursiv(i) + " iterativ: " + bsp_iterativ(i)
Next

'Beispielfunktionen
Function bsp_rekursiv:Int(n:Int)
If n <= 0 Return 0
Return 1 + bsp_rekursiv(n - 1)
End Function

Function bsp_iterativ:Int(n:Int)
Local a:Int
For Local i:Int = 1 To n
a:+1
Next
Return a
End Function

Beide Funktionen berechnen genau die gleichen Werte! Die iterative Funktion tut dies jedoch viel optimierter als die rekursiv programmierte.

Aufgabenstellung:
Schreibe die folgenden rekursiv programmierten Funktionen in iterative um:

Funktion 1 (leicht)
Code: [AUSKLAPPEN]

Function func1_rekursiv:Int(n:Int)
If n = 0 Return n
Return n + func1_rekursiv(n - 1)
End Function

Funktion 2 (schwer)
Code: [AUSKLAPPEN]

Function fib_rekursiv:Int(x:Int)
If x = 0 Return 0
If x = 1 Return 1
Return fib_rekursiv(x - 1) + fib_rekursiv(x - 2)
End Function

Tipps:

Lass dir die Ergebnisse der Funktionen mittels For-Schleife für unterschiedliche Werte anzeigen. So kannst du dein Ergebnis auch einfach überprüfen.
Für iterative Programmierung arbeitet man meistens mit For-Schleifen.
Überlege dir, was passiert, wenn der Funktion eine 2 übergeben wird. Verfolge den Weg der Zahl durch die Funktion.
Für die zweite Funktion: Es handelt sich um die Fibbonacci-Reihe.

Zeit:
Ihr habt zwei Wochen Zeit um eure Programme zu schreiben. Bitte postet Eure fertigen Codes erst in zwei Wochen, wenn der Auswertungsthread erstellt wird, dort hinein.
Fragen könnt ihr hier natürlich jederzeit stellen.

RELATED TOPIC: Auswertungsthread
RELATED TOPIC: Die Beginner's Practice Series (BPS)

Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Zuletzt bearbeitet von Xeres am Di, Dez 20, 2011 5:54, insgesamt 2-mal bearbeitet

	BlitzMoritz Betreff: Re: BPS #8: Rekursiv zu Iterativ	Fr, Mai 13, 2011 20:45 Antworten mit Zitat
Kleiner Tippfehler, es müsste wohl so lauten: Xeres hat Folgendes geschrieben: 'Die beiden Funktionen werden mit Werten von 0 bis 15 gefüttert und das Ergebnis ausgegeben. For Local i:Int = 0 To 15 Print i + " rekursiv: " + bsp_rekursiv(i) + " iterativ: " + bsp_iterativ(i) Next Edit: Für die leichte Aufgabe braucht man nicht einmal eine iterative Funktion, sondern lediglich die Summenformel, die ich jetzt natürlich nicht verrate, die sich aber leicht jeder selbst erschließen kann.

BlitzMoritz

Betreff: Re: BPS #8: Rekursiv zu Iterativ

Fr, Mai 13, 2011 20:45
Antworten mit Zitat

Kleiner Tippfehler, es müsste wohl so lauten:
Xeres hat Folgendes geschrieben:

'Die beiden Funktionen werden mit Werten von 0 bis 15 gefüttert und das Ergebnis ausgegeben.
For Local i:Int = 0 To 15
Print i + " rekursiv: " + bsp_rekursiv(i) + " iterativ: " + bsp_iterativ(i)
Next

Edit: Für die leichte Aufgabe braucht man nicht einmal eine iterative Funktion, sondern lediglich die Summenformel, die ich jetzt natürlich nicht verrate, die sich aber leicht jeder selbst erschließen kann.

	BlitzMoritz	So, Mai 15, 2011 9:37 Antworten mit Zitat
Nachdem ich mich jetzt ein bisschen mit dem Thema auseinandergesetzt habe, möchte ich vorsichtig hinterfragen, ob die in der Aufgabenstellung postulierte Prämisse, Probleme generell eher nicht rekursiv, sondern iterativ zu lösen, tatsächlich sinnvoll ist. Ich glaube nämlich, dass Rekursionen je nach Problem sehr wohl ihren berechtigten Platz haben und dort auch kaum sinnvoll durch Iterationen zu ersetzen sind. Sicher - die dargestellten Beispiele sind berechtigt, aber wer käme schon auf die Idee, eine rekursive Funktion zu bauen, wenn es lediglich darum geht, natürliche Zahlen zusammen zu zählen? Ob rekursiv oder iterativ, ist vielleicht keine Frage der Optimierung, sondern des zu lösenden Problems. Denn auf vielen Gebieten bieten sich Rekursionen wunderbar an, z.B. bei Spielzug-Vorausberechnungen einer Künstlichen Intelligenz oder bei Darstellungen von L-Systemen und Fraktalen. Nachdem die beiden BPS-Aufgaben in wenigen Zeilen zu lösen waren, habe ich mich einer dritten Aufgabe gestellt, nämlich dem folgenden pflanzenartigen Gewächs, bei dem ich wiederum nie auf die Idee gekommen wäre, sie iterativ statt rekursiv umzusetzen: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Graphics 800,600 Global MaxDepth% = 16 'Die Tiefe der Rekursion bzw. Iteration 'Hier nun die variierbaren Daten der beiden jeweils neuen Äste im Vergleich zum vorigen Ast: Global DistanceFactor#[] = [0.7, 1.0] 'Abstand Global LengthFactor#[] = [0.8, 0.7] 'Länge Global AngleAddition%[] = [-45, 30] 'Winkeländerung Function Bush_rekursiv(x%, y%, angle%, length%, Rekursion% = 0) SetColor Rand(0,192), Rand(64,255), 0 DrawLine x, y, x + length * Cos(angle), y + length * Sin(angle) If Rekursion < MaxDepth Then Bush_rekursiv(x + DistanceFactor[0] * length * Cos(angle), y + DistanceFactor[0] * length * Sin(angle), angle + AngleAddition[0], length * LengthFactor[0], Rekursion + 1) Bush_rekursiv(x + DistanceFactor[1] * length * Cos(angle), y + DistanceFactor[1] * length * Sin(angle), angle + AngleAddition[1], length * LengthFactor[1], Rekursion + 1) End If End Function Bush_rekursiv(320, 550, 300, 160) Flip WaitKey() Der einzige Unterschied zu den simplen Beispielaufgaben besteht darin, dass die Funktion sich nicht nur einmal, sondern mehrfach selbst aufruft. Je nach Rekursionstiefe bedeutet das ein potentielles Anwachsen der Datenfülle, die in einer iterativen Umsetzung gespeichert werden müsste, wobei wohl kein Weg an Listen oder dynamischen Arrays vorbeigeht. Ich habe einmal beides umgesetzt und musste prompt feststellen, dass beide iterativen Varianten um einiges langsamer waren als die oben dargestellte rekursive Lösung. Mehr dazu im Auswertungsthread. Und auf ein "Stack Overflow" bin ich in meinem ganzen Programmierleben eigentlich nur dann gestoßen, wenn ich schlichtweg vergessen hatte, die Rekursionstiefe zu begrenzen. Immerhin werden bei dem pflanzenartigen Gewächs mehr als 130.000 Ästchen gezeichnet.

BlitzMoritz

So, Mai 15, 2011 9:37
Antworten mit Zitat

Nachdem ich mich jetzt ein bisschen mit dem Thema auseinandergesetzt habe, möchte ich vorsichtig hinterfragen, ob die in der Aufgabenstellung postulierte Prämisse, Probleme generell eher nicht rekursiv, sondern iterativ zu lösen, tatsächlich sinnvoll ist.
Ich glaube nämlich, dass Rekursionen je nach Problem sehr wohl ihren berechtigten Platz haben und dort auch kaum sinnvoll durch Iterationen zu ersetzen sind. Sicher - die dargestellten Beispiele sind berechtigt, aber wer käme schon auf die Idee, eine rekursive Funktion zu bauen, wenn es lediglich darum geht, natürliche Zahlen zusammen zu zählen? Ob rekursiv oder iterativ, ist vielleicht keine Frage der Optimierung, sondern des zu lösenden Problems.
Denn auf vielen Gebieten bieten sich Rekursionen wunderbar an, z.B. bei Spielzug-Vorausberechnungen einer Künstlichen Intelligenz oder bei Darstellungen von L-Systemen und Fraktalen. Nachdem die beiden BPS-Aufgaben in wenigen Zeilen zu lösen waren, habe ich mich einer dritten Aufgabe gestellt, nämlich dem folgenden pflanzenartigen Gewächs, bei dem ich wiederum nie auf die Idee gekommen wäre, sie iterativ statt rekursiv umzusetzen:
BlitzMax: [AUSKLAPPEN]

Graphics 800,600

Global MaxDepth% = 16 'Die Tiefe der Rekursion bzw. Iteration
'Hier nun die variierbaren Daten der beiden jeweils neuen Äste im Vergleich zum vorigen Ast:
Global DistanceFactor#[] = [0.7, 1.0] 'Abstand
Global LengthFactor#[] = [0.8, 0.7]	 'Länge
Global AngleAddition%[] = [-45, 30]	 'Winkeländerung

Function Bush_rekursiv(x%, y%, angle%, length%, Rekursion% = 0)
	SetColor Rand(0,192), Rand(64,255), 0
	DrawLine x, y, x + length * Cos(angle), y + length * Sin(angle)
	If Rekursion < MaxDepth Then
		Bush_rekursiv(x + DistanceFactor[0] * length * Cos(angle), y + DistanceFactor[0] * length * Sin(angle), angle + AngleAddition[0], length * LengthFactor[0], Rekursion + 1)
		Bush_rekursiv(x + DistanceFactor[1] * length * Cos(angle), y + DistanceFactor[1] * length * Sin(angle), angle + AngleAddition[1], length * LengthFactor[1], Rekursion + 1)
	End If		
End Function

Bush_rekursiv(320, 550, 300, 160)
Flip
WaitKey()

Der einzige Unterschied zu den simplen Beispielaufgaben besteht darin, dass die Funktion sich nicht nur einmal, sondern mehrfach selbst aufruft. Je nach Rekursionstiefe bedeutet das ein potentielles Anwachsen der Datenfülle, die in einer iterativen Umsetzung gespeichert werden müsste, wobei wohl kein Weg an Listen oder dynamischen Arrays vorbeigeht. Ich habe einmal beides umgesetzt und musste prompt feststellen, dass beide iterativen Varianten um einiges langsamer waren als die oben dargestellte rekursive Lösung. Mehr dazu im Auswertungsthread.
Und auf ein "Stack Overflow" bin ich in meinem ganzen Programmierleben eigentlich nur dann gestoßen, wenn ich schlichtweg vergessen hatte, die Rekursionstiefe zu begrenzen. Immerhin werden bei dem pflanzenartigen Gewächs mehr als 130.000 Ästchen gezeichnet.

	BladeRunner Moderator	So, Mai 15, 2011 9:44 Antworten mit Zitat
Es wird ja nicht behauptet Iteration wäre generell besser als Rekursion. Aber in vielen Fällen ist die Iteration ein sehr effizienter Weg, wohingegen die Rekursion oft in der Tat leichter umzusetzen ist. Nur meine 2ct.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

So, Mai 15, 2011 9:44
Antworten mit Zitat

Es wird ja nicht behauptet Iteration wäre generell besser als Rekursion. Aber in vielen Fällen ist die Iteration ein sehr effizienter Weg, wohingegen die Rekursion oft in der Tat leichter umzusetzen ist.
Nur meine 2ct.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Xaymar ehemals "Cgamer"	Do, Mai 26, 2011 20:03 Antworten mit Zitat
Darf man hier auch mit anderen Programmiersprachen als nur Blitz mitmachen? BPS ist nicht nur für Blitzer sehr nützlich. Ich habe btw das Limit an Rekursionen bei 36890(mit Mono, 24013 bei .Net, 12192 bei BlitzMax) erreicht, StackOverflowException. Edit: Hier meine aktuellen Ergebnisse, fibonacci rekursiv laufen lassen ist wirklich langsam. Code: [AUSKLAPPEN] [EINKLAPPEN] Value 0: Func1=r0&i0 Func2=r0&i0 Time1=r117187&i0 Time2=r0&i9766 Value 1: Func1=r1&i1 Func2=r1&i1 Time1=r0&i0 Time2=r0&i0 Value 2: Func1=r3&i3 Func2=r1&i1 Time1=r0&i0 Time2=r0&i0 Value 3: Func1=r6&i6 Func2=r2&i2 Time1=r0&i0 Time2=r0&i0 Value 4: Func1=r10&i10 Func2=r3&i3 Time1=r0&i0 Time2=r0&i0 Value 5: Func1=r15&i15 Func2=r5&i5 Time1=r0&i0 Time2=r0&i0 Value 6: Func1=r21&i21 Func2=r8&i8 Time1=r0&i0 Time2=r0&i0 Value 7: Func1=r28&i28 Func2=r13&i13 Time1=r0&i0 Time2=r0&i0 Value 8: Func1=r36&i36 Func2=r21&i21 Time1=r0&i0 Time2=r0&i0 Value 9: Func1=r45&i45 Func2=r34&i34 Time1=r0&i0 Time2=r0&i0 Value 10: Func1=r55&i55 Func2=r55&i55 Time1=r0&i0 Time2=r0&i0 Value 11: Func1=r66&i66 Func2=r89&i89 Time1=r0&i0 Time2=r0&i0 Value 12: Func1=r78&i78 Func2=r144&i144 Time1=r0&i0 Time2=r0&i0 Value 13: Func1=r91&i91 Func2=r233&i233 Time1=r0&i0 Time2=r0&i0 Value 14: Func1=r105&i105 Func2=r377&i377 Time1=r0&i0 Time2=r0&i0 Value 15: Func1=r120&i120 Func2=r610&i610 Time1=r0&i0 Time2=r0&i0 Value 16: Func1=r136&i136 Func2=r987&i987 Time1=r0&i0 Time2=r0&i0 Value 17: Func1=r153&i153 Func2=r1597&i1597 Time1=r0&i0 Time2=r0&i0 Value 18: Func1=r171&i171 Func2=r2584&i2584 Time1=r0&i0 Time2=r0&i0 Value 19: Func1=r190&i190 Func2=r4181&i4181 Time1=r0&i0 Time2=r0&i0 Value 20: Func1=r210&i210 Func2=r6765&i6765 Time1=r0&i0 Time2=r0&i0 Value 21: Func1=r231&i231 Func2=r10946&i10946 Time1=r0&i0 Time2=r9766&i0 Value 22: Func1=r253&i253 Func2=r17711&i17711 Time1=r0&i0 Time2=r9765&i0 Value 23: Func1=r276&i276 Func2=r28657&i28657 Time1=r0&i0 Time2=r9766&i0 Value 24: Func1=r300&i300 Func2=r46368&i46368 Time1=r0&i0 Time2=r19531&i0 Value 25: Func1=r325&i325 Func2=r75025&i75025 Time1=r0&i0 Time2=r19531&i0 Value 26: Func1=r351&i351 Func2=r121393&i121393 Time1=r0&i0 Time2=r39063&i0 Value 27: Func1=r378&i378 Func2=r196418&i196418 Time1=r0&i0 Time2=r58593&i0 Value 28: Func1=r406&i406 Func2=r317811&i317811 Time1=r0&i0 Time2=r87891&i0 Value 29: Func1=r435&i435 Func2=r514229&i514229 Time1=r0&i0 Time2=r136718&i0 Value 30: Func1=r465&i465 Func2=r832040&i832040 Time1=r0&i0 Time2=r214844&i0 Value 31: Func1=r496&i496 Func2=r1346269&i1346269 Time1=r0&i0 Time2=r390625&i0 Value 32: Func1=r528&i528 Func2=r2178309&i2178309 Time1=r0&i0 Time2=r644531&i0 Value 33: Func1=r561&i561 Func2=r3524578&i3524578 Time1=r0&i0 Time2=r927734&i0 Value 34: Func1=r595&i595 Func2=r5702887&i5702887 Time1=r0&i0 Time2=r1708984&i0 Value 35: Func1=r630&i630 Func2=r9227465&i9227465 Time1=r0&i0 Time2=r2441407&i0 Value 36: Func1=r666&i666 Func2=r14930352&i14930352 Time1=r0&i0 Time2=r4531250&i0 Value 37: Func1=r703&i703 Func2=r24157817&i24157817 Time1=r0&i0 Time2=r7148438&i0 Value 38: Func1=r741&i741 Func2=r39088169&i39088169 Time1=r0&i0 Time2=r11435547&i0 Value 39: Func1=r780&i780 Func2=r63245986&i63245986 Time1=r0&i0 Time2=r17226563&i0 Value 40: Func1=r820&i820 Func2=r102334155&i102334155 Time1=r9765&i0 Time2=r29960938&i0 Value 41: Func1=r861&i861 Func2=r165580141&i165580141 Time1=r0&i0 Time2=r45234375&i0 Value 42: Func1=r903&i903 Func2=r267914296&i267914296 Time1=r0&i0 Time2=r72919921&i0 Value 43: Func1=r946&i946 Func2=r433494437&i433494437 Time1=r0&i0 Time2=r118759766&i0 Value 44: Func1=r990&i990 Func2=r701408733&i701408733 Time1=r0&i0 Time2=r194355469&i0 Value 45: Func1=r1035&i1035 Func2=r1134903170&i1134903170 Time1=r0&i0 Time2=r310996093&i0 Iterativ ist wirklich schneller

Xaymar

ehemals "Cgamer"

Do, Mai 26, 2011 20:03
Antworten mit Zitat

Darf man hier auch mit anderen Programmiersprachen als nur Blitz mitmachen? BPS ist nicht nur für Blitzer sehr nützlich.
Ich habe btw das Limit an Rekursionen bei 36890(mit Mono, 24013 bei .Net, 12192 bei BlitzMax) erreicht, StackOverflowException.

Edit: Hier meine aktuellen Ergebnisse, fibonacci rekursiv laufen lassen ist wirklich langsam.
Code: [AUSKLAPPEN]

Value 0: Func1=r0&i0 Func2=r0&i0 Time1=r117187&i0 Time2=r0&i9766
Value 1: Func1=r1&i1 Func2=r1&i1 Time1=r0&i0 Time2=r0&i0
Value 2: Func1=r3&i3 Func2=r1&i1 Time1=r0&i0 Time2=r0&i0
Value 3: Func1=r6&i6 Func2=r2&i2 Time1=r0&i0 Time2=r0&i0
Value 4: Func1=r10&i10 Func2=r3&i3 Time1=r0&i0 Time2=r0&i0
Value 5: Func1=r15&i15 Func2=r5&i5 Time1=r0&i0 Time2=r0&i0
Value 6: Func1=r21&i21 Func2=r8&i8 Time1=r0&i0 Time2=r0&i0
Value 7: Func1=r28&i28 Func2=r13&i13 Time1=r0&i0 Time2=r0&i0
Value 8: Func1=r36&i36 Func2=r21&i21 Time1=r0&i0 Time2=r0&i0
Value 9: Func1=r45&i45 Func2=r34&i34 Time1=r0&i0 Time2=r0&i0
Value 10: Func1=r55&i55 Func2=r55&i55 Time1=r0&i0 Time2=r0&i0
Value 11: Func1=r66&i66 Func2=r89&i89 Time1=r0&i0 Time2=r0&i0
Value 12: Func1=r78&i78 Func2=r144&i144 Time1=r0&i0 Time2=r0&i0
Value 13: Func1=r91&i91 Func2=r233&i233 Time1=r0&i0 Time2=r0&i0
Value 14: Func1=r105&i105 Func2=r377&i377 Time1=r0&i0 Time2=r0&i0
Value 15: Func1=r120&i120 Func2=r610&i610 Time1=r0&i0 Time2=r0&i0
Value 16: Func1=r136&i136 Func2=r987&i987 Time1=r0&i0 Time2=r0&i0
Value 17: Func1=r153&i153 Func2=r1597&i1597 Time1=r0&i0 Time2=r0&i0
Value 18: Func1=r171&i171 Func2=r2584&i2584 Time1=r0&i0 Time2=r0&i0
Value 19: Func1=r190&i190 Func2=r4181&i4181 Time1=r0&i0 Time2=r0&i0
Value 20: Func1=r210&i210 Func2=r6765&i6765 Time1=r0&i0 Time2=r0&i0
Value 21: Func1=r231&i231 Func2=r10946&i10946 Time1=r0&i0 Time2=r9766&i0
Value 22: Func1=r253&i253 Func2=r17711&i17711 Time1=r0&i0 Time2=r9765&i0
Value 23: Func1=r276&i276 Func2=r28657&i28657 Time1=r0&i0 Time2=r9766&i0
Value 24: Func1=r300&i300 Func2=r46368&i46368 Time1=r0&i0 Time2=r19531&i0
Value 25: Func1=r325&i325 Func2=r75025&i75025 Time1=r0&i0 Time2=r19531&i0
Value 26: Func1=r351&i351 Func2=r121393&i121393 Time1=r0&i0 Time2=r39063&i0
Value 27: Func1=r378&i378 Func2=r196418&i196418 Time1=r0&i0 Time2=r58593&i0
Value 28: Func1=r406&i406 Func2=r317811&i317811 Time1=r0&i0 Time2=r87891&i0
Value 29: Func1=r435&i435 Func2=r514229&i514229 Time1=r0&i0 Time2=r136718&i0
Value 30: Func1=r465&i465 Func2=r832040&i832040 Time1=r0&i0 Time2=r214844&i0
Value 31: Func1=r496&i496 Func2=r1346269&i1346269 Time1=r0&i0 Time2=r390625&i0
Value 32: Func1=r528&i528 Func2=r2178309&i2178309 Time1=r0&i0 Time2=r644531&i0
Value 33: Func1=r561&i561 Func2=r3524578&i3524578 Time1=r0&i0 Time2=r927734&i0
Value 34: Func1=r595&i595 Func2=r5702887&i5702887 Time1=r0&i0 Time2=r1708984&i0
Value 35: Func1=r630&i630 Func2=r9227465&i9227465 Time1=r0&i0 Time2=r2441407&i0
Value 36: Func1=r666&i666 Func2=r14930352&i14930352 Time1=r0&i0 Time2=r4531250&i0
Value 37: Func1=r703&i703 Func2=r24157817&i24157817 Time1=r0&i0 Time2=r7148438&i0
Value 38: Func1=r741&i741 Func2=r39088169&i39088169 Time1=r0&i0 Time2=r11435547&i0
Value 39: Func1=r780&i780 Func2=r63245986&i63245986 Time1=r0&i0 Time2=r17226563&i0
Value 40: Func1=r820&i820 Func2=r102334155&i102334155 Time1=r9765&i0 Time2=r29960938&i0
Value 41: Func1=r861&i861 Func2=r165580141&i165580141 Time1=r0&i0 Time2=r45234375&i0
Value 42: Func1=r903&i903 Func2=r267914296&i267914296 Time1=r0&i0 Time2=r72919921&i0
Value 43: Func1=r946&i946 Func2=r433494437&i433494437 Time1=r0&i0 Time2=r118759766&i0
Value 44: Func1=r990&i990 Func2=r701408733&i701408733 Time1=r0&i0 Time2=r194355469&i0
Value 45: Func1=r1035&i1035 Func2=r1134903170&i1134903170 Time1=r0&i0 Time2=r310996093&i0

Iterativ ist wirklich schneller Very Happy

Übersicht

BlitzMax, BlitzMax NG

Beginners-Corner

Nach Oben

BlitzBasic Portal

BPS #8: Rekursiv zu Iterativ

Xeres

Betreff: BPS #8: Rekursiv zu Iterativ

BlitzMoritz

Betreff: Re: BPS #8: Rekursiv zu Iterativ

BlitzMoritz

BladeRunner

Xaymar