2012-04-08 8 views
4

Ich habe Schwierigkeiten, meinen Kopf um eine Möglichkeit, Rekursion zu verwenden, um eine Liste erstellen und dann diese Liste für den Basisfall zurückgeben. Genauer gesagt gebe ich zwei 32-Bit-Zahlen (x1 und x2) in eine ALU ein und bewerte sie bitweise (über ALU1) und erstelle dann eine Liste der resultierenden Zahl. Mein Basisszenario für diesen Rekursionsalgorithmus ist (null? X1), aber wie kann ich zu diesem Zeitpunkt auf die resultierende Liste zugreifen? Ich weiß, dass Listen im Schema unveränderlich sind, also kann ich nicht einfach eine leere Liste erstellen und die resultierende Liste anhängen. Irgendeine Hilfe? Dies ist meine erste Aufgabe bei der funktionalen Programmierung, also danke im Voraus.Rekursion und Rückgabe einer Liste in Schema

(define ALU-helper 
    (lambda (selection sub x1 x2 carry-in n) 
     (if (null? x1) 
      (________?) 
      (cons 
       (ALU1 selection sub (car x1) (car x2) carry-in n) 
       (ALU-helper selection sub (cdr x1) (cdr x2) carry-in (- n 1)))))) 

Antwort

4

Unter der Annahme, dass sowohl x1 und x2 genau die gleiche Länge haben, sollte diese Arbeit:

(define ALU-helper 
    (lambda (selection sub x1 x2 carry-in n) 
    (if (null? x1) 
     '() 
     (cons 
     (ALU1 selection sub (car x1) (car x2) carry-in n) 
     (ALU-helper selection sub (cdr x1) (cdr x2) carry-in (- n 1)))))) 

Wenn Sie die Rekursion auf einer Eingangsliste Leistung erbringt, und den Aufbau einer neuen Ausgabeliste als ein Ergebnis, der Basisfall ist if (null? lst) dann geben Sie die leere Liste '() zurück. Das liegt daran, dass die resultierende Liste bei jedem Schritt neu erstellt wird, wenn Sie neue Elemente hinzufügen: cons; Wenn Sie das letzte Element der Eingabeliste erreicht haben, haben Sie bereits die Ausgabeliste erstellt, und Sie müssen nur noch den Listenende-Marker '() zurückgeben.

Um es klarer zu sehen, versuchen Sie es mit einem einfacheren Beispiel. Dieses Verfahren kopiert einfach die Liste als Eingabe empfangen:

(define (copy lst) 
    (if (null? lst) 
     '() 
     (cons (car lst) 
      (copy (cdr lst))))) 

(copy '(1 2 3 4 5)) 
> (1 2 3 4 5) 

Beachten Sie, dass wieder das Basismodell ist if (null? lst) und der rekursiven Schritt cons das aktuelle Element der Liste ES (car lst) mit dem Ergebnis der wiederholten auf (cdr lst), the rest of the list. In your case, you perform ALU1`, eine Operation auf den aktuellen Elementen beider Listen, während Sie zwei Listen gleichzeitig durchlaufen.

+0

Danke, natürlich wäre es so einfach!Aus irgendeinem Grund glaubte ich nicht, dass die konstruierte Liste immer noch ausgegeben würde, wenn ich etwas wie '() ausgeben würde (ich dachte, es würde nur'() ausgeben). – Vance

+0

@Vance du bist willkommen! Wenn diese Antwort hilfreich für Sie war, denken Sie bitte daran, sie zu akzeptieren. –

-1

Rekursion - Hier ist eine Metapher.

Stellen Sie sich vor, dass Sie umziehen. Sie haben eine Menge Dinge, die verschoben werden müssen, und Sie müssen sicherstellen, dass es im neuen Zuhause ankommt.

Holen Sie sich ein paar Freunde, um den LKW zu füllen. Sie werden andere Freunde haben, die helfen können. Schlauchleute werden andere Freunde haben usw. Bis es zu einer Person kommt, die ein paar Sachen in den Lastwagen steckt.

Jetzt hat jede Person ein bisschen Papier, um Ihnen zu sagen, was im LKW vor mehr ist. Jetzt haben Sie eine Liste, indem Sie diese Papierschnipsel zusammenziehen.

+0

Danke, ich verstehe die Grundlagen der Rekursion, ich bin nur neu zu Schema und habe Probleme, dies in einer funktionalen Programmierung zu tun. Mein Hauptproblem besteht darin, zu verstehen, wie ich auf diese neue rekursiv erstellte Liste zugreifen kann, ohne diese Liste benennen oder an eine andere Liste anhängen zu können, auf die ich zugreifen kann. – Vance

0

Wahrscheinlich wollen Sie nur die leere Liste, geschrieben null. Also:

(if (null? x1) 
    null 
    (cons ...)) 
0

Hier ist eine Möglichkeit, eine neue Liste von Listen zu erstellen: Im Wesentlichen entgegengesetzte Reihenfolge.

(definieren envers (Lambda (lat) (Ltg ((null? Lat) ‚()) (sonst (Liste (envers (cdr lat)) (Auto lat))) ) ) )