延续传递风格使事物尾递归？

Question

在这里问它很痛.确实如此.每次我徒劳地寻找我的烦恼的答案,我都会看到它.嘲弄我.堆栈溢出.

无论如何,一些地狱般的影响使我试图解决河内塔.我的第一个解决方案是不完整的,因为如果运行太多磁盘会导致内存错误:

(define hanoi
  (lambda (n from to other)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       '())
      (else
       (append (hanoi (- n 1)
              from
              other
              to)
           `((,from ,to))
           (hanoi (- n 1)
              other
              to
              from))))))

我在某处读到延续传递方式可以解决问题.但是,这也无济于事:

(define hanoi_cps
  (lambda (n from to other c)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       (c '()))
      (else
       (hanoi_cps (- n 1)
              from
              other
              to
              (lambda (x)
            ((lambda (w)
               (w `((,from ,to))))
             (lambda (y)
               (hanoi_cps (- n 1)
                      other
                      to
                      from
                      (lambda (z)
                    (c (append x y z))))))))))))

Answer 1

在继续传递样式中,而不是使用递归调用扩展堆栈空间,而是在执行连续执行的环境中构建递归定义的lambda ...换句话说,内存在沿线的某处使用.例如,使用简单的因子算法,您通常会将其写为:

(define (factorial x)
    (cond ((eq? x 0) 1))
          ((eq? x 1) 1))
          (else (* x (factorial (- x 1))))))

使用此递归定义factorial,堆栈空间将用于保存在每个递归函数调用中执行的延迟乘法运算的参数.相同函数的延续传递版本如下所示:

(define (factorial x cont)
    (cond ((eq? x 0) (cont 1))
          ((eq? x 1) (cont 1))
          (else (factorial (- x 1) (lambda (y) (cont (* x y)))))))

之前消耗堆栈空间的东西现在被匿名lambda的环境耗尽了.在这种情况下,lambda的环境正在填充为了解析每个递归调用的值x和所需的值.由于它本身就是一个带有环境的lambda,你可以看到内存最终将如何消耗,因为每个lambda-continuation需要在其环境中存储从前一次调用factorial的lambda ...这会创建一个递归定义的lambda-continuation,有一个环境基本上是通过递归调用累积的所有延续的递归列表. contfactorialcontfactorial

查看continuation-passing风格的一种方法是,虽然你基本上将函数调用机制转换为尾递归方法,但是continuation本身的实际定义本质上是递归的,所以你并没有真正去除递归 - 算法本身的特征...换句话说,评估在尾递归调用上构建的延续需要在其内部评估递归定义的延续,其本身在其内部具有另一个递归定义的延续,等等. lambda-continuations最终看起来像列表列表等等.在lambda-continuation的环境中存储所有这些递归定义需要内存,所以无论你是否消耗了空间通过正常的递归调用约定堆栈,或者通过在每个lambda-continuation中存储递归定义的环境来消耗内存空间,无论哪种方式,你最终都会耗尽空间.