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.

waldinator

Praktikant

  • "waldinator" started this thread

Posts: 11

Date of registration: Nov 24th 2009

1

Sunday, December 6th 2009, 8:04pm

Rekursion bei Scheme

Hallo leute,
ich bin mal wieder am Verzweifeln bei den Schemeaufgaben und habe gemerkt, dass ich diese Rekursion bei Scheme immer noch nciht wirklich verstanden hab :/ Wenn das Programm nicht rekursiv arbeiten würde, dann wären die Aufgabe ja echt ein Klacks, leider ist das ja nicht so :/
Also wollte ich mal fragen ob mir jemand mal richtig erklären könnte wie das dort funktioniert :)
Das aus den früheren Programmen hab ich ja eigentlich verstanden (denke ich) z.b. dieses facultätsprogramm.
[codefile](define (fac n)
(if (< n 2) 1
(* n (fac (- n 1)))))[/codefile]
aber wie ist das bei diesem Programm, das 2 Listen (die Mengen darstellen sollen) voneinander abzieht.

[codefile](define (minus-list-set set1 set2)
(cond ((null? set1) '())
((null? set2) set1)
(else
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2) (minus-list-set (cdr set1) (cdr set2)))
((< x1 x2) (cons x1 (minus-list-set (cdr set1) set2)))
(else (minus-list-set set1 (cdr set2)))))))) [/codefile]
(minus-list-set '(1 2 3 4 5 6 7 8 9 10) '(2 4 7 9 12)) --->(1 3 5 6 8 10)

Wo speichert das Programm die neue Liste? Irgendwie in sich selber oder so? :/ ich komme damit nicht klar.
und warum funktioniert mein Programm nicht, das eine Liste aus den Elementen bilden soll, die in beiden Listen vorhanden sind:

[codefile]
(define (intersection-list-set set1 set2)
(cond ((null? set1) '())
((null? set2) '())
(else
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2)(cons x1 (intersection-list-set (cdr x1) (cdr x2))))
((< x1 x2)(intersection-list-set (cdr set1) set2))
(else (intersection-list-set set1 (cdr set2))))))))[/codefile]
hab das ja praktisch genau so geschrieben wie das andere Programm :/
hoffentlich kann mir jemand helfen...
  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

2

Sunday, December 6th 2009, 8:36pm

RE: Rekursion bei Scheme

Quoted from "waldinator"

Wo speichert das Programm die neue Liste? Irgendwie in sich selber oder so? :/ ich komme damit nicht klar.

Wie die neue Liste durch Rekursion entsteht, kannst Du Dir leicht klar machen, wenn Du einmal den Ablauf des Programms aufschreibst. Am Bespiel der Fakultätsberechnung für den Wert 5 sieht das so aus:

(fac 5)
-> (* 5 (fac 4))
-> (* 5 (* 4 (fac 3)))
-> (* 5 (* 4 (* 3 (fac 2))))
-> (* 5 (* 4 (* 3 (* 2 (fac 1)))))
-> (Abbruchbedingung) (* 5 (* 4 (* 3 (* 2 1))))
-> (* 5 (* 4 (* 3 2)))
-> (* 5 (* 4 6))
-> (* 5 24)
-> 120

Mit den Listen wird der Schreibaufwand für diese Darstellung zwar noch größer, das Prinzip ist aber dasselbe.
  • Send private message

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

3

Sunday, December 6th 2009, 9:12pm

RE: Rekursion bei Scheme

Hallo,

Du hast nur zwei kleine Fehler in Zeile 6 (wißt ihr eigentlich, wie man den Debugger benutzt ...?)

Viele Grüße
Carsten
  • Send private message

Schokoholic

Fritz

  • "Schokoholic" is male

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

4

Sunday, December 6th 2009, 9:20pm

RE: Rekursion bei Scheme

Quoted from "waldinator"

aber wie ist das bei diesem Programm, das 2 Listen (die Mengen darstellen sollen) voneinander abzieht.

