C++实现SICP累加器传递风格：递归Lambda编译失败求助

累加器传递风格是SICP里的经典递归优化技巧，通过传递累加器实现尾递归，避免不必要的栈开销。你用Python实现的版本很直观，但C++里直接写递归Lambda会编译失败——因为Lambda是匿名类型，默认无法引用自身。下面是几种可行的实现方案：

先回顾你给出的Python实现：

def fac(n):
    def facAcc(i, acc):
        if (i == n): 
            return acc
        else:
            return facAcc(i+1, (i+1)*acc)

    return facAcc(0, 1) # 0! = 1

>>> list(map(fac, range(0,6))) 
[1, 1, 2, 6, 24, 120]

方案1：用std::function显式声明类型 #

通过std::function先定义递归函数的类型，再让Lambda捕获这个函数对象实现递归：

#include <functional>
#include <vector>
#include <iostream>

long long fac(int n) {
    std::function<long long(int, long long)> facAcc;
    facAcc = [n, &facAcc](int i, long long acc) -> long long {
        if (i == n) {
            return acc;
        } else {
            return facAcc(i + 1, (i + 1LL) * acc);
        }
    };
    return facAcc(0, 1);
}

int main() {
    std::vector<long long> results;
    for (int i = 0; i < 6; ++i) {
        results.push_back(fac(i));
    }
    // 输出：1 1 2 6 24 120
    for (auto num : results) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

编译时需要链接标准库，g命令：g++ -std=c++11 your_file.cpp -o fac（C11及以上支持std::function和Lambda）。

方案2：Y组合子（纯函数式风格） #

Y组合子是函数式编程里实现匿名递归的经典工具，不需要依赖std::function的显式类型声明：

#include <functional>
#include <vector>
#include <iostream>

template<typename Func>
struct YCombinator {
    Func func;

    template<typename... Args>
    decltype(auto) operator()(Args&&... args) {
        return func(*this, std::forward<Args>(args)...);
    }
};

template<typename Func>
YCombinator<Func> makeYCombinator(Func&& func) {
    return YCombinator<Func>{std::forward<Func>(func)};
}

long long fac(int n) {
    auto facAcc = makeYCombinator([n](auto self, int i, long long acc) -> long long {
        if (i == n) {
            return acc;
        } else {
            return self(i + 1, (i + 1LL) * acc);
        }
    });
    return facAcc(0, 1);
}

int main() {
    std::vector<long long> results;
    for (int i = 0; i < 6; ++i) {
        results.push_back(fac(i));
    }
    for (auto num : results) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

这里Lambda通过参数self引用Y组合子实例，从而实现递归，完全贴合SICP的函数式思路。

方案3：C++23递归Lambda（最简写法） #

C++23直接支持递归Lambda，只需要在Lambda参数列表里用this auto self声明自身引用：

#include <vector>
#include <iostream>

long long fac(int n) {
    auto facAcc = [n](this auto self, int i, long long acc) -> long long {
        if (i == n) {
            return acc;
        } else {
            return self(i + 1, (i + 1LL) * acc);
        }
    };
    return facAcc(0, 1);
}

int main() {
    std::vector<long long> results;
    for (int i = 0; i < 6; ++i) {
        results.push_back(fac(i));
    }
    for (auto num : results) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

编译时需要指定C++23标准：g++ -std=c++23 your_file.cpp -o fac，适合用新版本编译器的场景。

内容的提问来源于stack exchange，提问作者Hank