wil*_*lem 2 lisp scheme tail-recursion
我有以下数学表达式:
; f(n) = f(n - 1) + f(n - 2) where n >= 2
; f(n) = n where n < 2`
我将其转换为正常的递归LISP调用:
(define (f n)
(cond ((< n 2) n)
(else (+ (f (- n 1))
(f (- n 2))))))
我如何将上述内容转换为尾递归过程？我不习惯函数式编程,所以我有点挣扎.
(以下代码在Racket中编写和测试.)
从天真的版本开始:
;; fib : nat -> nat
(define (fib n)
(cond [(= n 0) 0]
[(= n 1) 1]
[else (+ (fib (- n 1)) (fib (- n 2)))]))
在我们开发新版本时,我们可以使用它test来查看它们是否与初始版本一致fib(至少在数字0到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))))
首先,能够实现其他一切的关键观察是,当我们计算时(fib N),我们已经计算了(fib (- N 1))......但我们丢弃了它,因此我们必须在以后再次重新计算它.这就是天真fib是指数时间的原因!我们可以通过保留它来做得更好,例如使用返回列表的辅助函数:
;; 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
该fib2list函数在1处停止,因此将fib20作为特殊(但不感兴趣)的情况处理.
我们可以在延续传递样式(CPS)中重写它以使其尾递归:
;; 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
现在,不是进行非尾递归调用,fib3k而是使用扩展的继续调用自身来获取列表结果.延续k的(fib3k N k)被调用列表相当于一个(list (fib (- N 1)) (fib N)).(因此,如果第一个参数是(- n 1),则连续参数被命名resultN-1,等等)
为了开始一切,我们提供一个初始延续,取得结果resultN; 第二个元素是等于(fib N),所以我们返回.
当然,没有理由把包装作为清单; 我们可以让延续有两个参数:
;; 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
请注意,程序中只有两种延续变量 - 它们对应lambda于代码中的两次出现.这是最初的延续,并且有一种扩展现有延续的方法.使用此观察,我们可以将continuation函数转换为上下文数据结构:
;; A context5 is either
;; - (initial-context)
;; - (extend-context context5)
(struct initial-context ())
(struct extend-context (inner))
现在我们使用上下文构造函数替换创建延续函数(即lambdas)的表达式,并使用新的显式函数替换应用continuation函数的(单个)站点,该函数执行先前由两个表达式完成的工作:apply-context5lambda
;; 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
(当编译器这样做时,他们称之为去功能化或闭包转换,他们这样做是为了将间接跳转变为直接跳转.)
在这一点上,context数据类型非常无聊是非常明显的.事实上,它在代数上等同于自然数!(自然数是零或自然数的后继.)因此,让我们只更改上下文数据类型以使用自然数而不是一些堆分配结构.
;; 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
但是现在显而易见的是,fib6ctx只要计数到1 ctx,就会计数n.特别是:
(fib6ctx N M) = (fib6ctx 1 (+ N M -1))
= (apply-context6 (+ N M -1) 0 1)
所以
(fib6ctx N 0) = (apply-context6 (+ N -1) 0 1)
所以我们可以fib6ctx完全摆脱.
;; 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
这是Fibonacci的传统迭代版本,除了apply-context7通常被调用fib-iter或类似的东西,并且大多数版本计数而不是向下并希望他们得到正确的比较,因此他们不会得到一个一个错误.