Wikipedia:SchemeÄndere nie ein Variable
Bei
del.icio.us/tag/scheme
habe ich einen Link zum Artikel
Mastering recursive programming
gefunden, in dem Jonathan Bartlett
beschreibt, wie sich Rekursion in einer imperativen Programmiersprache nutzen lässt.
Während er am Anfang ein Paar
Scheme
und C
Rekursionsbeispiele aufzeigt und zum Schluss die Speicheroptimierung durch tail-call
aufzeigt, geht er im Mittelteil darauf ein, wie man überprüfbare und richtige Programme - mit Hilfe der Rekursion - schreibt.
Bugs gehören zum täglichen Leben eines Programmierers und sie treten sogar in kleinen Schleifen oder Funktionen auf. Der Hauptgrund liegt in der Statusänderung von Variablen. Abhängig vom Status entstehen unterschiedliche Ergebnisse, so dass sich die ganze Komplexität gar nicht überblicken lässt.
Es gibt eine Lösung, mit einer einzigen Regel: Weise einer Variable einen Wert zu und ÄNDERE SIE NIE!
Imperative, prozedurale und die OO
Programmierung bauen aber gerade auf die Zuweisung und Änderung von Variablen auf. Jedoch ist gerade die Statusänderung eines der Gründe für Programmierfehler.
In drei Situationen werden Variablen verändert:
Im Artikel wird eine Beispielfunktion in eine rekursive Funktion umgewandelt und es wird auch aufgezeigt, wie sich diese rekursive Funktion auf Korrektheit überprüfen lässt.
Zum Schluss geht Jonathan Bartlett
noch auf tail-recursive Funktionen ein, die den Speicherbedarf des Stacks, unabhängig von der tiefe der Aufrufe, konstant halten. Hierzu hat er ein Assembler Beispiel, jedoch erwähnt er auch, dass
GCC
in bestimmten Konstellationen eine tail-call
Optimierung anwendet.
... je komplexer die Programme werden, um so eher bietet die rekursive Programmierung dem Programmierer eine Möglichkeit den Code so zu organisieren, dass er wartbar und logisch konsistent ist.