Fachrat Informatik - Forum

Um die Idee der beiden Funktionen zu verstehen, solltest Du Dir vielleicht einmal die Abarbeitung einer Beispieleingabe anzeigen lassen. Meine Scheme-Zeit liegt schon etwas zurück, ich glaube der nötige Befehl dazu hieß TRACE, vllt findest Du dazu ja etwas.

Die erste Version von rev scheint so zu arbeiten: In Akku wird nach und nach die umgekehrte Liste aufgebaut, durch (rev L '())) übergibt man der Unterfunktion rev eine Liste und einen leeren Akkumulator.
Diese Unterfunktion nimmt dann jeweils ein Element der übergebenen Liste L, und hängt es an das Ende der Akkumulatorliste; das geschieht solange, bis alle Elemente von L eingefügt wurden.
Der rekursive Teil steht ganz am Ende der Funktion (rev L akku), dahinter müssen keine Berechnungen mehr durchgeführt werden: man "schiebt" quasi ein Teilergebnis in einem Akkumulator (von lat. akkumulare: ansammeln, aufhäufen) vor sich her, und erweitert dieses Schritt für Schritt durch einen rekursiven Aufruf von rev.
Wobei zu beachten ist, dass rev in diesem Fall eigentlich einen iterativen Prozess erzeugen dürfte, denn schließlich übergibt es alle zur weiteren Berechnung nötigen Daten an sein rekursiv aufgerufenes Kind, und tut danach selbst nichts mehr (man kann also direkt aus der Funktion herausspringen, und die Berechnung bei der Kindfunktion fortsetzen). Ich denke, das versteht man dann auch unter einer Endrekursion.

->["hallo", ""]
->["allo", "h"]
->["llo", "ah"]
...>["", "ollah"]
->"ollah" zurückliefern

Anders geht hier die zweite Variante von rev vor. Die hängt nämlich mit (append (rev (cdr L)) (list (car L))))) das erste Element der umzukehrenden Liste an die umgedrehte Version der Restliste. Diese umgedrehte Version der restlichen Liste berechnet es dann rekursiv... in allen folgenden Rekursionen passiert natürlich das gleiche. In jeder aufgerufenen Instanz der Rekursion wird sozusagen darauf "gewartet", dass ein Teilergebnis von jemand anders berechnet wird...erst wenn dieses Teilergebnis da ist, kann eine Instanz sein eigenes Element dahinter hängen, und das Ergebnis als Teilergebnis der Instanz überreichen, von der sie selbst aufgerufen wurde:

->["hallo", ""]
->["allo" rückwärts] + "h"
---->["llo" rückwärts] + "a"
-------> ["lo" rückwärts] + "l"
----------> ["o" rückwärts] + "l"
----------------> ["" rückwärts] + "o"
----------------> liefert "" zurück
----------------> liefert "" + "o" = "o" zurück
----------> liefert "o" + "ol" = "ol" zurück
-------> liefert "ol" + "l" = "oll" zurück
----> liefert "oll" + "a" = "olla" zurück
-> liefert "olla" + "h" = "ollah" zurück

Dieses "Warten auf Teilergebnisse, die selbst wieder von der Funktion rekursiv erzeugt werden" ist es, was Dir Deine rekursiven Prozesse erzeugt (der Begriff "natürliche Rekursion" sagt mir erstmal nichts, allerdings dürfte es sich hierbei wahrscheinlich um das selbe handeln). Wenn Du erreichen kannst, dass Du ein Teilergebnis Schritt für Schritt, "akkumulierend", zum vollständigen Ergebnis erweitern kannst, ohne dass Du hierfür auf Ergebnisse anderer Berechnungen angewiesen bist, erzeugst Du somit einen iterativen Prozess.

Hoffe, diese grobe Erklärung konnte weiterhelfen ... ansonsten schau doch mal in der Wikipedia nach , da gabs auch ganz gute und verständliche Artikel zu dem Thema, soweit ich mich erinnern kann...

Im Endeffekt ist der Akku nichts anderes als eine Iteration. Hier wird die Variable immer gleich weitergereicht. Bei der Rekursion wird alles erst am Ende zusammen gesetzt, sobald alle Berechnungen abgeschlossen wurden.

http://mitpress.mit.edu/sicp/

Hier einfach nach zu lesen.