4

在这里问它很痛苦。确实如此。每次我徒劳地寻找问题的答案时，我都会看到它。嘲讽我。堆栈溢出。

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

(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))))))))))))
4

2 回答 2

14

在延续传递风格中，不是通过递归调用来扩展堆栈空间，而是在执行延续的环境中构建递归定义的 lambdas ......换句话说，内存在某处被用完。例如，对于一个简单的阶乘算法，您通常会这样写：

(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并且cont每次递归调用factorial. 由于cont它本身是一个带有环境的 lambda，因此您可以看到最终将如何消耗内存，因为每个 lambda-continuation 都需要在其环境中存储上一次调用 factorial 的 lambda ...这会创建一个递归定义的 lambda-continuation有一个环境，它基本上是一个递归列表，列出了通过递归调用factorial.

查看延续传递风格的一种方法是，虽然您基本上已将函数调用机制转换为尾递归方法，但延续本身的实际定义本质上是递归的，因此您并没有真正删除递归-算法本身的性质......换句话说，评估在尾递归调用上建立的延续需要评估它内部的递归定义的延续，它本身内部还有另一个递归定义的延续，等等。 lambda-continuations 最终看起来像一个 list-of-a-list-of-a-list 等。将所有这些递归定义存储在 lambda-continuation 的环境中需要内存，所以无论你是否在消耗空间通过正常的递归调用约定堆栈，或者通过在每个 lambda-continuation 中存储递归定义的环境来消耗内存空间，无论哪种方式你最终都会耗尽空间。

于 2011-07-25T19:43:54.497 回答
3

CPS 不会帮助您提高内存效率，因为通过执行它，您只是用匿名函数替换堆栈帧。如果您希望程序使用更少的内存，请尝试回溯搜索（但请注意，您必须小心避免无限移动序列）。

于 2011-07-25T17:22:18.737 回答