Wie lässt sich das folgende Verfahren in eine rekursive Prozedur am Ende übersetzen?

Question

Ich habe den folgenden mathematischen Ausdruck:

; f(n) = f(n - 1) + f(n - 2)   where n >= 2 
; f(n) = n where n < 2`

Das habe ich in einen normalen rekursiven LISP-Aufruf übersetzt:

(define (f n)
  (cond ((< n 2) n)
        (else (+ (f (- n 1))
                 (f (- n 2))))))

Wie würde ich das oben genannte Verfahren in ein Tail-Recursive-Verfahren übersetzen? Ich bin nicht an die funktionale Programmierung gewöhnt, also habe ich ein wenig zu kämpfen.

Answer 1

(Der folgende Code ist geschrieben und getestet in Schläger .)

Beginnen Sie mit der naiven Version:

;; fib : nat -> nat
(define (fib n)
  (cond [(= n 0) 0]
        [(= n 1) 1]
        [else (+ (fib (- n 1)) (fib (- n 2)))]))

Wenn wir neue Versionen entwickeln, können wir test um zu sehen, ob sie mit der ursprünglichen fib (zumindest für die Zahlen 0 bis 9).

;; test : (nat -> nat) -> boolean
;; Check that the given function agrees with fib on 0 through 9
(define (test f)
  (for/and ([i (in-range 10)])
    (= (f i) (fib i))))

Erstens: Die entscheidende Beobachtung, die alles andere ermöglicht, ist, dass wir bei der Berechnung von (fib N) haben wir berechnet (fib (- N 1)) ... aber wir verwerfen sie und müssen sie später wieder neu berechnen. Deshalb ist naiv fib ist Exponentialzeit! Wir können es besser machen, indem wir es in der Nähe behalten, zum Beispiel mit einer Hilfsfunktion, die eine Liste zurückgibt:

;; fib2list : nat -> (list nat nat)
;; (fib2list N) = (list (fib (- N 1)) (fib N))
(define (fib2list n)
  (cond [(= n 1) (list 0 1)]
        [else (let ([resultN-1 (fib2list (- n 1))])
                (let ([fibN-2 (first resultN-1)]
                      [fibN-1 (second resultN-1)])
                  (list fibN-1
                        (+ fibN-2 fibN-1))))]))

;; fib2 : nat -> nat
(define (fib2 n)
  (cond [(= n 0) 0]
        [else (second (fib2list n))]))

(test fib2) ;; => #t

En fib2list Funktion endet bei 1, also fib2 behandelt 0 als einen speziellen (aber uninteressanten) Fall.

Wir können dies im Continuation-Passing-Stil (CPS) umschreiben, um es schwanzrekursiv zu machen:

;; fib3k : nat ((list nat nat) -> nat) -> nat
(define (fib3k n k)
  (cond [(= n 1) (k (list 0 1))]
        [else (fib3k (- n 1)
                     (lambda (resultN-1)
                       (let ([fibN-2 (first resultN-1)]
                             [fibN-1 (second resultN-1)])
                         (k (list fibN-1
                                  (+ fibN-2 fibN-1))))))]))

;; fib3 : nat -> nat
(define (fib3 n)
  (cond [(= n 0) 0]
        [else (fib3k n (lambda (resultN)
                         (let ([fibN-1 (first resultN)]
                               [fibN (second resultN)])
                           fibN)))]))

(test fib3) ;; => #t

Anstatt einen rekursiven Aufruf ohne Ende zu machen, fib3k ruft sich selbst mit einer erweiterten Fortsetzung auf, die ein Listenergebnis annimmt. Die Fortsetzung k de (fib3k N k) wird mit einer Liste aufgerufen, die (list (fib (- N 1)) (fib N)) . (Wenn also das erste Argument (- n 1) wird das Fortsetzungsargument mit resultN-1 , usw.)

Um alles zu beginnen, stellen wir eine anfängliche Fortsetzung zur Verfügung, die das Ergebnis resultN ; das zweite Element ist gleich (fib N) also geben wir das zurück.

Natürlich gibt es keinen Grund, die Dinge weiterhin als Liste zu verpacken; wir können die Fortsetzung einfach mit zwei Argumenten versehen:

;; fib4k : nat (nat nat -> nat) -> nat
(define (fib4k n k)
  (cond [(= n 1) (k 0 1)]
        [else (fib4k (- n 1)
                     (lambda (fibN-2 fibN-1)
                       (k fibN-1
                          (+ fibN-2 fibN-1))))]))

;; fib4 : nat -> nat
(define (fib4 n)
  (cond [(= n 0) 0]
        [else (fib4k n (lambda (fibN-1 fibN) fibN))]))

(test fib4) ;; => #t

Beachten Sie, dass es nur zwei Varianten der Fortsetzung im Programm---sie entsprechen den beiden Vorkommen von lambda im Code. Es gibt die ursprüngliche Fortsetzung und es gibt eine einzige Möglichkeit, eine bestehende Fortsetzung zu erweitern. Mit dieser Beobachtung können wir die Fortsetzungsfunktionen in eine Kontext-Datenstruktur :

;; A context5 is either
;;   - (initial-context)
;;   - (extend-context context5)
(struct initial-context ())
(struct extend-context (inner))

Jetzt ersetzen wir die Ausdrücke, die die Fortsetzungsfunktionen (d.h., die lambda s) mit Verwendungen des Kontext-Konstrukteure und wir ersetzen die (einzige) Seite, die eine Fortsetzungsfunktion anwendet, durch eine neue explizite apply-context5 Funktion, die die Arbeit übernimmt, die zuvor von den beiden lambda Ausdrücke:

;; fib5ctx : nat context5 -> nat
(define (fib5ctx n ctx)
  (cond [(= n 1) (apply-context5 ctx 0 1)]
        [else (fib5ctx (- n 1)
                       (extend-context ctx))]))

;; apply-context5 : context5 nat nat -> nat
(define (apply-context5 ctx a b)
  (match ctx
    [(initial-context)
     b]
    [(extend-context inner-ctx)
     (apply-context5 inner-ctx b (+ a b))]))

;; fib5 : nat -> nat
(define (fib5 n)
  (cond [(= n 0) 0]
        [else (fib5ctx n (initial-context))]))

(test fib5) ;; => #t

(Wenn Compiler dies tun, nennen sie es Defunktionalisierung oder Schließungskonvertierung, und sie tun es, um indirekte Sprünge in direkte Sprünge zu verwandeln.)

An diesem Punkt ist es wirklich offensichtlich, dass die context Datentyp ist total langweilig. In der Tat ist er algebraisch äquivalent zu den natürlichen Zahlen! (Eine natürliche Zahl ist entweder Null oder der Nachfolger einer natürlichen Zahl.) Ändern wir also einfach den Kontextdatentyp so, dass er natürliche Zahlen verwendet und nicht irgendeine Struktur, die auf dem Heap zugewiesen wird.

;; A context6 is just a natural number.

;; fib6ctx : nat context6 -> nat
(define (fib6ctx n ctx)
  (cond [(= n 1) (apply-context6 ctx 0 1)]
        [else (fib6ctx (- n 1)
                       (+ ctx 1))]))

;; apply-context6 : context6 nat nat -> nat
(define (apply-context6 ctx a b)
  (cond [(= ctx 0)
         b]
        [else
         (apply-context6 (- ctx 1) b (+ a b))]))

;; fib6 : nat -> nat
(define (fib6 n)
  (cond [(= n 0) 0]
        [else (fib6ctx n 0)]))

(test fib6) ;; => #t

Aber jetzt ist es offensichtlich, dass fib6ctx zählt nur ctx wenn's drauf ankommt n auf 1 gesenkt werden, und zwar insbesondere:

(fib6ctx N M) = (fib6ctx 1 (+ N M -1))
              = (apply-context6 (+ N M -1) 0 1)

und so

(fib6ctx N 0) = (apply-context6 (+ N -1) 0 1)

So können wir loswerden fib6ctx vollständig.

;; apply-context7 : nat nat nat -> nat
(define (apply-context7 ctx a b)
  (cond [(= ctx 0)
         b]
        [else
         (apply-context7 (- ctx 1) b (+ a b))]))

;; fib7 : nat -> nat
(define (fib7 n)
  (cond [(= n 0) 0]
        [else (apply-context7 (- n 1) 0 1)]))

(test fib7) ;; => #t

Und das ist die traditionelle iterative Version von Fibonacci, mit dem Unterschied, dass apply-context7 wird gewöhnlich als fib-iter oder so ähnlich, und die meisten Versionen zählen aufwärts statt abwärts und hoffen, dass sie den Vergleich richtig hinbekommen, damit sie keinen Fehler bekommen, der um eins versetzt ist.

Answer 2

Sie sprechen von einem etablierten Beispiel für eine rekursive Transformation zur Berechnung der Fibonacci-Zahlen. Eine ausgezeichnete Beschreibung mit Codebeispielen finden Sie unter dieses Kapitel des SICP.