如何用 Scheme 把 FIB 写成尾递归的形式？

如何用 Scheme 把 FIB 写成尾递归的形式？

(define fib-naive ;; 弱智版
(lambda (x)
(cond
[(zero? x) 0]
[(zero? (sub1 x)) 1]
[else (+ (fib-naive (sub1 x)) (fib-naive (- x 2)))])))

;; Chez Scheme Version 8.4
;; Copyright (c) 1985-2011 Cadence Research Systems
;;
;; > (time (fib-naive 42))
;; (time (fib-naive 42))
;; no collections
;; 8932 ms elapsed cpu time
;; 8931 ms elapsed real time
;; 0 bytes allocated
;; 267914296

(define fib-cps-aux ;; Continuation Passing Style: 其实 CPS 是不会变快的。
(lambda (x k)
(cond
[(zero? x) (k x)]
[(zero? (sub1 x)) (k 1)]
[else (fib-cps-aux
(sub1 x)
(lambda (v1)
(fib-cps-aux
(- x 2)
(lambda (v2)
(k (+ v1 v2))))))])))

(define id (lambda (x) x))

(define fib-cps
(lambda (x)
(fib-cps-aux x id)))

;; > (time (fib-cps 42))
;; (time (fib-cps 42))
;; 3290 collections
;; 11746 ms elapsed cpu time, including 235 ms collecting
;; 11746 ms elapsed real time, including 239 ms collecting
;; 27744486208 bytes allocated, including 27742030496 bytes reclaimed
;; 267914296

(define fib-acc ;; Accumulator Passing Style:
;; Racket 标准库中大量函数都是用 named let 形式构造的
(lambda (x)
(let loop ([i x] [m 0] [n 1])
(cond
[(zero? i) m]
[(zero? (sub1 i)) n]
[else (loop (sub1 i) n (+ m n))]))))

;; > (time (fib-acc 42))
;; (time (fib-acc 42))
;; no collections
;; 0 ms elapsed cpu time
;; 0 ms elapsed real time
;; 0 bytes allocated
;; 267914296

;; > (time (fib-acc 100000))
;; (time (fib-acc 100000))
;; 43 collections
;; 622 ms elapsed cpu time, including 4 ms collecting
;; 622 ms elapsed real time, including 8 ms collecting
;; 435519664 bytes allocated, including 428330784 bytes reclaimed

(define fib-sps-aux ;; Store Passing Style: 穷人版的 State Monad
(lambda (n s)
(cond
[(assv n s) => (lambda (pr) `(,(cdr pr) . ,s))]
[(< n 2) `(,n . ((,n . ,n) . ,s))]
[else
(let* ([res2 (fib-sps-aux (- n 2) s)]
[v (car res2)]
[s^ (cdr res2)]
[res1 (fib-sps-aux (sub1 n) s^)]
[u (car res1)]
[s^^ (cdr res1)]
[u+v (+ u v)])
`(,u+v . ((,n . ,u+v) . ,s^^)))])))

(define fib-sps
(lambda (x)
(car (fib-sps-aux x '()))))

;; > (time (fib-sps 42))
;; (time (fib-sps 42))
;; no collections
;; 0 ms elapsed cpu time
;; 0 ms elapsed real time
;; 2704 bytes allocated
;; 267914296

;; > (time (fib-sps 100000))
;; (time (fib-sps 100000))
;; 52 collections
;; 9480 ms elapsed cpu time, including 437 ms collecting
;; 9480 ms elapsed real time, including 435 ms collecting
;; 443672544 bytes allocated, including 5324752 bytes reclaimed