c++ - 使用堆栈递归循环

Question

我想使用堆栈和循环将以下程序转换为非递归代码:

void write(int n) {
    if (n>0) {
        write(n-1);
        cout << n << " ";
        write(n-1);
    }
}

这是我正在使用的代码，但目前不起作用，我不知道为什么:

stack<int> S;
S.push(n);
while (not S.empty()) {
    int k = S.top(); 
    S.pop()
    if (k>0) {
        S.push(k-1);
        cout<<k<<" ";
        S.push(k-1);
    }
}

它不起作用，我不知道如何模拟该递归。我认为将等效的递归调用插入堆栈就足够了。

谢谢

Answer 1

问题是您向堆栈执行了 2 次推送，但在使用所有调用链进行打印之前，首先递归调用了 write()。

这是递归调用的等效迭代:

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

while( not S.empty() ) {
    int k = S.top();
    S.pop();
    for( int i = k - 1; i > 0; --i ) {
        S.push( i );
    }
    std::cout << k << " ";
}