我该怎么做这个尾递归？

Question

我有这个代码:

(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.有人能指出我正确的方向!

Answer 1

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

首先，您的函数不是直接递归的（即prog1不直接调用自身）。相反，prog1调用map，然后调用您给它的 lambda（可能多次），然后调用prog1; 所以它是间接的。对 的调用map不是尾调用；对 lambda 的调用map当然不是尾部调用（可能需要多次调用）；从 lambda 到 的调用prog1是尾调用。

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

使程序中的每个调用都成为尾调用的通用方法称为连续传递风格。基本上，每个函数都需要一个附加的函数参数，即“延续”。您不是对函数进行非尾部调用，而是对其进行尾部调用，并向其传递一个延续，指定如何处理函数调用的结果。基本上，延续将包含非尾调用之后原始函数的“其余部分”，并且它将原始非尾调用的“返回结果”作为参数。我将把如何将程序转换为 CPS 作为练习。