9

我有这个代码：

(define (prog1 x y)
    (let ([rel (related x y)])
      (cond
        [(null? rel) (list x)]
        [else (cons x (map (lambda (d) (prog1 (neighbour d) y)) rel))])))

我想要做的是尝试让它尾递归。我知道我需要做类似的事情：

(define (prog1 x y)
  (prog1-iter x y `()))

(define (prog1-iter x y acc)
  (...
   ))

但我不确定如何从我的代码转到这段代码......我认为这是因为原件中有一个地图，我不确定如何将它合并到一个prog1-iter. 有人可以指出我正确的方向！

4

1 回答 1

4

对于本质上是迭代的东西，尾递归很容易编写。您的函数可能会多次调用自身，因此它不会很简单。尽管如此，任何程序都可以进行迭代（例如，您的计算机是一个巨大的迭代机器），所以它可以完成。

首先，您的函数不是直接递归的（即prog1不直接调用自身）。而是prog1调用map，然后调用你给它的 lambda（可能多次），然后调用prog1; 所以它是间接的。调用map不是尾调用；对 lambda的调用map肯定不是尾调用（它可能需要多次调用它）；来自 lambda 的调用prog1是尾调用。

因此，当您要求它是“尾递归”时，我不确定您到底需要什么。您是否希望从自身到自身的调用链中的每个调用prog1都是尾调用？或者你想让程序中的每个调用都成为尾调用？存在 的“尾递归”版本map，但它们仅对来自mapto的调用是“尾递归” map，而不是对映射函数的调用，因此它们对您的情况没有用处。

使程序中的每个调用都成为尾调用的一般方法称为continuation-passing style。基本上，每个函数都有一个额外的函数参数，即“延续”。不是对函数进行非尾调用，而是对它进行尾调用，并传递给它一个延续，指定如何处理函数调用的结果。基本上，延续将包含非尾调用之后的原始函数的“其余部分”，并将原始非尾调用的“返回结果”作为参数。我将把它作为练习如何将您的程序转换为 CPS。

于 2012-12-29T00:07:51.137 回答