BPS #8: Rekursiv zu Iterativ

Übersicht BlitzBasic Beginners-Corner

Neue Antwort erstellen

Xeres

Moderator

Betreff: BPS #8: Rekursiv zu Iterativ

BeitragFr, Mai 13, 2011 11:45
Antworten mit Zitat
Benutzer-Profile anzeigen
user posted image

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%(x%)
    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%(x%)
    Local y% = 1, i%
    For i = 0 To x-1
        y = 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.
Local i%
For i = 0 To 15
    Print i + " rekursiv: " + bsp_rekursiv(i) + " iterativ: " + bsp_iterativ(i)
Next


;Beispielfunktionen
Function bsp_rekursiv%(n%)
    If n <= 0 Return 0
    Return 1 + bsp_rekursiv(n - 1)
End Function

Function bsp_iterativ%(n%)
    Local a%, i%
    For i = 1 To n
        a = 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%(n%)
    If n = 0 Return n
    Return n + func1_rekursiv(n - 1)
End Function


Funktion 2 (schwer)
Code: [AUSKLAPPEN]
Function fib_rekursiv%(x%)
    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
T
HERE 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 6-mal bearbeitet

Eingeproggt

BeitragFr, Mai 13, 2011 12:04
Antworten mit Zitat
Benutzer-Profile anzeigen
Is schon nicht mehr unbedingt Stoff für Beginner, aber um die Verwirrung perfekt zu machen, 2 Anmerkungen:
-) Bevor die rekursive Variante zu nem Stack-Overflow führt, wird sie die Integer-Grenzen von BB sprengen.
-) Apropos Grenzen von BB... dein Beispielcode ist BMax, das sollte man eventuel dazu sagen.

mfG, Christoph.
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

Xeres

Moderator

BeitragFr, Mai 13, 2011 12:14
Antworten mit Zitat
Benutzer-Profile anzeigen
Danke für den Hinweis; Code verbessert.
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
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

Lador

BeitragFr, Mai 13, 2011 15:23
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich finde, jede Methode, die etwas zurückgibt, sollte auch entsprechend gekennzeichnet sein (Wieso kommt da eigentlich keine Fehlermeldung? Kommt die nur bei BlitzMax Strict/SuperStrict?). Also mit %, da sie ja einen Integer zurückgibt. Ansonsten finde ich aber das Thema sehr gut, da rekursive Methoden ja eigentlich auch zu den Grundlagen der Programmierung gehören, braucht man in Schule und Studium ja auch sehr oft.

MFG Lador
Mein aktuelles Projekt:
2D-Rollenspiel "Iliran"
Screenshot | Worklog
Fortschritt: ca. 70%

Xeres

Moderator

BeitragFr, Mai 13, 2011 15:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Es sind a) Funktionen, keine Methoden und b) ist es BlitzBasic, was bedeutet, das Variablen und Funktionen - wenn nicht anders angegeben - Integer verwenden.
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
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

Lador

BeitragFr, Mai 13, 2011 16:17
Antworten mit Zitat
Benutzer-Profile anzeigen
Sorry, kam gerade frisch aus dem Informatikunterricht, da heißt alles Methode. Abgesehen davon gibt es in BlitzBasic sowieso keinen wirklichen Unterschied zwischen Funktionen und Methoden, soweit ich weiß.

Hab doch auch nie behauptet, dass es nicht BlitzBasic sei, oder? Ich finde, es gehört einfach zum guten Programmierstil, der Vollständigkeit halber Integer mit anzugeben. Wenn du das anders siehst, gerne. Sind ja deine BPS.

MFG Lador
Mein aktuelles Projekt:
2D-Rollenspiel "Iliran"
Screenshot | Worklog
Fortschritt: ca. 70%

Xeres

Moderator

BeitragFr, Mai 13, 2011 16:31
Antworten mit Zitat
Benutzer-Profile anzeigen
Nein, es sind nicht meine BPS - und ja: Es wäre sicherlich besser immer alles ordentlich zu Deklarieren. Da ohnehin alles automatisch Integer wird, mache ich mir die Mühe gewöhnlich nicht. Aber bitte, wir haben's ja.
(Generell ist der fehlende Zwang ein zweischneidiges Schwert der es für Anfänger nicht unbedingt einfacher macht... aber das ist ein anderes Thema.)
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
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Neue Antwort erstellen


Übersicht BlitzBasic Beginners-Corner

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group