[codefile](define (minus-list-set set1 set2)
(cond ((null? set1) '())
((null? set2) set1)
(else
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2) (minus-list-set (cdr set1) (cdr set2)))
((< x1 x2) (cons x1 (minus-list-set (cdr set1) set2)))
(else (minus-list-set set1 (cdr set2)))))))) [/codefile]

Wichtig ist hier, dass das Programm nur mit aufsteigend sortierten Listen funktioniert.

Im Prinzip geht man immer folgendermaßen vor, wenn man ein Problem rekursiv lösen will. Als erstes hat man ein Problem gegeben. Das kann eine Zahl n sein, deren Fakultät man berechnen will, oder es können zwei Listen sein, bei denen man eine von der anderen abziehen will, oder es können irgendwelche anderen Daten sein. Das prinzipielle Vorgehen ist dann (am besten im Kopf, nicht an der Tastatur):
  1. Es gibt Fälle, in denen das Problem trivial lösbar ist. Diese finden und merken.
    Beispiel 1: (fak 0) => 1
    Beispiel 2: (minus-list-set '() eineliste) => '() und (minus-list-set eineliste '()) => eineliste (einfach durch Überlegungen, wie die einfachsten Fälle bei der Mengensubtraktion aussehen)
  2. Wege suchen, um das Problem so zu "verkleinern", dass man irgendwann bei den trivialen Fällen ankommt.
    Beispiel 1: bei fak ist das "verkleinern" zum Beispiel minus 1 rechnen
    Beispiel 2: bei den Listen könnte man naheliegenderweise Elemente entfernen
  3. Einen möglichst einfachen Weg finden um aus dem aktuellen Problem und der Lösung(!) des verkleinerten Problems eine Lösung des aktuellen Problems zu basteln.
    Beispiel 1: bei fak nimmt man z.B. das aktuelle Problem n mit der Lösung des verkleinerten Problems (fak (- n 1)) mal und erhält so die Lösung für (fak n).
    Beispiel 2: Ein möglichst einfacher Weg wäre es, immer nur das jeweils erste Element der beiden Listen anzuschauen und zu überlegen, ob man allein dadurch einen Teil der Lösung bekommt. Mit ein wenig nachdenken wird man schnell zu dem Ergebnis kommen, dass das nur möglich ist, wenn beide Listen sortiert sind. Dann weiß man z.B., dass wenn das erste Element von set2 eine 5 ist, keine Elemente mehr vorkommen können, die kleiner als 5 sind. Ist also das erste Element von set1 also kleiner als 5, muss es also auf jeden Fall auch im Ergebnis stehen. Das Schicksal des ersten Elements von set1 ist nun also geklärt, d.h. wenn man es aus set1 entfernt haben wir das Problem um einen Schritt verkleinert. Nun kommt der wichtige Schritt: aus dem ersten Element von set1 und der Lösung(!) (berechnet mit minus-list-set) des verkleinerten Problems (ohne das erste Element von set1), setzen wir mit cons eine Liste (das Ergebnis) zusammen. Das geht, weil wir wissen, dass minus-list-set immer eine Liste (bzw. eine Menge) zurückgibt (per Definition!).
    Die anderen zwei Fälle funktionieren analog dazu.

EDIT: Schritt 2 und 3 gehen natürlich Hand in Hand. Wenn man keinen Weg findet, aus Teillösung und Problem die Gesamtlösung zusammenzusetzen muss man sich vielleicht in Schritt 2 eine andere Vereinfachung suchen.

Quoted from "waldinator"

Wo speichert das Programm die neue Liste? Irgendwie in sich selber oder so? :/ ich komme damit nicht klar.

Das Ergebnis wird also nirgends "gespeichert" sondern quasi schrittweise "von unten nach oben" (sprich, vom trivialen Fall zur Gesamtlösung) zusammengesetzt, wie man es z.B. im Post von Bastian sehr schön sehen kann.

Gruß,
Fritz

Edith sagt: "Typos!"

This post has been edited 2 times, last edit by "Schokoholic" (Dec 6th 2009, 9:25pm)

  • Send private message