c++11 - 如何使这个函数尾递归？

Question

我试图使这个函数成为尾递归函数，这样我就可以用它来处理大量事件而不会出现堆栈溢出。我确保将递归调用放在函数的最后一行，但它仍然会用递归调用淹没调用堆栈。

我还需要做些什么来使其成为尾递归，还是我的编译器不知道如何优化它？

我应该放弃这个函数并改用循环吗？

template <class Csi>
void GetEvents(EventHandle handle, vector<int> desiredCodes, vector<EventHandle> &events, Csi &csi)
{
    if (handle == INVALID_HANDLE)
    {
        return;
    }

    int code = csi.GetEventCode(handle);
    bool codeSatisfiesSearch = (find(desiredCodes.begin(), desiredCodes.end(), code) != desiredCodes.end());
    if (codeSatisfiesSearch)
    {
        events.push_back(handle);

        handle = csi.FindNextEventEx(handle, &desiredCodes[0], 0, desiredCodes.size());
    }
    else
    {
        handle = csi.FindNextEventEx(handle, &desiredCodes[0], 0, desiredCodes.size());
    }
    return GetEvents(handle, desiredCodes, events, csi);
}

Answer 1

从表面上看这个问题。

在当前形式中，代码不适合 TCO，因为 vector<int> desiredCodes按值传递。它要求调用者在递归调用后销毁局部向量，因此尾调用优化不是一个选项。

当我更改代码以通过 const 引用传递向量时，我注意到最新版本的 clang确实优化了尾调用:https://gcc.godbolt.org/z/qM7QVv

然而，gcc仍然没有:https://gcc.godbolt.org/z/u7yIvR .我注意到它是 push_back这会阻止 gcc 优化 - 当被注释掉时，递归调用被消除。

在替换 events.push_back(handle) 时，我能够获得 gcc 9.2 来优化递归调用与

events.resize(events.size() + 1);
events[events.size()  - 1] = handle;

所有这些都表明，C++ 中的 TCO 是不可依赖的，因为它非常脆弱，并且取决于不可预测的因素。这是您偶尔可能会得到的一笔不错的奖金，但不是您可以用来构 build 计的东西。

如果您对 TCO 感兴趣(例如，我对它感兴趣)，您会更幸运地使用更可预测的语言，例如 C，或者更好的是，使用函数式风格的语言。