C++ 关于使用堆栈将递归转换为迭代的困惑

当你问问题的时候，一定要记minimal, reproducible example分.这有助于每个人理解问题并生成和测试潜在的答案.

如果您创建了这样一个示例，很明显，迭代解决方案的版本1永远不会返回，而版本2总是返回0，这两个版本都不是正确的候选.

递归可能很有挑战性，但我认为在这个例子中，我们可以通过一种通用的方法将递归函数转换为迭代函数.

让我们看一下sigma1的递归实现，

int sigma1(int n) {
    if (n == 0)
        return 0;
    else
        return n + sigma1(n - 1);
}

在幕后，调用该函数会 for each 递归调用生成一个新的堆栈框架(假设编译器没有对其进行优化).这些调用帧中的每一个将具有该帧的自变量n的值，该值将在递归的每一级递减1.我们可以用同样的方式考虑迭代版本，将值n存储在显式std::stack<int>上，而不是由调用堆栈自动处理它.

当递归终止并且调用帧展开时，本地值n被加到前一次调用的结果中，从而创建要返回的新结果.同样，我们可以从显式std::stack<int>中弹出值，并将它们添加到迭代版本中的运行总计中.

该函数将如下所示，

int sigma1_stack(int n) {
    std::stack<int> stack;
    for (int i = n; i > 0; --i)
        stack.push(i);

    int res{};
    while (not stack.empty()) {
        res += stack.top();
        stack.pop();
    }

    return res;
}

现在，在这个特定的场景中，您可以将两个循环简化为没有堆栈的单个迭代循环.当然，情况不会总是这样.

int sigma1_iter(int n) {
    int res{};
    for (int i = n; i > 0; --i)
        res += i;
    return res;
}

我采用了您发布的代码，并将其更改为使用std::stack<int>进行编译，因为您没有发布完整的示例.我还为sigma1和sigma2以及相应的输出添加了正确的迭代版本.希望这能对你有所帮助.

示例代码

#include <iostream>
#include <stack>

using std::cout, std::endl;

int sigma1(int n) {
    if (n == 0)
        return 0;
    else
        return n + sigma1(n - 1);
}

int sigma1_iter_v1(int n) {
    std::stack<int> stack;
    stack.push(n);

    int res = 0;
    while (not stack.empty()) {
        int elm = stack.top();
        stack.pop();
        if (elm == 0)
            return res;
        else {
            res += n;
            stack.push(n - 1);
        }
    }

    return res;
}

int sigma1_iter_v2(int n) {
    std::stack<int> stack;
    stack.push(n);

    int res = 0;
    while (not stack.empty()) {
        if (n > 0) {
            n--;
            stack.push(n);
        } else {
            int elm = stack.top();
            stack.pop();
            if(elm == 0)
                return res;
            else {
                res += n;
            }
        }
    }

    return res;
}

int sigma1_iter(int n) {
    int res{};
    for (int i = n; i > 0; --i)
        res += i;
    return res;
}

int sigma1_stack(int n) {
    std::stack<int> stack;
    for (int i = n; i > 0; --i)
        stack.push(i);

    int res{};
    while (not stack.empty()) {
        res += stack.top();
        stack.pop();
    }

    return res;
}

int sigma2(int n, int res = 0) {
    if (n == 0)
        return res;
    else
        return sigma2(n - 1, n + res);
}

int sigma2_iter(int n) {
    int res{};
    for (int i = n; i > 0; --i)
        res += i;
    return res;
}

int main(int argc, const char *argv[]) {
    cout << "sigma1         : " << sigma1(20) << endl;
    cout << "sigma1_iter   : " << sigma1_iter(20) << endl;
    cout << "sigma1_stack  : " << sigma1_stack(20) << endl;
    // This never returns
    // cout << "sigma1_iter_v1 : " << sigma1_iter_v1(20) << endl;
    cout << "sigma1_iter_v1 : " << "never returns" << endl;
    cout << "sigma1_iter_v2 : " << sigma1_iter_v2(20) << endl;

    cout << endl;
    cout << "sigma2         : " << sigma2(20) << endl;
    cout << "sigma2_iter    : " << sigma2_iter(20) << endl;
    return 0;
}

输出

sigma1         : 210
sigma1_iter    : 210
sigma1_stack   : 210
sigma1_iter_v1 : never returns
sigma1_iter_v2 : 0

sigma2         : 210
sigma2_iter    : 210