Tail Rekursive Zählfunktion in Schema

Question

Die Funktion soll tail-rekursiv sein und von 1 bis zur angegebenen Zahl zählen. Ich denke, ich bin ziemlich nah dran. Hier ist, was ich habe:

(define (countup l) 
    (if (= 1 l) 
     (list l) 
     (list 
     (countup (- l 1)) 
     l 
     ) 
    ) 
) 

Allerdings gibt dies offensichtlich eine Liste mit verschachtelten Listen. Ich habe versucht, die Append-Funktion anstelle der zweiten Liste ohne Erfolg zu verwenden. Irgendeine Anleitung?

Answer 1

Hier ist eine falsche Lösung:

(define (countup n) 
    (define (help i) 
    (if (<= i n) 
     (cons i (help (+ i 1))) 
     '())) 
    (help 1)) 

Diese Lösung:

• verwendet eine Hilfsfunktion
• rekursiv über die Zahlen von 1 bis n, cons-ing sie auf eine ständig wachsende Liste

Warum ist das falsch? Es ist nicht wirklich tail-recursive, weil es eine große lange Linie von cons Aufrufen erstellt, die nicht sofort ausgewertet werden können. Dies würde einen Stapelüberlauf für genügend große Werte von n verursachen.

Hier ist ein besserer Weg, um dieses Problem zu nähern:

(define (countup n) 
    (define (help i nums) 
    (if (> i 0) 
     (help (- i 1) 
       (cons i nums)) 
     nums))) 
    (help n '())) 

Dinge zu beachten:

• diese Lösung ist besser, weil die Anrufe an cons können sofort ausgewertet werden, so dass diese Funktion ist ein Kandidat für Tail-Recursion-Optimierung (TCO), in welchem ​​Fall Stapelspeicherplatz kein Problem sein wird.
• help rekursiv über die Zahlen zurück, vermeidet somit die Notwendigkeit append, zu verwenden, die sehr teuer sein können

Answer 2

Hier eine funktionierende Version des Codes, der eine Liste in der richtigen Reihenfolge zurück (I ersetzt l von n):

(define (countup n) 
(if (= 1 n) 
    (list n) 
    (append (countup (- n 1)) (list n)))) 

Leider gibt es ein Problem mit diesem Stück Code: es ist nicht Schwanz -rekursiv. Der Grund dafür ist, dass der rekursive Aufruf an countup nicht in einer Endposition ist. Es ist nicht in Endposition, weil ich eine Anhängung des Ergebnisses von (countup (- l 1)) mache, so ist der Endanruf append (oder list wenn n = 1) und nicht countup. Dies bedeutet, dass es sich bei diesem Codeabschnitt um eine normale recusus-Funktion, aber um eine tail-rekursive Funktion handelt.

Überprüfen Sie diese link von Wikipedia für ein besseres Beispiel dafür, warum es nicht Tail-Recusrive ist.

Um es rekursiv zu machen, müssten Sie einen Akkumulator haben, der dafür verantwortlich ist, die gezählten Werte zu akkumulieren. Auf diese Weise könnten Sie den rekursiven Funktionsaufruf in eine Endposition setzen. Sehen Sie den Unterschied in der Verbindung, die ich Ihnen gab.

Zögern Sie nicht zu antworten, wenn Sie weitere Informationen benötigen.

Answer 3

Unter der Annahme, dies für eine Übung zu lernen ist und Sie wollen diese Art von Verhalten:

(countup 5) => (list 1 2 3 4 5) 

Hier ist ein Hinweis - in einer Tail-Recursive-Funktion sollte der Aufruf in Tail-Position für sich selbst sein (außer es ist der Randfall).

Da countup keine Zahlenliste verwendet, benötigen Sie eine Akkumulatorfunktion, die eine Zahl und eine Liste übernimmt und eine Liste zurückgibt.

Hier ist eine Vorlage:

;; countup : number -> (listof number) 
(define (countup l) 

    ;; countup-acc : number, (listof number) -> (listof number) 
    (define (countup-acc c ls) 
    (if ... 
     ... 
     (countup-acc ... ...))) 

    (countup-acc l null)) 

Im inneren Ruf zu-acc CountUp, müssen Sie das Argument verändern, wenn dies für die im Randfall geprüft wird, um näher an diesem Rand Fall und Sie müssen das andere Argument ändern, um es näher an das zu bringen, was Sie am Ende zurückgeben möchten.

Answer 4

Sie sollten eine Hilfskomponente zum Implementieren einer tail-rekursiven Lösung für dieses Problem (eine "Schleifen" -Funktion) verwenden und einen zusätzlichen Parameter zum Akkumulieren der Antwort verwenden. Etwas wie dieses:

(define (countup n) 
    (loop n '())) 

(define (loop i acc) 
    (if (zero? i) 
     acc 
     (loop (sub1 i) (cons i acc)))) 

Alternativ könnten Sie einen benannten Let verwenden. So oder so, ist die Lösung tail-rekursive und ein Parameter zum Ansammeln von Werten verwendet wird, feststellen, dass die Rekursion vorrückt rückwärts, bei n beginnend und zurück zu 0, consing jeden Wert wiederum am Anfang der Liste zu zählen:

(define (countup n) 
    (let loop ((i n) 
      (acc '())) 
    (if (zero? i) 
     acc 
     (loop (sub1 i) (cons i acc)))))