c++ - 使显式堆栈算法更快

Question

有一些递归算法可以很快填满堆栈。一种解决方案是使堆栈显式化，从而将算法转变为迭代算法。

但我注意到显式堆栈会使算法变慢很多(这可能不会让我感到惊讶)。是否有任何通用的 C++ 指南可以使显式堆栈更快？它们是否有可能比原始递归算法运行得更快？

---

编辑: 下面是我为其编写显式堆栈的函数。我也粘贴了迭代代码。出于某种原因，使用 std::vector 而不是 std::stack 更快，这很令人惊讶。

// A(m, n) = n + 1                 if m = 0
//         = A(m - 1, 1)           if m > 0 and n = 0
//         = A(m - 1, A(m, n - 1)) if m, n > 0


int A(int m, int n, long& iterations,
    std::vector<std::pair<int, int> >& stack)
{
    stack.push_back(std::make_pair(m, n));
    long result = 0;
    bool result_available = false;

    while (stack.size() > 0)
    {
        iterations += 1;

        if (result_available) {
            stack.back().second = result;
            result_available = false;
        }

        m = stack.back().first;
        n = stack.back().second;
        stack.pop_back();

        if (m == 0) {
            result = n + 1;
            result_available = true;
        }
        else if (m > 0 && n == 0) {
            stack.push_back(std::make_pair(m - 1, 1));
        }
        else if (m > 0 && n > 0) {
            stack.push_back(std::make_pair(m - 1, n));
            stack.push_back(std::make_pair(m, n - 1));
        }
    }

    return result;
}

Answer 1

1. 尽量少从堆中分配内存。它非常慢。

2. 消除尾递归 - 对于它们，您不需要递归调用。它看起来不像递归解决方案那么优雅，但速度更快。有关如何完成的示例，请搜索 Fibonacci 实现。有 2 个递归变体和一个非递归变体。

3. 使用显式堆栈不会更快，因为函数调用和通过堆栈传递参数是一些最快的汇编程序指令，因为它们经常被使用。