尾递归仅仅是 CPS 的一个特例吗？

Question

我已经 map 实现了尾递归和延续传递风格。两个版本非常相似：

var inc = x => ++x;
var xs = [1,2,3,4,5];

var mapR = f => xs => {
    var rec = acc => {
        acc[acc.length] = f(xs[acc.length]);
        return acc.length < xs.length ? rec(acc) : acc;
    }

    return rec([]);
}

mapR(inc)(xs); // [2,3,4,5,6]

var mapC = f => xs => cc => {
    var rec = acc => cc => {
        acc[acc.length] = f(xs[acc.length]);
        return acc.length < xs.length ? cc(acc)(rec) : acc;
    }

    return cc(rec([])(rec));
}

mapC(inc)(xs)(console.log.bind(console)); // [2,3,4,5,6]

而不是 cc(acc)(rec) 我显然也可以写 rec(acc)。我的结论是否正确，尾递归只是 CPS 的特例，用 var rec = acc => {...} 编写的 mapC 是正确的 CPS 函数吗？

Answer 1

我会用纯 CPS 编写如下内容：

const inc = x => cont => cont(x+1);

const map = f => xss => cont => {
    if (!xss.length) cont([]);
    else f(xss[0])(x => map(f)(xss.slice(1))(xs => cont([x].concat(xs))));
};

// or with an accumulator:
const mapA = f => xs => cont => {
    const rec = acc => {
        if (acc.length >= xs.length) cont(acc);
        else f(xs[acc.length])(x => {
            acc.push(x);
            rec(acc);
        });
    }
    rec([]);
};

Is tail recursion merely a special case of CPS?

我不会这么说。 CPS 与递归关系不大。
然而，CPS 通常只包含尾调用，这使得堆栈变得多余 - 而且功能如此强大。

Answer 2

为了能够回答问题，需要先弄清楚术语：

递归：从同一个函数中调用一个函数
尾调用：一个函数在它return之前做的最后一件事是调用另一个函数
尾递归：#1 和#2 合并
直接风格：以函数为特征的顺序编程风格，return 给它们的调用者
Continuation Passing Style (CPS)：编程风格的特点是函数带有一个额外的continuation 参数，调用它们的continuation 而不是return调用它们的调用者（continuations只是 Javascript)

如何关联这些术语？

Direct Style 和 Continuation Passing Style 是控制流的对立概念
尾递归调用是尾调用的特化
递归和尾递归是直接式的技术
每个（尾）递归算法都可以转换成它的CPS形式，因为CPS比递归有更强的表达能力

比较尾递归和 CPS 没有意义，因为这两种技术代表了应该如何处理控制流的不同范例 - 即使它们有很多相似之处：

两者当然都可以描述递归控制流
两者都没有调用堆栈
但是：尾递归是静态的，CPS是动态的控制流（解决接下来调用哪个函数）

最后一点：描述递归算法的 CPS 函数将其数据存储在递归定义的匿名函数（闭包）环境中。这意味着，CPS 不会比递归更有效地使用内存。

尾递归仅仅是 CPS 的一个特例吗？

Is tail recursion merely a special case of CPS?

javascript

tail-recursion

continuations