Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.
  • "schemeneuling" started this thread

Posts: 1

Date of registration: May 1st 2007

1

Tuesday, May 1st 2007, 8:13pm

Probleme mit Scheme [Anfänger]

Hallo,

ich habe ein paar Probleme mit der Programmiersprache und benötige eure hilfe.

Ich weiß nicht was ein Akkumulator (Akku) bewirkt.

Was ist der Unterschied zwischen einer natürlichen Rekursion und einer doppelten Rekursion?


Ich habe hier mal ein Programm mit dem akku verfahren könntet ihr mir das mal bitte erklären:

(rev L) /kehrt die Reihenfolge der Elemente einer Liste um.

(define (rev L)
(define (rev L akku)
(if (null? L)
akku
(rev (cdr L) (cons (car L) akku))))
(rev L '()))

---------------------mit der natürlichen Rekursion--------------------

(define (rev L)
(if (null? L)
'()
(append (rev (cdr L)) (list (car L)))))

__________________________________________________



Könntet ihr mir auch diese Endrekursion erklären mit akku wie das funktioniert?

Würde mich freuen, wenn ihr mir helfen könntet.

MfG
schemeneuling

This post has been edited 1 times, last edit by "schemeneuling" (May 1st 2007, 8:14pm)


DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

2

Wednesday, May 2nd 2007, 7:10pm

RE: Probleme mit Scheme [Anfänger]

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...

This post has been edited 3 times, last edit by "DrChaotica" (May 2nd 2007, 7:26pm)


hyperion

Erfahrener Schreiberling

  • "hyperion" is male

Posts: 422

Date of registration: Oct 8th 2004

3

Wednesday, May 2nd 2007, 7:23pm

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.
"Der Klügere gibt nach! Eine traurige Wahrheit, sie begründet die Weltherrschaft der Dummheit." --Marie von Ebner-Eschenbach